9 found
Order:
  1.  18
    Existential Arithmetization of Diophantine Equations.Yuri Matiyasevich - 2009 - Annals of Pure and Applied Logic 157 (2-3):225-233.
    A new method of coding Diophantine equations is introduced. This method allows checking that a coded sequence of natural numbers is a solution of a coded equation without decoding; defining by a purely existential formula, the code of an equation equivalent to a system of indefinitely many copies of an equation represented by its code. The new method leads to a much simpler construction of a universal Diophantine equation and to the existential arithmetization of Turing machines, register machines, and partial (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  2.  12
    A Direct Method for Simulating Partial Recursive Functions by Diophantine Equations.Yuri Matiyasevich - 1994 - Annals of Pure and Applied Logic 67 (1-3):325-348.
    A new proof is given of the celebrated theorem of M. Davis, H. Putnam and J. Robinson concerning exponential Diophantine representation of recursively enumerable predicates. The proof goes by induction on the defining scheme of a partial recursive function.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  3.  7
    Window-Accumulated Subsequence Matching Problem is Linear.Luc Boasson, Patrick Cegielski, Irène Guessarian & Yuri Matiyasevich - 2001 - Annals of Pure and Applied Logic 113 (1-3):59-80.
    Given two strings, text t of length n, and pattern p = p1…pk of length k, and given a natural number w, the subsequence matching problem consists in finding the number of size w windows of text t which contain pattern p as a subsequence, i.e. the letters p1,…,pk occur in the window, in the same order as in p, but not necessarily consecutively . Subsequence matching is used for finding frequent patterns and association rules in databases. We generalize the (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  4.  3
    First St. Petersburg Conference on Days of Logic and Computability.Yuri Matiyasevich - 2001 - Annals of Pure and Applied Logic 113 (1):3.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  5.  6
    Preface.Sergei Artemov, Yuri Matiyasevich, Grigori Mints & Anatol Slissenko - 2010 - Annals of Pure and Applied Logic 162 (3):173-174.
  6.  28
    Definability and Decidability Issues in Extensions of the Integers with the Divisibility Predicate.Patrick Cegielski, Yuri Matiyasevich & Denis Richard - 1996 - Journal of Symbolic Logic 61 (2):515-540.
    Let M be a first-order structure; we denote by DEF(M) the set of all first-order definable relations and functions within M. Let π be any one-to-one function from N into the set of prime integers. Let ∣ and $\bullet$ be respectively the divisibility relation and multiplication as function. We show that the sets DEF(N,π,∣) and $\mathrm{DEF}(\mathbb{N},\pi,\bullet)$ are equal. However there exists function π such that the set DEF(N,π,∣), or, equivalently, $\mathrm{DEF}(\mathbb{N},\pi,\bullet)$ is not equal to $\mathrm{DEF}(\mathbb{N},+,\bullet)$ . Nevertheless, in all cases (...)
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  7.  5
    Preface.Yuri Matiyasevich & Anil Nerode - 1996 - Annals of Pure and Applied Logic 78 (1-3):1.
  8.  4
    Preface.Yuri Matiyasevich - 2001 - Annals of Pure and Applied Logic 113 (1-3):1.
  9.  1
    Preface.Yuri Matiyasevich & Sergei Artemov - 2006 - Annals of Pure and Applied Logic 141 (3):307.