On the complexity of simple arithmetic expressions

DOI10.1016/0304-3975(82)90012-3MaRDI QIDQ1162150zbMATH OpenOpenAlexFDO

Authors 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

Analysis of algorithms and problem complexity (68Q25)

Cites work

• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3723859 (Why is no real title available?)
• scientific article; zbMATH DE number 3197115 (Why is no real title available?)
• Complexity of automaton identification from given data
• 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
• The Equivalence Problem of Simple Programs
• The complexity of theorem-proving procedures

Cited in

(2)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1162150)