Conference paper

 
Koutný, J., Křivka, Z., Meduna, A.: Pumping Properties of Path-Restricted Tree-Controlled Languages, In: 7th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science, Brno, CZ, VUT v Brně, 2011, p. 61-69, ISBN 978-80-214-4305-1
Publication language:english
Original title:Pumping Properties of Path-Restricted Tree-Controlled Languages
Title (cs):Lemmata o vkládání pro cestou řízené gramatiky
Pages:61-69
Proceedings:7th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science
Conference:MEMICS'11 -- 7th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science
Place:Brno, CZ
Year:2011
ISBN:978-80-214-4305-1
Publisher:Brno University of Technology
Keywords
regulated rewriting, 
derivation tree,
tree-controlled grammars,
path-controlled grammars,
$n$-path tree-controlled grammars,
pumping properties.
Annotation
This paper discusses new kind of a restriction placed on tree-controlled grammars-context-free grammars with some root-to-leaf paths in their derivation trees restricted by a control language. We introduce an n-path restriction and demonstrate that if the control language is linear, there are several families of generated languages depending on the length of common part of restricted paths. Then, the paper introduces several pumping properties of these families.
BibTeX:
@INPROCEEDINGS{
   author = {Jiří Koutný and Zbyněk Křivka and Alexander Meduna},
   title = {Pumping Properties of Path-Restricted Tree-Controlled
	Languages},
   pages = {61--69},
   booktitle = {7th Doctoral Workshop on Mathematical and Engineering
	Methods in Computer Science},
   year = {2011},
   location = {Brno, CZ},
   publisher = {Brno University of Technology},
   ISBN = {978-80-214-4305-1},
   language = {english},
   url = {http://www.fit.vutbr.cz/research/view_pub.php?id=9698}
}