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

Christian Choffrut

RAIRO - Theoretical Informatics and Applications (2008)

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

Abstract

top
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.

How to cite

top

Choffrut, 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
  1. O. Carton, C. Choffrut and S. Grigorieff. Decision problems for rational relations. RAIRO-Theor. Inf. Appl.40 (2006) 255–275.  Zbl1112.03008
  2. C. Choffrut and M. Goldwurm. Timed automata with periodic clock constraints. J. Algebra Lang. Comput.5 (2000) 371–404.  Zbl0964.68076
  3. S. Eilenberg. Automata, Languages and Machines, volume A. Academic Press (1974).  Zbl0317.94045
  4. S. Eilenberg and M.-P. Schützenbeger. Rational sets in commutative monoids. J. Algebra13 (1969) 173–191.  Zbl0206.02703
  5. S. Ginsburg and E.H. Spanier. Bounded regular sets. Proc. Amer. Math. Soc. 17 (1966) 1043–1049.  Zbl0147.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 Logic52 (1987) 219–226.  Zbl0628.03005
  8. A. Muchnik. Definable criterion for definability in presburger arithmentic and its application (1991). Preprint in russian.  
  9. P. Péladeau. Logically defined subsets of k . Theoret. Comput. Sci.93 (1992) 169–193.  Zbl0747.03017
  10. J.-E. Pin. Varieties of formal languages. Plenum Publishing Co., New-York (1986). (Traduction de Variétés de langages formels.)  
  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).  Zbl0970.90052
  13. C. Smoryński. Logical Number Theory I: An Introduction. Springer Verlag (1991).  Zbl0759.03002

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.