Kybernetika 48 no. 1, 165-175, 2012

Tree-controlled grammars with restrictions placed upon cuts and paths

Jiří Koutný and Alexander Meduna

Abstract:

First, this paper discusses tree-controlled grammars with root-to-leaf derivation-tree paths restricted by control languages. It demonstrates that if the control languages are regular, these grammars generate the family of context-free languages. Then, in a similar way, the paper introduces tree-controlled grammars with derivation-tree cuts restricted by control languages. It proves that if the cuts are restricted by regular languages, these grammars generate the family of recursively enumerable languages. In addition, it places a binary-relation-based restriction upon these grammars and demonstrate that this additional restriction does not affect the generative power of these grammars.

Keywords:

cuts, context-free grammars, tree-controlled grammars, restricted derivation trees, paths, language families

Classification:

68Q42

paper.pdf

References:

  1. A. V. Aho and J. D. Ullman: The theory of parsing, translation, and compiling. Prentice-Hall, Inc., Upper Saddle River, NJ, USA, 1972.   CrossRef
  2. A. Bondy: Graph Theory. Springer, 2010.   CrossRef
  3. K. Čulik and H. A. Maurer: Tree controlled grammars. Computing 19 (1977), 129-139.   CrossRef
  4. J. Dassow and Gh. P\u{a}un: Regulated Rewriting in Formal Language Theory. Springer, Berlin 1989.   CrossRef
  5. J. Dassow and B. Truthe: Subregularly tree controlled grammars and languages. In: Automata and Formal Languages - 12th Int. Conference AFL 2008, Proceedings (E. Csuhaj-Varjú, Z. Ésik, eds.), Balatonfüred, Hungary 2008, pp. 158-169.   CrossRef
  6. S. Marcus, C. Mart{\'i}n-Vide, V. Mitrana and Gh. P{\u{a}}un: A new-old class of linguistically motivated regulated grammars. In: Computational Linguistics in the Netherlands 2000, Selected Papers from the Eleventh clin Meeting (W. Daelemans, K. Sima'an, J. Veenstra, J. Zavrel, eds.), Rodopi, Amsterdam 2001, pp. 111-125.   CrossRef
  7. C. Martín-Vide and V. Mitrana: Further properties of path-controlled grammars. In: Proceedings of FG-MoL 2005, The 10th Conference on Formal Grammar and The 9th Meeting on Mathematics of Language, Edinburgh 2005, pp. 221-232.   CrossRef
  8. A. Meduna: Automata and Languages: Theory and Applications. Springer Verlag, 2005.   CrossRef
  9. Gh. P{\u{a}}un: On the generative capacity of tree controlled grammars. Computing 21 (1979), 3, 213-220.   CrossRef