On the Complexity of Linear Arithmetic with Divisibility
From MaRDI portal
Publication:4635845
DOI10.1109/LICS.2015.67zbMath1401.03070MaRDI QIDQ4635845
Antonia Lechner, Joël Ouaknine, James Worrell
Publication date: 23 April 2018
Published in: 2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15) First-order arithmetic and fragments (03F30)
Related Items (8)
NP-complete problems for systems of linear polynomial's values divisibilities ⋮ A proof of Bel'tyukov-Lipshitz theorem by quasi-quantifier elimination. II: The main reduction ⋮ On the complexity of algebraic numbers, and the bit-complexity of straight-line programs1 ⋮ Automated verification of functional correctness of race-free GPU programs ⋮ NP-completeness conditions for consistency verification of some types of systems of linear Diophantine dis-equations ⋮ Unnamed Item ⋮ A proof of Bel'tyukov-Lipshitz theorem by quasi-quantifier elimination. I: Definitions and GCD-lemma ⋮ On parametric timed automata and one-counter machines
This page was built for publication: On the Complexity of Linear Arithmetic with Divisibility
