Geodesic
The decision problem for some logics for finite words on infinite alphabets
Zapiski Nauchnykh Seminarov POMI, Studies in constructive mathematics and mathematical logic. Part XI, Tome 358 (2008), pp. 100-119

Voir la notice de l'article provenant de la source Math-Net.Ru

This paper is a follow-up of a previous paper where the logical characterization of Eilenberg, Elgot, and Shepherdson of $n$ary synchronous relations was investigated in the case where the alphabet has infinitely many letters. Here we show that modifying one of the predicate leads to a completely different picture for infinite alphabets though it does not change the expressive power for finite alphabets. Indeed, roughly speaking, being able to express the fact that two words end with the same symbol leads to an undecidable theory, already for the $\Sigma_2$ fragment. Finally, we show that the existential fragment is decidable. Bibl. – 19 titles. 
@article{ZNSL_2008_358_a5,
     author = {S. Grigorieff and Ch. Choffrut},
     title = {The decision problem for some logics for finite words on infinite alphabets},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {100--119},
     publisher = {mathdoc},
     volume = {358},
     year = {2008},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_2008_358_a5/}
}
TY  - JOUR
AU  - S. Grigorieff
AU  - Ch. Choffrut
TI  - The decision problem for some logics for finite words on infinite alphabets
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 2008
SP  - 100
EP  - 119
VL  - 358
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/ZNSL_2008_358_a5/
LA  - en
ID  - ZNSL_2008_358_a5
ER  - 
%0 Journal Article
%A S. Grigorieff
%A Ch. Choffrut
%T The decision problem for some logics for finite words on infinite alphabets
%J Zapiski Nauchnykh Seminarov POMI
%D 2008
%P 100-119
%V 358
%I mathdoc
%U http://geodesic.mathdoc.fr/item/ZNSL_2008_358_a5/
%G en
%F ZNSL_2008_358_a5
S. Grigorieff; Ch. Choffrut. The decision problem for some logics for finite words on infinite alphabets. Zapiski Nauchnykh Seminarov POMI, Studies in constructive mathematics and mathematical logic. Part XI, Tome 358 (2008), pp. 100-119. http://geodesic.mathdoc.fr/item/ZNSL_2008_358_a5/