Well-structured program equivalence is highly undecidable

DOI10.1145/2287718.2287726zbMath1351.68073arXiv1103.1433OpenAlexW2054812122MaRDI QIDQ2946675

Marcel Jackson, Robert Goldblatt

Publication date: 17 September 2015

Published in: ACM Transactions on Computational Logic (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1103.1433

zbMATH Keywords

undecidabilityintersectionprogram equivalencePDLdeterministic propositional dynamic logicfixset

Mathematics Subject Classification ID

Undecidability and degrees of sets of sentences (03D35) Logic in computer science (03B70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30)

Related Items (4)

Static analysis of navigational XPath over graph databases ⋮ The algebra of functions with antidomain and range ⋮ On axiomatizations of public announcement logic ⋮ Monoids with tests and the algebra of possibly non-halting programs

This page was built for publication: Well-structured program equivalence is highly undecidable