On the zero-inequivalence problem for loop programs

DOI10.1016/0022-0000(83)90020-XzbMath0498.68030OpenAlexW1974546986MaRDI QIDQ1171383

Brian S. Leininger, Oscar H. Ibarra

Publication date: 1983

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(83)90020-x

zbMATH Keywords

decision problemsNP-completenesssimple classes of loop programs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Theory of software (68N99)

Related Items

On the complexity of commutativity analysis

Cites Work

• Unnamed Item
• Unnamed Item
• Some simplified undecidable and NP-hard problems for simple programs
• On the complexity of simple arithmetic expressions
• On the Computational Complexity of Program Scheme Equivalence
• The Complexity of the Equivalence Problem for Simple Programs
• Complexity of automaton identification from given data
• A Complete and Consistent Hoare Axiomatics for a Simple Programming Language
• Reduction of an arbitrary diophantine equation to one in 13 unknowns
• The Equivalence Problem of Simple Programs
• The complexity of theorem-proving procedures