scientific article; zbMATH DE number 3862425
[For the entire collection see Zbl 0533.00026.] It is well-known in formal language theory that all properties of regular languages are decidable but some significant properties of context-free languages in general fail to be decidable. The transition from regular propositional dynamic logics (PDLs) to context-free ones is more drastic, since some simple context-free augmentations on regular PDLs force the validity problem to be \(\Pi^ 1_ 1\) undecidable as has been shown by \textit{D. Harel}, \textit{A. Pnueli} and \textit{J. Stavi} [J. Comput. Syst. Sci. 26, 222-243 (1983)]. However some restricted context-free languages are known to enjoy many decidable properties (e.g., the equivalence problem to LL(k)), and the main purpose of this paper is to find out a similar situation in context-PDLs. Indeed it is shown that a regular PDL augmented by a single context-free language \(\{A^ iB^ i:\quad i\geq 0\}\) is decidable. This system gives also a significant example of a PDL system which is decidable but fails to enjoy the so-called finite model property.
- Problems concerning fairness and temporal logic for conflict-free Petri nets
- Propositional dynamic logic with recursive programs
- Deciding Properties of Nonregular Programs
- Regular dynamic logic is not interpretable in deterministic context-free dynamic logic
- scientific article; zbMATH DE number 7317262 (Why is no real title available?)
- scientific article; zbMATH DE number 7713505 (Why is no real title available?)
- Beyond \(\mathcal{ALC}_{\textsf{reg}} \): exploring non-regular extensions of PDL with description logics features
- Exploring non-regular extensions of propositional dynamic logic with description-logics features
- Propositional dynamic logic of nonregular programs
- Undecidability of PDL with \(L=\{a^{2^ i}| i\geq 0\}\)
- Propositional dynamic logic of context-free programs and fixpoint logic with chop
- A note on an extension of PDL
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3330494)