On context-free rewriting with a simple restriction and its computational completeness
Tomáš Masopust; Alexander Meduna
RAIRO - Theoretical Informatics and Applications (2009)
- Volume: 43, Issue: 2, page 365-378
- ISSN: 0988-3754
Access Full Article
top
Abstract
topHow to cite
topMasopust, Tomáš, and Meduna, Alexander. "On context-free rewriting with a simple restriction and its computational completeness." RAIRO - Theoretical Informatics and Applications 43.2 (2009): 365-378. <http://eudml.org/doc/250577>.
@article{Masopust2009,
abstract = {
This paper discusses context-free rewriting systems in which there exist two disjoint finite sets of rules, and a symbol, referred to as a condition of applicability, is attached to each rule in either of these two sets. In one set, a rule with a symbol attached to it is applicable if the attached symbol occurs in the current rewritten string while in the other set, such a rule is applicable if the attached symbol does not occur there. The present paper demonstrates that these rewriting systems are computationally complete. From this main result, the paper derives several consequences and solves several open problems.
},
author = {Masopust, Tomáš, Meduna, Alexander},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Formal languages; context-free grammar; context-free rewriting system; derivation restriction; generative power.; formal languages; generative power},
language = {eng},
month = {3},
number = {2},
pages = {365-378},
publisher = {EDP Sciences},
title = {On context-free rewriting with a simple restriction and its computational completeness},
url = {http://eudml.org/doc/250577},
volume = {43},
year = {2009},
}
TY - JOUR
AU - Masopust, Tomáš
AU - Meduna, Alexander
TI - On context-free rewriting with a simple restriction and its computational completeness
JO - RAIRO - Theoretical Informatics and Applications
DA - 2009/3//
PB - EDP Sciences
VL - 43
IS - 2
SP - 365
EP - 378
AB -
This paper discusses context-free rewriting systems in which there exist two disjoint finite sets of rules, and a symbol, referred to as a condition of applicability, is attached to each rule in either of these two sets. In one set, a rule with a symbol attached to it is applicable if the attached symbol occurs in the current rewritten string while in the other set, such a rule is applicable if the attached symbol does not occur there. The present paper demonstrates that these rewriting systems are computationally complete. From this main result, the paper derives several consequences and solves several open problems.
LA - eng
KW - Formal languages; context-free grammar; context-free rewriting system; derivation restriction; generative power.; formal languages; generative power
UR - http://eudml.org/doc/250577
ER -
References
top- J. Dassow and G. Păun, Regulated Rewriting in Formal Language Theory. Springer-Verlag, Berlin (1989).
- O. Mayer, Some restrictive devices for context-free grammars. Inform. Control20 (1972) 69–92.
- A. Meduna and A. Gopalaratnam, On semi-conditional grammars with productions having either forbidding or permitting conditions. Acta Cybernetica11 (1994) 307–324.
- A. Meduna and M. Švec, Grammars with Context Conditions and Their Applications. John Wiley & Sons, New York (2005).
- G. Păun, A variant of random context grammars: Semi-conditional grammars. Theoret. Comput. Sci.41 (1985) 1–17.
- A. Salomaa, Formal languages. Academic Press, New York (1973).
- A.P.J. van der Walt, Random context grammars, in Proceedings of the Symposium on Formal Languages (1970).
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.