On the complexity of simple arithmetic expressions

DOI10.1016/0304-3975(82)90012-3zbMath0479.68050OpenAlexW2079232283MaRDI QIDQ1162150

Oscar H. Ibarra, Brian S. Leininger, Shlomo Moran

Publication date: 1982

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

Full work available at URL: https://doi.org/10.1016/0304-3975(82)90012-3

zbMATH Keywords

decidabilityNP-completepolynomial timeequivalence problembounded inequivalence problemscomplexity of inequivalence

Mathematics Subject Classification ID

Related Items (2)

On the complexity of commutativity analysis ⋮ On the zero-inequivalence problem for loop programs

Cites Work

• NP-complete decision problems for binary quadratics
• On the Computational Complexity of Program Scheme Equivalence
• The Complexity of the Equivalence Problem for Simple Loop-Free Programs
• Complexity of automaton identification from given data
• The Equivalence Problem of Simple Programs
• The complexity of theorem-proving procedures
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the complexity of simple arithmetic expressions