The Complexity of the Equivalence Problem for Simple Programs
From MaRDI portal
Publication:3912019
DOI10.1145/322261.322270zbMath0462.68023MaRDI QIDQ3912019
Eitan M. Gurari, Oscar H. Ibarra
Publication date: 1981
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/322261.322270
NP-complete; polynomial time; counter machines; polynomial space; Presburger formulas; simple programming languages
68Q25: Analysis of algorithms and problem complexity
68Q60: Specification and verification (program logics, model checking, etc.)
68Q65: Abstract data types; algebraic specification
Related Items
On the Decidability of the Equivalence Problem for Monadic Recursive Programs, ON THE EDGE OF DECIDABILITY IN COMPLEXITY ANALYSIS OF LOOP PROGRAMS, Simple programming languages and restricted classes of Turing machines, Some simplified undecidable and NP-hard problems for simple programs, On the zero-inequivalence problem for loop programs, A note on the complexity of program evaluation