No label defined (Q3330494)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 3862425
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 3862425

      Statements

      0 references
      0 references
      1984
      0 references
      regular languages
      0 references
      context-free languages
      0 references
      propositional dynamic logics
      0 references
      [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.
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references