Publication result detail

Tree-Controlled Grammars with Restrictions Placed upon Cuts and Paths

KOUTNÝ, J.; MEDUNA, A.

Original Title

Tree-Controlled Grammars with Restrictions Placed upon Cuts and Paths

English Title

Tree-Controlled Grammars with Restrictions Placed upon Cuts and Paths

Type

Scopus Article

Original 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 adi- tional restriction does not affect the generative power of these grammars.

English 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 adi- tional restriction does not affect the generative power of these grammars.

Keywords

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

Key words in English

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

Authors

KOUTNÝ, J.; MEDUNA, A.

RIV year

2013

Released

08.02.2012

ISBN

0023-5954

Periodical

KYBERNETIKA

Volume

48

Number

1

State

Czech Republic

Pages from

165

Pages to

175

Pages count

11

URL

http://www.kybernetika.cz/content/2012/1/165

BibTex

@article{BUT91444,
  author="Jiří {Koutný} and Alexandr {Meduna}",
  title="Tree-Controlled Grammars with Restrictions Placed upon Cuts and Paths",
  journal="KYBERNETIKA",
  year="2012",
  volume="48",
  number="1",
  pages="165--175",
  issn="0023-5954",
  url="http://www.kybernetika.cz/content/2012/1/165"
}