On restricted context-free grammars (Q414885): Difference between revisions

From MaRDI portal
Added link to MaRDI item.
ReferenceBot (talk | contribs)
Changed an Item
 
(4 intermediate revisions by 3 users not shown)
Property / author
 
Property / author: Juergen Dassow / rank
Normal rank
 
Property / author
 
Property / author: Juergen Dassow / rank
 
Normal rank
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank
Property / full work available at URL
 
Property / full work available at URL: https://doi.org/10.1016/j.jcss.2011.05.008 / rank
 
Normal rank
Property / OpenAlex ID
 
Property / OpenAlex ID: W1999932874 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5485990 / rank
 
Normal rank
Property / cites work
 
Property / cites work: A pumping lemma for random permitting context languages / rank
 
Normal rank
Property / cites work
 
Property / cites work: A Note on the Generative Power of Some Simple Variants of Context-Free Grammars Regulated by Context Conditions / rank
 
Normal rank
Property / cites work
 
Property / cites work: Simple restriction in context-free rewriting / rank
 
Normal rank
Property / cites work
 
Property / cites work: On context-free rewriting with a simple restriction and its computational completeness / rank
 
Normal rank
Property / cites work
 
Property / cites work: Some restrictive devices for context-free grammars / rank
 
Normal rank
Property / cites work
 
Property / cites work: Grammars with Context Conditions and Their Applications / rank
 
Normal rank
Property / cites work
 
Property / cites work: One-sided and two-sided context in formal grammars / rank
 
Normal rank
Property / cites work
 
Property / cites work: A variant of random context grammars: Semi-conditional grammars / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5626298 / rank
 
Normal rank
Property / cites work
 
Property / cites work: A shrinking lemma for random forbidding context languages / rank
 
Normal rank
Property / cites work
 
Property / cites work: On Erasing Productions in Random Context Grammars / rank
 
Normal rank

Latest revision as of 04:16, 5 July 2024

scientific article
Language Label Description Also known as
English
On restricted context-free grammars
scientific article

    Statements

    On restricted context-free grammars (English)
    0 references
    0 references
    0 references
    11 May 2012
    0 references
    The contribution investigates the generative power of several derivation-restricted context-free grammars. Many derivation restriction mechanisms for context-free grammars have already been studied in the literature, and the current contribution investigates a restriction on the non-terminals that allows/disallows the application of a production depending on the presence/absence of certain symbols in the sentential form. Context-free grammars using such restrictions on the derivations are shown to be equivalent in generative power to random context grammars [\textit{S. Ewert} and \textit{A. van der Walt}, ``The power and limitations of random context'', Top. Comput. Math. 9, 33--43 (2003; Zbl 1102.68619)]. While this equivalence is also true for the permitting variants (in which only the presence of symbols can be required), it remains an open question whether this is also true in the presence of forbidding context. With the equivalence established, the generative power for most classes is presented in some simple hierarchies. The equivalence is also used to derive new normal forms for random context grammars. It is even demonstrated that the obtained normal forms are as simple as possible (in a rather restricted sense). This is achieved by demonstrating that further restrictions to the context indeed limit the generative power. At last, the contribution investigates a minor twist on the previous model. Instead of non-terminals, productions can now force the presence/absence of terminal symbols in the sentential form. The main line of research is repeated for this model (with different arguments) to show that the non-erasing variant of this model characterizes exactly the context-sensitive languages. As before, the equivalence is used to derive a new normal form for this model. The contribution is expertly written and the main points can be understood on the first reading. However, it is very technical in the mathematical development. While the main notions are understandable also to non-expert readers, I would recommend an introduction to regulated rewriting or derivation-restricted context-free grammars to non-expert readers. On the positive side, the contribution re-uses its results efficiently, which is enjoyable to read and allows the reader to focus on the actual differences.
    0 references
    context-free grammars
    0 references
    derivation restriction
    0 references
    normal forms
    0 references
    generative power
    0 references

    Identifiers