One-variable logic meets Presburger arithmetic

DOI10.1016/j.tcs.2019.09.028zbMath1454.03038arXiv1810.10899OpenAlexW2975157560WikidataQ127218853 ScholiaQ127218853MaRDI QIDQ2007734

Bartosz Bednarczyk

Publication date: 22 November 2019

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1810.10899

zbMATH Keywords

computational complexitydecidabilityfinite satisfiabilityclassical decision problemarithmetics

Mathematics Subject Classification ID

Logic in computer science (03B70) Decidability of theories and sets of sentences (03B25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (1)

Presburger Büchi tree automata with applications to logics with expressive counting

Cites Work

• Small solutions of linear diophantine equations
• Undecidability results on two-variable logics
• A new description logic with set constraints and cardinality constraints on role successors
• Complexity of modal logics with Presburger constraints
• Reasoning with Global Assumptions in Arithmetic Modal Logics
• Complexity of the Guarded Two-variable Fragment with Counting Quantifiers
• Towards Efficient Satisfiability Checking for Boolean Algebra with Presburger Arithmetic
• The Support of Integer Optimal Solutions
• Complexity Results for First-Order Two-Variable Logic with Counting
• On the Computational Complexity of the Numerically Definite Syllogistic and Related Logics

This page was built for publication: One-variable logic meets Presburger arithmetic