Separation of Test-Free Propositional Dynamic Logics over Context-Free Languages

Details Separation of Test-Free Propositional Dynamic Logics over Context-Free Languages Separation of Test-Free Propositional Dynamic Logics over Context-Free Languages

2011-06-07

arxiv.org/abs/1106.1242v1

EPTCS 54, 2011, pp. 207-221

Computer Science

Logic in Computer Science

In Proceedings GandALF 2011, arXiv:1106.0814

Scientific paper

10.4204/EPTCS.54.15

For a class L of languages let PDL[L] be an extension of Propositional Dynamic Logic which allows programs to be in a language of L rather than just to be regular. If L contains a non-regular language, PDL[L] can express non-regular properties, in contrast to pure PDL. For regular, visibly pushdown and deterministic context-free languages, the separation of the respective PDLs can be proven by automata-theoretic techniques. However, these techniques introduce non-determinism on the automata side. As non-determinism is also the difference between DCFL and CFL, these techniques seem to be inappropriate to separate PDL[DCFL] from PDL[CFL]. Nevertheless, this separation is shown but for programs without test operators.

Affiliated with

Also associated with

No associations

Rating

Separation of Test-Free Propositional Dynamic Logics over Context-Free Languages 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 Separation of Test-Free Propositional Dynamic Logics over Context-Free Languages, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Separation of Test-Free Propositional Dynamic Logics over Context-Free Languages will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-26176