Theories of orders on the set of words
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 40 (2006) no. 1, pp. 53-74.

It is shown that small fragments of the first-order theory of the subword order, the (partial) lexicographic path ordering on words, the homomorphism preorder, and the infix order are undecidable. This is in contrast to the decidability of the monadic second-order theory of the prefix order [M.O. Rabin, Trans. Amer. Math. Soc., 1969] and of the theory of the total lexicographic path ordering [P. Narendran and M. Rusinowitch, Lect. Notes Artificial Intelligence, 2000] and, in case of the subword and the lexicographic path order, improves upon a result by Comon & Treinen [H. Comon and R. Treinen, Lect. Notes Comp. Sci., 1994]. Our proofs rely on the undecidability of the positive Σ 1 -theory of (,+,·) [Y. Matiyasevich, Hilbert’s Tenth Problem, 1993] and on Treinen’s technique [R. Treinen, J. Symbolic Comput., 1992] that allows to reduce Post’s correspondence problem to logical theories.

@article{ITA_2006__40_1_53_0,
     author = {Kuske, Dietrich},
     title = {Theories of orders on the set of words},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {53--74},
     publisher = {EDP-Sciences},
     volume = {40},
     number = {1},
     year = {2006},
     doi = {10.1051/ita:2005039},
     zbl = {1098.03021},
     mrnumber = {2197283},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ita:2005039/}
}
TY  - JOUR
AU  - Kuske, Dietrich
TI  - Theories of orders on the set of words
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2006
DA  - 2006///
SP  - 53
EP  - 74
VL  - 40
IS  - 1
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita:2005039/
UR  - https://zbmath.org/?q=an%3A1098.03021
UR  - https://www.ams.org/mathscinet-getitem?mr=2197283
UR  - https://doi.org/10.1051/ita:2005039
DO  - 10.1051/ita:2005039
LA  - en
ID  - ITA_2006__40_1_53_0
ER  - 
Kuske, Dietrich. Theories of orders on the set of words. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 40 (2006) no. 1, pp. 53-74. doi : 10.1051/ita:2005039. http://www.numdam.org/articles/10.1051/ita:2005039/

[1] F. Baader and T. Nipkow, Term Rewriting and All That. Cambridge University Press (1998). | MR 1629216 | Zbl 0948.68098

[2] A. Björner, The Möbius function of subword order, in Invariant theory and tableaux, IMA Springer. Math. Appl. 19 (1990) 118-124. | Zbl 0706.06007

[3] A. Boudet and H. Comon, About the theory of tree embedding, in TAPSOFT'93, Springer. Lect. Notes Comp. Sci. 668 (1993) 376-390.

[4] J.R. Büchi, Transfinite automata recursions and weak second order theory of ordinals, in Logic, Methodology and Philos. Sci., North Holland, Amsterdam (1965) 3-23. | Zbl 0207.31001

[5] J.R. Büchi and S. Senger, Coding in the existential theory of concatentation. Archiv Math. Logik 26 (1986) 101-106. | Zbl 0646.03040

[6] H. Comon and R. Treinen, Ordering constraints on trees, in CAAP'94, Springer. Lect. Notes Comp. Sci. 787 (1994) 1-14. | Zbl 0938.68589

[7] H. Comon and R. Treinen, The first-order theory of lexicographic path orderings is undecidable. Theor. Comput. Sci. 176 (1997) 67-87. | Zbl 0903.68107

[8] D.E. Daykin, To find all “suitable” orders of 0,1-vectors. Congr. Numer. 113 (1996) 55-60. Festschrift for C. St. J. A. Nash-Williams. | Zbl 0898.15002

[9] N. Dershowitz, Orderings for term rewriting systems. Theor. Comput. Sci. 17 (1982) 279-301. | Zbl 0525.68054

[10] V.G. Durnev, Undecidability of the positive 3 -theory of a free semigroup. Sibirsky Matematicheskie Jurnal 36 (1995) 1067-1080. | Zbl 0853.20035

[11] F.D. Farmer, Homotopy spheres in formal languages. Stud. Appl. Math. 66 (1982) 171-179. | Zbl 0511.55009

[12] A. Finkel and Ph. Schnoebelen, Well-structured transition systems everywhere! Theor. Comput. Sci. 256 (2001) 63-92. | Zbl 0973.68170

[13] K. Gödel, Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I. Monatshefte für Mathematik und Physik 38 (1931) 173-198. | JFM 57.0054.02

[14] T. Harju and L. Illie, On quasi orders of words and the confluence property. Theor. Comput. Sci. 200 (1998) 205-224. | Zbl 0915.68104

[15] G. Higman, Ordering by divisibility in abstract algebras. Proc. London Math. Soc. 2 (1952) 326-336. | Zbl 0047.03402

[16] S. Kosub and K. Wagner, The boolean hierarchy of NP-partitions, in STACS 2000, Springer. Lect. Notes Comp. Sci. 1770 (2000) 157-168. | Zbl 0959.68521

[17] D. Kuske, Emptiness is decidable for asynchronous cellular machines, in CONCUR 2000. Springer. Lect. Notes Comp. Sci. 1877 (2000) 536-551. | Zbl 0999.68132

[18] U. Leck, Nonexistence of a Kruskal-Katona type theorem for subword orders. Technical Report 98-06, Universität Rostock, Fachbereich Mathematik (1998). | Zbl 1058.06003

[19] M. Lothaire, Combinatorics on Words. Addison-Wesley (1983). | MR 675953 | Zbl 0514.20045

[20] G.S. Makanin, The problem of solvability of equations in a free semigroup, Math. Sbornik, 103 (1977) 147-236. In Russian; English translation in: Math. USSR Sbornik 32 (1977). | Zbl 0396.20037

[21] Y. Matiyasevich, Hilbert's Tenth Problem. MIT Press (1993). | Zbl 0790.03008

[22] P. Narendran and M. Rusinowitch, The theory of total unary rpo is decidable, in Computational Logic 2000, Springer. Lect. Notes Artificial Intelligence 1861 (2000) 660-672. | Zbl 0983.68175

[23] M.O. Rabin, Decidability of second-order theories and automata on infinite trees. Trans. Amer. Math. Soc. 141 (1969) 1-35. | Zbl 0221.02031

[24] V.L. Selivanov, Boolean hierarchy of partitions over reducible bases. Algebra and Logic 43 (2004) 77-109. | Zbl 1061.03044

[25] R. Treinen, A new method for undecidability proofs of first order theories. J. Symbolic Comput. 14 (1992) 437-458. | Zbl 0769.03026

Cité par Sources :