On the complexity of linear arithmetic with divisibility

DOI10.1109/LICS.2015.67MaRDI QIDQ4635845zbMATH OpenFDO

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)

Mathematics Subject Classification ID

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)

Recommendations

• Foundations of Software Science and Computational Structures
• Complexity of Subcases of Presburger Arithmetic
• Approaching arithmetic theories with finite-state automata
• The complexity of linear problems in fields
• On Presburger arithmetic extended with modulo counting quantifiers

Cited in

(16)

• A proof of Bel'tyukov-Lipshitz theorem by quasi-quantifier elimination. I: Definitions and GCD-lemma
• scientific article; zbMATH DE number 7315090 (Why is no real title available?)
• The complexity of divisibility
• Automated verification of functional correctness of race-free GPU programs
• Quadratic word equations with length constraints, counter systems, and Presburger arithmetic with divisibility
• On the complexity of algebraic numbers, and the bit-complexity of straight-line programs1
• scientific article; zbMATH DE number 1254004 (Why is no real title available?)
• 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
• On parametric timed automata and one-counter machines
• NP-completeness conditions for consistency verification of some types of systems of linear Diophantine dis-equations
• 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)