Publication detail

Pumping Properties of Path-Restricted Tree-Controlled Languages

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

Original Title

Pumping Properties of Path-Restricted Tree-Controlled Languages

English Title

Pumping Properties of Path-Restricted Tree-Controlled Languages

Type

conference paper

Language

en

Original Abstract

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.

English abstract

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.

Keywords

regulated rewriting, derivation tree,tree-controlled grammars,path-controlled grammars,$n$-path tree-controlled grammars,pumping properties.

RIV year

2011

Released

14.10.2011

Publisher

Brno University of Technology

Location

Brno

ISBN

978-80-214-4305-1

Book

7th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science

Edition

NEUVEDEN

Edition number

NEUVEDEN

Pages from

61

Pages to

69

Pages count

9

Documents

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"
}