Detail publikace

Tree-controlled Grammars with Restrictions Placed upon Cuts and Paths

Originální název

Tree-controlled Grammars with Restrictions Placed upon Cuts and Paths

Anglický název

Tree-controlled Grammars with Restrictions Placed upon Cuts and Paths

Jazyk

en

Originální abstrakt

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.

Anglický abstrakt

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.

BibTex


@article{BUT91444,
  author="Jiří {Koutný} and Alexandr {Meduna}",
  title="Tree-controlled Grammars with Restrictions Placed upon Cuts and Paths",
  annote="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.",
  address="NEUVEDEN",
  chapter="91444",
  edition="NEUVEDEN",
  howpublished="print",
  institution="NEUVEDEN",
  number="1",
  volume="48",
  year="2012",
  month="february",
  pages="165--175",
  publisher="NEUVEDEN",
  type="journal article in Scopus"
}