Subclasses of presburger arithmetic and the weak EXP hierarchy

DOI10.1145/2603088.2603092zbMath1394.68153arXiv1401.5266OpenAlexW3102787008WikidataQ56059271 ScholiaQ56059271MaRDI QIDQ4635632

Christoph Haase

Publication date: 23 April 2018

Published in: Proceedings of the Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) (Search for Journal in Brave)

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

zbMATH Keywords

Presburger arithmeticcontext-free commutative grammarsultimately periodic setsbounded quantifier alternationweak EXP hierarchy

Mathematics Subject Classification ID

First-order arithmetic and fragments (03F30) Grammars and rewriting systems (68Q42) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (9)

Equivalence between model-checking flat counter systems and Presburger arithmetic ⋮ Context-free commutative grammars with integer counters and resets ⋮ Unnamed Item ⋮ Presburger Arithmetic, Rational Generating Functions, and Quasi-Polynomials ⋮ Feferman-vaught decompositions for prefix classes of first order logic ⋮ State-based opacity of labeled real-time automata ⋮ On Presburger arithmetic extended with non-unary counting quantifiers ⋮ A decision procedure for string constraints with string/integer conversion and flat regular constraints ⋮ Monadic decomposition in integer linear arithmetic

This page was built for publication: Subclasses of presburger arithmetic and the weak EXP hierarchy