Deciding whether a relation defined in Presburger logic can be defined in weaker logics
Choffrut, Christian
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 42 (2008), p. 121-135 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

We consider logics on ℤ and ℕ which are weaker than Presburger arithmetic and we settle the following decision problem: given a k-ary relation on ℤ and ℕ which are first order definable in Presburger arithmetic, are they definable in these weaker logics? These logics, intuitively, are obtained by considering modulo and threshold counting predicates for differences of two variables.

Publié le : 2008-01-01
DOI : https://doi.org/10.1051/ita:2007047
Classification:  03B10,  68Q70 
@article{ITA_2008__42_1_121_0,
     author = {Choffrut, Christian},
     title = {Deciding whether a relation defined in Presburger logic can be defined in weaker logics},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {42},
     year = {2008},
     pages = {121-135},
     doi = {10.1051/ita:2007047},
     mrnumber = {2382547},
     zbl = {1158.03007},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_2008__42_1_121_0}
}

Choffrut, Christian. Deciding whether a relation defined in Presburger logic can be defined in weaker logics. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 42 (2008) pp. 121-135. doi : 10.1051/ita:2007047. http://gdmltest.u-ga.fr/item/ITA_2008__42_1_121_0/

[1] O. Carton, C. Choffrut and S. Grigorieff. Decision problems for rational relations. RAIRO-Theor. Inf. Appl. 40 (2006) 255-275. | Numdam | MR 2252638 | Zbl 1112.03008

[2] C. Choffrut and M. Goldwurm. Timed automata with periodic clock constraints. J. Algebra Lang. Comput. 5 (2000) 371-404. | MR 1788401 | Zbl 0964.68076

[3] S. Eilenberg. Automata, Languages and Machines, volume A. Academic Press (1974). | MR 530382 | Zbl 0317.94045

[4] S. Eilenberg and M.-P. Schützenbeger. Rational sets in commutative monoids. J. Algebra 13 (1969) 173-191. | MR 246985 | Zbl 0206.02703

[5] S. Ginsburg and E.H. Spanier. Bounded regular sets. Proc. Amer. Math. Soc. 17 (1966) 1043-1049. | MR 201310 | Zbl 0147.25301

[6] M. Koubarakis. Complexity results for first-order theories of temporal constraints. KR (1994) 379-390.

[7] H. Läuchli and C. Savioz. Monadic second order definable relations on the binary tree. J. Symbolic Logic 52 (1987) 219-226. | MR 877871 | Zbl 0628.03005

[8] A. Muchnik. Definable criterion for definability in presburger arithmentic and its application (1991). Preprint in russian. | MR 1937730

[9] P. Péladeau. Logically defined subsets of ℕ k . Theoret. Comput. Sci. 93 (1992) 169-193. | MR 1146191 | Zbl 0747.03017

[10] J.-E. Pin. Varieties of formal languages. Plenum Publishing Co., New-York (1986). (Traduction de Variétés de langages formels.) | MR 912694 | Zbl 0632.68069

[11] J. Sakarovitch. Eléments de théorie des automates. Vuibert Informatique (2003).

[12] A. Schrijver. Theory of Linear and Integer Programming. John Wiley & sons (1998). | MR 874114 | Zbl 0665.90063

[13] C. Smoryński. Logical Number Theory I: An Introduction. Springer Verlag (1991). | MR 1106853 | Zbl 0759.03002