Browse wiki
From International Center for Computational Logic
Context-free grammars are widely used for … Context-free grammars are widely used for the simple form of their rules. A derivation step consists of the choice of a nonterminal of the sentential form and of an application of a rule rewriting it. Several regulations of the derivation process have been studied to increase the power of context-free grammars. In the resulting grammars, however, not only the symbols to be rewritten are restricted, but also the rules to be applied. In this paper, we study context-free grammars with a simpler restriction where only symbols to be rewritten are restricted, not the rules, in the sense that any rule rewriting the chosen nonterminal can be applied. We prove that these grammars have the same power as random context, matrix, or programmed grammars. We also present two improved normal forms and discuss the characterization of context-sensitive languages by a variant using strings of length at most two instead of symbols. of length at most two instead of symbols. +
Tomáš Masopust + and Jürgen Dassow +
@article{DM2012,
author = {J{\"{u}}rgen Dassow and Tom{\'{a}}{\v{s}} Masopust},
title = {On restricted context-free grammars},
journal = {Journal of Computer and System Sciences},
volume = {78},
number = {1},
year = {2012},
pages = {293{\textendash}304},
doi = {10.1016/j.jcss.2011.05.008}
}
author = {J{\"{u}}rgen Dassow and Tom{\'{a}}{\v{s}} Masopust},
title = {On restricted context-free grammars},
journal = {Journal of Computer and System Sciences},
volume = {78},
number = {1},
year = {2012},
pages = {293{\textendash}304},
doi = {10.1016/j.jcss.2011.05.008}
}
Dassow +
Jürgen +
Jürgen Dassow, Tomáš Masopust<br/> ' … Jürgen Dassow, Tomáš Masopust<br/> '''[[Article3003|On restricted context-free grammars]]''' <br/>__NOTOC__Journal of Computer and System Sciences, 78(1):293–304, 2012<br/><span class="fas fa-chevron-right" style="font-size: 85%;" ></span> [[Article3003|Details]] <span class="fas fa-chevron-right" style="font-size: 85%; margin-left: 2ex; "></span> [[Media:On restricted context-free grammars.pdf|Download]]On restricted context-free grammars.pdf|Download]] +
Jürgen Dassow, Tomáš Masopust<br/> ' … Jürgen Dassow, Tomáš Masopust<br/> '''[[Article3003/en|On restricted context-free grammars]]''' <br/>__NOTOC__Journal of Computer and System Sciences, 78(1):293–304, 2012<br/><span class="fas fa-chevron-right" style="font-size: 85%;" ></span> [[Article3003|Details]] <span class="fas fa-chevron-right" style="font-size: 85%; margin-left: 2ex;" ></span> [[Media:On restricted context-free grammars.pdf|Download]]On restricted context-free grammars.pdf|Download]] +
Display title of"Display title of" is a predefined property that can assign a distinct display title to an entity and is provided by <a rel="nofollow" class="external text" href="https://www.semantic-mediawiki.org/wiki/Help:Special_properties">Semantic MediaWiki</a>.
On restricted context-free grammars +
Modification date"Zuletzt geändert <span style="font-size:small;">(Modification date)</span>" is a predefined property that corresponds to the date of the last modification of a subject and is provided by <a rel="nofollow" class="external text" href="https://www.semantic-mediawiki.org/wiki/Help:Special_properties">Semantic MediaWiki</a>.
24. Mai 2016, 16:00:51 +
Has query"Hat Abfrage <span style="font-size:small;">(Has query)</span>" is a predefined property that represents meta information (in form of a <a rel="nofollow" class="external text" href="https://www.semantic-mediawiki.org/wiki/Subobject">subobject</a>) about individual queries and is provided by <a rel="nofollow" class="external text" href="https://www.semantic-mediawiki.org/wiki/Help:Special_properties">Semantic MediaWiki</a>.
