On the complexity of linear arithmetic with divisibility
From MaRDI portal
Publication:4635845
DOI10.1109/LICS.2015.67zbMATH Open1401.03070MaRDI QIDQ4635845FDOQ4635845
Authors: 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)
Recommendations
Analysis of algorithms and problem complexity (68Q25) Decidability of theories and sets of sentences (03B25) First-order arithmetic and fragments (03F30) Complexity of computation (including implicit computational complexity) (03D15)
Cited In (16)
- A proof of Bel'tyukov-Lipshitz theorem by quasi-quantifier elimination. I: Definitions and GCD-lemma
- Title not available (Why is that?)
- The complexity of divisibility
- Automated verification of functional correctness of race-free GPU programs
- On the complexity of algebraic numbers, and the bit-complexity of straight-line programs1
- Quadratic word equations with length constraints, counter systems, and Presburger arithmetic with divisibility
- Title not available (Why is that?)
- The complexity of almost linear diophantine problems
- Foundations of Software Science and Computational Structures
- A proof of Bel'tyukov-Lipshitz theorem by quasi-quantifier elimination. II: The main reduction
- Identity testing for radical expressions
- NP-complete problems for systems of linear polynomial's values divisibilities
- Positive existential Definability with unit, addition and coprimeness
- NP-completeness conditions for consistency verification of some types of systems of linear Diophantine dis-equations
- On parametric timed automata and one-counter machines
- Complete divisibility problems for slowly utilized oracles
This page was built for publication: On the complexity of linear arithmetic with divisibility
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4635845)
