Powered by OpenAIRE graph
Found an issue? Give us feedback
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/ Journal of Computer ...arrow_drop_down
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
Journal of Computer and System Sciences
Article
License: Elsevier Non-Commercial
Data sources: UnpayWall
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
Journal of Computer and System Sciences
Article . 2012
License: Elsevier Non-Commercial
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao
Journal of Computer and System Sciences
Article . 2012 . Peer-reviewed
License: Elsevier Non-Commercial
Data sources: Crossref
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao
zbMATH Open
Article . 2012
Data sources: zbMATH Open
https://doi.org/10.1007/978-3-...
Part of book or chapter of book . 2010 . Peer-reviewed
Data sources: Crossref
DBLP
Conference object
Data sources: DBLP
DBLP
Article
Data sources: DBLP
versions View all 10 versions
addClaim

On Restricted Context-Free Grammars

On restricted context-free grammars
Authors: Jürgen Dassow; Tomás Masopust;

On Restricted Context-Free Grammars

Abstract

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.

Country
Czech Republic
Keywords

regulated rewriting, Computer Networks and Communications, Applied Mathematics, Formal languages and automata, Normal forms, context-free rules, Theoretical Computer Science, Computational Theory and Mathematics, Derivation restriction, Grammars and rewriting systems, normal forms, context-free grammars, Generative power, Context-free grammars, derivation restriction, generative power

  • BIP!
    Impact byBIP!
    selected citations
    These citations are derived from selected sources.
    This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    10
    popularity
    This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
    Average
    influence
    This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    Top 10%
    impulse
    This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
    Average
Powered by OpenAIRE graph
Found an issue? Give us feedback
selected citations
These citations are derived from selected sources.
This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Citations provided by BIP!
popularity
This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
BIP!Popularity provided by BIP!
influence
This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Influence provided by BIP!
impulse
This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
BIP!Impulse provided by BIP!
10
Average
Top 10%
Average
hybrid