# 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

top## How 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). Zbl0697.68067
- O. Mayer, Some restrictive devices for context-free grammars. Inform. Control20 (1972) 69–92. Zbl0248.68035
- A. Meduna and A. Gopalaratnam, On semi-conditional grammars with productions having either forbidding or permitting conditions. Acta Cybernetica11 (1994) 307–324. Zbl0938.68680
- A. Meduna and M. Švec, Grammars with Context Conditions and Their Applications. John Wiley & Sons, New York (2005). Zbl1087.68045
- G. Păun, A variant of random context grammars: Semi-conditional grammars. Theoret. Comput. Sci.41 (1985) 1–17. Zbl0587.68071
- A. Salomaa, Formal languages. Academic Press, New York (1973). Zbl0262.68025
- A.P.J. van der Walt, Random context grammars, in Proceedings of the Symposium on Formal Languages (1970). Zbl0221.68047

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.