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

Abstract

top
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.

How to cite

top

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

NotesEmbed ?

top

You 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.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.