Detail publikace

Pumping Properties of Path-Restricted Tree-Controlled Languages

KOUTNÝ, J. KŘIVKA, Z. MEDUNA, A.

Originální název

Pumping Properties of Path-Restricted Tree-Controlled Languages

Anglický název

Pumping Properties of Path-Restricted Tree-Controlled Languages

Jazyk

en

Originální abstrakt

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.

Anglický abstrakt

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.

Dokumenty

BibTex 


@inproceedings{BUT76416,
  author="Jiří {Koutný} and Zbyněk {Křivka} and Alexandr {Meduna}",
  title="Pumping Properties of Path-Restricted Tree-Controlled Languages",
  annote="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.",
  address="Brno University of Technology",
  booktitle="7th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science",
  chapter="76416",
  edition="NEUVEDEN",
  howpublished="print",
  institution="Brno University of Technology",
  year="2011",
  month="october",
  pages="61--69",
  publisher="Brno University of Technology",
  type="conference paper"
}