On the Computational Complexity of Program Scheme Equivalence
From MaRDI portal
Publication:3893301
DOI10.1137/0209031zbMath0447.68038OpenAlexW1963980186MaRDI QIDQ3893301
Robert L. Constable, Sartaj K. Sahni, Harry B. III Hunt
Publication date: 1980
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0209031
Analysis of algorithms and problem complexity (68Q25) Specification and verification (program logics, model checking, etc.) (68Q60)
Related Items
Decidability of strong equivalence for subschemas of a class of linear, free, near-liberal program schemas, Some simplified undecidable and NP-hard problems for simple programs, On the complexity of simple arithmetic expressions, Characterizing minimal semantics-preserving slices of predicate-linear, free, liberal program schemas, On the zero-inequivalence problem for loop programs, Average case completeness, A note on the complexity of program evaluation, An improvement on Valiant's decision procedure for equivalence of deterministic finite turn pushdown machines, On the computational complexity of dynamic slicing problems for program schemas, Using DNA to solve the bounded Post correspondence problem, The complexity of monadic recursion schemes: executability problems, nesting depth, and applications, The complexity of monadic recursion schemes: Exponential time bounds, Weak equivalence in a class of structured program schemes
