Geodesic
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

Voir la notice de l'article provenant de la source Numdam

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.

DOI : 10.1051/ita:2005039
Classification : 03D35 
@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},
     mrnumber = {2197283},
     zbl = {1098.03021},
     language = {en},
     url = {http://geodesic.mathdoc.fr/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
SP  - 53
EP  - 74
VL  - 40
IS  - 1
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/articles/10.1051/ita:2005039/
DO  - 10.1051/ita:2005039
LA  - en
ID  - ITA_2006__40_1_53_0
ER  - 
%0 Journal Article
%A Kuske, Dietrich
%T Theories of orders on the set of words
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2006
%P 53-74
%V 40
%N 1
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/articles/10.1051/ita:2005039/
%R 10.1051/ita:2005039
%G en
%F ITA_2006__40_1_53_0
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

Cité par Sources :