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

DOI10.1051/ita:2007047zbMath1158.03007OpenAlexW2085137086MaRDI QIDQ3514638

Christian Choffrut

Publication date: 21 July 2008

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/92855

zbMATH Keywords

first-order logicdecidabilityPresburger arithmetic

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Classical first-order logic (03B10) Decidability of theories and sets of sentences (03B25)

Related Items (1)

On the open problem of Ginsburg concerning semilinear sets and related problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Logically defined subsets of \(\mathbb{N}{}^ k\)
• Logical number theory I. An introduction
• Rational sets in commutative monoids
• Decision problems among the main subfamilies of rational relations
• Monadic second order definable relations on the binary tree
• Bounded Regular Sets

This page was built for publication: Deciding whether a relation defined in Presburger logic can be defined in weaker logics