Deciding whether a relation defined in Presburger logic can be defined in weaker logics

Choffrut, Christian

doi:10.1051/ita:2007047

Choffrut, Christian

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 42 (2008) no. 1, pp. 121-135.

Résumé

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.

MR Zbl

DOI : 10.1051/ita:2007047

Classification : 03B10, 68Q70
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/

Bibliographie
Cité par

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

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

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

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

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

[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 | Zbl

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

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

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

[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 | Zbl

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

Cité par Sources :