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
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (7)
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
This page was built for publication: The Complexity of the Equivalence Problem for Simple Programs
