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
1984
0 references
regular languages
0 references
context-free languages
0 references
propositional dynamic logics
0 references
0.840326189994812
0 references
0.8352125883102417
0 references
0.821672797203064
0 references
0.813231348991394
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