Techreport4023: Unterschied zwischen den Versionen
Aus International Center for Computational Logic
Tomas Masopust (Diskussion | Beiträge) Keine Bearbeitungszusammenfassung |
Markus Krötzsch (Diskussion | Beiträge) K (Textersetzung - „|Forschungsgruppe=Knowledge Systems“ durch „|Forschungsgruppe=Wissensbasierte Systeme“) |
||
| Zeile 15: | Zeile 15: | ||
|Download=Comparison of Two Context-Free Rewriting Systems with Simple Context-Checking Mechanism.pdf | |Download=Comparison of Two Context-Free Rewriting Systems with Simple Context-Checking Mechanism.pdf | ||
|Link=http://arxiv.org/abs/1004.3635 | |Link=http://arxiv.org/abs/1004.3635 | ||
|Forschungsgruppe= | |Forschungsgruppe=Wissensbasierte Systeme | ||
|DOI=http://arxiv.org/abs/1004.3635 | |DOI=http://arxiv.org/abs/1004.3635 | ||
}} | }} | ||
Aktuelle Version vom 24. Mai 2016, 18:02 Uhr
Comparison of Two Context-Free Rewriting Systems with Simple Context-Checking Mechanisms
Tomáš MasopustTomáš Masopust
Tomáš Masopust
Comparison of Two Context-Free Rewriting Systems with Simple Context-Checking Mechanisms
Technical Report, arXiv.org, volume CoRR abs/1004.3635, April 2010
Comparison of Two Context-Free Rewriting Systems with Simple Context-Checking Mechanisms
Technical Report, arXiv.org, volume CoRR abs/1004.3635, April 2010
- KurzfassungAbstract
This paper solves an open problem concerning the generative power of nonerasing context-free rewriting systems using a simple mechanism for checking for context dependencies, in the literature known as semi-conditional grammars of degree (1,1). In these grammars, two nonterminal symbols are attached to each context-free production, and such a production is applicable if one of the two attached symbols occurs in the current sentential form, while the other does not. Specifically, this paper demonstrates that the family of languages generated by semi-conditional grammars of degree (1,1) coincides with the family of random context languages. In addition, it shows that the normal form proved by Mayer for random context grammars with erasing productions holds for random context grammars without erasing productions, too. It also discusses two possible definitions of the relation of the direct derivation step used in the literature. - Weitere Informationen unter:Further Information: Link
- Forschungsgruppe:Research Group: Wissensbasierte SystemeKnowledge-Based Systems
@techreport{M2010,
author = {Tom{\'{a}}{\v{s}} Masopust},
title = {Comparison of Two Context-Free Rewriting Systems with Simple
Context-Checking Mechanisms},
institution = {arXiv.org},
year = {2010},
month = {April}
}
