On the Computational Complexity of Program Scheme Equivalence

DOI10.1137/0209031MaRDI QIDQ3893301zbMATH OpenOpenAlexFDO

Authors H. B. III Hunt, Robert Constable, Sartaj Sahni

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)

Cited in

(14)

• Average case completeness
• Using DNA to solve the bounded Post correspondence problem
• An improvement on Valiant's decision procedure for equivalence of deterministic finite turn pushdown machines
• Many bounded versions of undecidable problems are \textsf{NP}-hard
• On the computational complexity of dynamic slicing problems for program schemas
• Some simplified undecidable and NP-hard problems for simple programs
• On the complexity of simple arithmetic expressions
• Decidability of strong equivalence for subschemas of a class of linear, free, near-liberal program schemas
• On the zero-inequivalence problem for loop programs
• A note on the complexity of program evaluation
• Characterizing minimal semantics-preserving slices of predicate-linear, free, liberal program schemas
• 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

This page was built for publication: On the Computational Complexity of Program Scheme Equivalence

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3893301)