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

RAIRO - Theoretical Informatics and Applications (2008)

- Volume: 42, Issue: 1, page 121-135
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topChoffrut, Christian. "Deciding whether a relation defined in Presburger logic can be defined in weaker logics." RAIRO - Theoretical Informatics and Applications 42.1 (2008): 121-135. <http://eudml.org/doc/250349>.

@article{Choffrut2008,

abstract = {
We consider logics on
$\mathbb\{Z\}$ and $\mathbb\{N\}$ which are weaker than
Presburger arithmetic and
we settle the following decision
problem: given a k-ary
relation on $\mathbb\{Z\}$ and $\mathbb\{N\}$
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.
},

author = {Choffrut, Christian},

journal = {RAIRO - Theoretical Informatics and Applications},

keywords = {Presburger arithmetic; first order logic; decidability; first-order logic},

language = {eng},

month = {1},

number = {1},

pages = {121-135},

publisher = {EDP Sciences},

title = {Deciding whether a relation defined in Presburger logic can be defined in weaker logics},

url = {http://eudml.org/doc/250349},

volume = {42},

year = {2008},

}

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

DA - 2008/1//

PB - EDP Sciences

VL - 42

IS - 1

SP - 121

EP - 135

AB -
We consider logics on
$\mathbb{Z}$ and $\mathbb{N}$ which are weaker than
Presburger arithmetic and
we settle the following decision
problem: given a k-ary
relation on $\mathbb{Z}$ and $\mathbb{N}$
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.

LA - eng

KW - Presburger arithmetic; first order logic; decidability; first-order logic

UR - http://eudml.org/doc/250349

ER -

## References

top- O. Carton, C. Choffrut and S. Grigorieff. Decision problems for rational relations. RAIRO-Theor. Inf. Appl.40 (2006) 255–275. Zbl1112.03008
- C. Choffrut and M. Goldwurm. Timed automata with periodic clock constraints. J. Algebra Lang. Comput.5 (2000) 371–404. Zbl0964.68076
- S. Eilenberg. Automata, Languages and Machines, volume A. Academic Press (1974). Zbl0317.94045
- S. Eilenberg and M.-P. Schützenbeger. Rational sets in commutative monoids. J. Algebra13 (1969) 173–191. Zbl0206.02703
- S. Ginsburg and E.H. Spanier. Bounded regular sets. Proc. Amer. Math. Soc. 17 (1966) 1043–1049. Zbl0147.25301
- M. Koubarakis. Complexity results for first-order theories of temporal constraints. KR (1994) 379–390.
- H. Läuchli and C. Savioz. Monadic second order definable relations on the binary tree. J. Symbolic Logic52 (1987) 219–226. Zbl0628.03005
- A. Muchnik. Definable criterion for definability in presburger arithmentic and its application (1991). Preprint in russian.
- P. Péladeau. Logically defined subsets of ${\mathbb{N}}^{k}$. Theoret. Comput. Sci.93 (1992) 169–193. Zbl0747.03017
- J.-E. Pin. Varieties of formal languages. Plenum Publishing Co., New-York (1986). (Traduction de Variétés de langages formels.)
- J. Sakarovitch. Eléments de théorie des automates. Vuibert Informatique (2003).
- A. Schrijver. Theory of Linear and Integer Programming. John Wiley & sons (1998). Zbl0970.90052
- C. Smoryński. Logical Number Theory I: An Introduction. Springer Verlag (1991). Zbl0759.03002

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.