On the Computational Complexity of Program Scheme Equivalence

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

zbMATH Keywords

programming languagesrecursion schemedecidable problemsprogram scheme equivalence

Mathematics Subject Classification ID

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