Personal Journal of Yuri Matiyasevich
Content (in reverse chronological order)

Below the content is listed in the reverse chronological order of the first addition or last substantial modification of an item.

Formats of files

---

A Criterion for Vertex Colorability of a Graph Stated in Terms of Edge Orientations

proposed by Yuri MATIYASEVICH

English translation of a paper published in Russian in 1974

Homepage of the paper


 

Hidden Life of Riemann's Zeta Function

revealed by Yuri MATIYASEVICH

Homepage of the ongoing research


 

A Class of Primality Criteria Formulated in Terms of the Divisibility of Binomial Coefficients

by Yuri MATIYASEVICH

Homepage of the paper


 

Identities with Bernoulli numbers

found by Yuri MATIYASEVICH

.html (last modified on August 30, 2006)


 

Some Probabilistic Restatements of the Four Color Conjecture

found by Yuri MATIYASEVICH
This is a preprint of a paper accepted for publication in:
Journal of Graph Theory © (2003) John Wiley and Sons, Inc.


.ps.gz (163Kb)       .pdf.gz (164Kb)




One Probabilistic Equivalent of the Four Color Conjecture

found by Yuri MATIYASEVICH
This is a translation of my paper published in:
Teoriya Veroyatnostei i ee Primeneniya, 48(2003), 411--416


.ps.gz (141Kb)       .pdf.gz (145Kb)




Real-time recognition of the inclusion relation

made available by Yuri MATIYASEVICH
This is an English translation of my paper "Raspoznovanie v realnoe vremya otnosheniya vkhozhdeniya" published originally in Russian in "Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo instututa im. V.A.Steklova Akademii Nauk SSSR", vol. 20, pages 104-114 (1971);
MR 45#3208; ZBl 0222.02029; ZBl 0253.02043
The English translation was published in "J. of Sovjet Mathematics", vol. 1, No.1, pp. 64-70, (1973), ISSN 0090-4104;© Plenum Publishing Corporation

.ps.gz (388Kb)       .pdf.gz (365Kb)

.ps (483Kb)       .pdf (377Kb)


 


Reduction of an arbitrary Diophantine equation to one in 13 unknowns

published by Yuri MATIYASEVICH and Julia ROBINSON
in Acta Arithmetica, XXVII (1975), pages 521-549; MR 52, #8033.
homepage of the paper


 


HILBERT'S TENTH PROBLEM:


What can we do with Diophantine equations?

a series of 5 lectures read by Yuri MATIYASEVICH

at distinguished chair of Pacific Institute of Mathematical Sciencies in Calgary in February-March 2000

streaming video from Calgary, Canada


 

How to draw a tree correctly

a talk given by Yuri MATIYASEVICH

at colloquium of Department of Mathematics and Statistique of the University of Calgary on March 9, 2000

streaming video from Calgary, Canada


 

Window-Accumulated Subsequence matching Problem is linear

which was proved by Irène Guessarian, Luc Boasson, Patrick Cegielski, and Yuri MATIYASEVICH

published in PODS'99 Proceedings, 1999, 327-336

.ps (496Kb)


 

Two Universal 3-Quantifier Representations of Recursively Enumerable Sets

constructed by Yuri MATIYASEVICH and Julia ROBINSON

.ps.gz (63Kb)       .pdf.gz (154Kb)

.ps (160Kb)       .pdf (189Kb)


 

HILBERT'S TENTH PROBLEM:


What can we do with Diophantine equations?

a talk given by Yuri MATIYASEVICH

at a seminar of IREM in Paris

.ps.gz (68Kb)  .pdf.gz (154Kb)

.ps (177Kb)  .pdf (263Kb)


 

A visual Sieve for Prime Numbers

invented by Yuri MATIYASEVICH and Boris STECHKIN

.html


 

The Four Colour Theorem as a possible corollary of binomial summation

suggested by Yuri MATIYASEVICH

An invited lecture on this subject was presented at JAF'13 and was published in the Proceedings, ISBN 2-9511539-0-2, 119-134 (1997).

A version of this paper was submitted to the Electronic Journal of Combinatorics but did not meet the high standards of this Journal.

A version of this paper appeared in  Theoretical Computer Science , 257(1-2):167--183, 2001.

.ps.gz (108Kb)

.ps (588Kb)


 

A binomial representation of the 3x+1 problem

found by Maurice MARGENSTERN and Yuri MATIYASEVICH

Published in Acta Arithmetica, XCI.4, 1999, 367-378

.ps.gz (60Kb)  .pdf.gz (131Kb)

.ps (147Kb)  .pdf (204Kb)


 

Decision Problems for Semi-Thue Systems with a Few Rules

studied by Yuri MATIYASEVICH and Géraud SENIZERGUEZ,

presented at LICS'96, Eleventh Annual IEEE Symposium on Logic in Computer Science.

New Brunswick, NJ, USA, 1996.

Preliminary version of full paper: .ps


 

My collaboration with Julia Robinson

reminiscence by Yuri MATIYASEVICH

Originally published in The Mathematical Intelligencer, vol.14, no.4, 1992, pp.38-45

.html


 

Hilbert's tenth problem

book written by Yuri MATIYASEVICH

homepage of the book


 

Generalized Chebyshev polynomials

found by Yuri MATIYASEVICH

.html (last modified on April 7, 1998)


 

Elimination of bounded universal quantifiers standing in front of a quantifier-free arithmetical formula

by Yuri MATIYASEVICH

.tex   .dvi   .ps


 

Bounding the existential variables after the elimination of a bounded universal quantifier

by Yuri MATIYASEVICH

.tex   .dvi   .ps


 

Proof Procedures as Bases for Metamathematical Proofs in Discrete Mathematics

by Yuri MATIYASEVICH

.ps.gz


 

A Polynomial related to Colourings of Triangulation of Sphere

introduced by Yuri Matiyasevich

.html (last modified on July 4, 1997)


 

Solving trace equations using lexicographical normal forms

by Volker DIEKERT, Yuri MATIYASEVICH, and Anca MUSCHOLL

presented at ICALP'97 (Bologna, Italy)

 

Abstract and BibTeX entry

.dvi

.ps.Z


 

Simultaneous Rigid E-Unification and Related Algorithmic Problems

by A. DEGTYAREV, Yu. MATIYASEVICH and A. VORONKOV

presented at LICS'96, Eleventh Annual IEEE Symposium on Logic in Computer Science.

New Brunswick, NJ, 1996.

abstract,

.ps (9 pages)

---

URL of my original Home page is http://logic.pdmi.ras.ru/~yumat/index.html.