The Complexity of the Equivalence Problem for Simple Programs
From MaRDI portal
Publication:3912019
DOI10.1145/322261.322270zbMath0462.68023OpenAlexW1985456258MaRDI 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-completepolynomial timecounter machinespolynomial spacePresburger formulassimple programming languages
Analysis of algorithms and problem complexity (68Q25) Specification and verification (program logics, model checking, etc.) (68Q60) Abstract data types; algebraic specification (68Q65)
Related Items
On the complexity of commutativity analysis, 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, ON THE EDGE OF DECIDABILITY IN COMPLEXITY ANALYSIS OF LOOP PROGRAMS, Simple programming languages and restricted classes of Turing machines, On the Decidability of the Equivalence Problem for Monadic Recursive Programs