| Title:
|
Tree-controlled grammars with restrictions placed upon cuts and paths (English) |
| Author:
|
Koutný, Jiří |
| Author:
|
Meduna, Alexander |
| Language:
|
English |
| Journal:
|
Kybernetika |
| ISSN:
|
0023-5954 |
| Volume:
|
48 |
| Issue:
|
1 |
| Year:
|
2012 |
| Pages:
|
165-175 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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. (English) |
| Keyword:
|
context-free grammars |
| Keyword:
|
tree-controlled grammars |
| Keyword:
|
restricted derivation trees |
| Keyword:
|
paths |
| Keyword:
|
cuts |
| Keyword:
|
language families |
| MSC:
|
68Q42 |
| idZBL:
|
Zbl 1260.68195 |
| idMR:
|
MR2932934 |
| . |
| Date available:
|
2012-03-05T08:37:43Z |
| Last updated:
|
2013-09-22 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/142069 |
| . |
| Reference:
|
[1] A. V. Aho, J. D. Ullman: The theory of parsing, translation, and compiling..Prentice-Hall, Inc., Upper Saddle River, NJ, USA, 1972. MR 0408321 |
| Reference:
|
[2] A. Bondy: Graph Theory..Springer, 2010. |
| Reference:
|
[3] K. Čulik, H. A. Maurer: Tree controlled grammars..Computing 19 (1977), 129-139. Zbl 0363.68108, MR 0464718, 10.1007/BF02252350 |
| Reference:
|
[4] J. Dassow, Gh. Păun: Regulated Rewriting in Formal Language Theory..Springer, Berlin 1989. MR 1067543 |
| Reference:
|
[5] J. Dassow, 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. |
| Reference:
|
[6] S. Marcus, C. Martín-Vide, V. Mitrana, Gh. Pă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. MR 1869435 |
| Reference:
|
[7] C. Martín-Vide, 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. MR 2153679 |
| Reference:
|
[8] A. Meduna: Automata and Languages: Theory and Applications..Springer Verlag, 2005. MR 1778364 |
| Reference:
|
[9] Gh. Păun: On the generative capacity of tree controlled grammars..Computing 21 (1979), 3, 213–220. Zbl 0392.68060, MR 0620209, 10.1007/BF02253054 |
| . |
