We consider logics on and which are weaker than Presburger arithmetic and we settle the following decision problem: given a -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.
Mots clés : Presburger arithmetic, first order logic, decidability
@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}, pages = {121--135}, publisher = {EDP-Sciences}, volume = {42}, number = {1}, year = {2008}, doi = {10.1051/ita:2007047}, mrnumber = {2382547}, zbl = {1158.03007}, language = {en}, url = {http://www.numdam.org/articles/10.1051/ita:2007047/} }
TY - JOUR AU - Choffrut, Christian TI - Deciding whether a relation defined in Presburger logic can be defined in weaker logics JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2008 SP - 121 EP - 135 VL - 42 IS - 1 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ita:2007047/ DO - 10.1051/ita:2007047 LA - en ID - ITA_2008__42_1_121_0 ER -
%0 Journal Article %A Choffrut, Christian %T Deciding whether a relation defined in Presburger logic can be defined in weaker logics %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2008 %P 121-135 %V 42 %N 1 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ita:2007047/ %R 10.1051/ita:2007047 %G en %F 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) no. 1, pp. 121-135. doi : 10.1051/ita:2007047. http://www.numdam.org/articles/10.1051/ita:2007047/
[1] Decision problems for rational relations. RAIRO-Theor. Inf. Appl. 40 (2006) 255-275. | Numdam | MR | Zbl
, and .[2] Timed automata with periodic clock constraints. J. Algebra Lang. Comput. 5 (2000) 371-404. | MR | Zbl
and .[3] Automata, Languages and Machines, volume A. Academic Press (1974). | MR | Zbl
.[4] Rational sets in commutative monoids. J. Algebra 13 (1969) 173-191. | MR | Zbl
and .[5] Bounded regular sets. Proc. Amer. Math. Soc. 17 (1966) 1043-1049. | MR | Zbl
and .[6] Complexity results for first-order theories of temporal constraints. KR (1994) 379-390.
.[7] Monadic second order definable relations on the binary tree. J. Symbolic Logic 52 (1987) 219-226. | MR | Zbl
and .[8] Definable criterion for definability in presburger arithmentic and its application (1991). Preprint in russian. | MR
.[9] Logically defined subsets of . Theoret. Comput. Sci. 93 (1992) 169-193. | MR | Zbl
.[10] Varieties of formal languages. Plenum Publishing Co., New-York (1986). (Traduction de Variétés de langages formels.) | MR | Zbl
.[11] Eléments de théorie des automates. Vuibert Informatique (2003).
.[12] Theory of Linear and Integer Programming. John Wiley & sons (1998). | MR | Zbl
.[13] Logical Number Theory I: An Introduction. Springer Verlag (1991). | MR | Zbl
.Cité par Sources :