Well structured program equivalence is highly undecidable

Details Well structured program equivalence is highly undecidable Well structured program equivalence is highly undecidable

2011-03-08

arxiv.org/abs/1103.1433v1

Computer Science

Logic in Computer Science

8 pages

Scientific paper

We show that strict deterministic propositional dynamic logic with intersection is highly undecidable, solving a problem in the Stanford Encyclopedia of Philosophy. In fact we show something quite a bit stronger. We introduce the construction of program equivalence, which returns the value $\mathsf{T}$ precisely when two given programs are equivalent on halting computations. We show that virtually any variant of propositional dynamic logic has $\Pi_1^1$-hard validity problem if it can express even just the equivalence of well-structured programs with the empty program \texttt{skip}. We also show, in these cases, that the set of propositional statements valid over finite models is not recursively enumerable, so there is not even an axiomatisation for finitely valid propositions.

Affiliated with

Also associated with

No associations

Rating

Well structured program equivalence is highly undecidable does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Well structured program equivalence is highly undecidable, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Well structured program equivalence is highly undecidable will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-81983