On restricted context-free grammars (Q414885): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(6 intermediate revisions by 5 users not shown) | |||
Property / author | |||
Property / author: Juergen Dassow / rank | |||
Property / author | |||
Property / author: Juergen Dassow / rank | |||
Normal rank | |||
Property / review text | |||
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. | |||
Property / review text: 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. / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Andreas Maletti / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 68Q42 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 68Q45 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 6033496 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
context-free grammars | |||
Property / zbMATH Keywords: context-free grammars / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
derivation restriction | |||
Property / zbMATH Keywords: derivation restriction / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
normal forms | |||
Property / zbMATH Keywords: normal forms / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
generative power | |||
Property / zbMATH Keywords: generative power / 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 | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 05: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
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
0 references