Detail publikace

Two-Way Linear PC Grammar Systems and Their Descriptional Complexity

KALÁB, P.

Originální název

Two-Way Linear PC Grammar Systems and Their Descriptional Complexity

Typ

článek ve sborníku ve WoS nebo Scopus

Jazyk

angličtina

Originální abstrakt

Besides derivation and communication steps, a two-way PC grammar system can make a reduction step during which it reduces the right-hand side of a context-free production to its left hand-side. This paper proves that every non-unary recursively enumerable language is defined by a centralized two-way grammar system, Γ, with five components in a very economical way. Indeed, Γ's master has only three nonterminals and one communication production; furthermore, it produces all sentential forms with no more than two occurrences of nonterminals. In addition, during every computation, Γ makes a single communication step.

Klíčová slova

Context-free grammar, left-linear grammar, right-linear grammar, grammar system, communication step, two-way PC grammar systems, derivation, production, sentential form, nonterminal, terminal

Autoři

KALÁB, P.

Rok RIV

2005

Vydáno

14. 5. 2005

Nakladatel

Publishing house of Brno University of Technology VUTIUM

Místo

Brno

ISBN

80-214-2890-2

Kniha

Proceedings of the 11th Conference Student EEICT 2005

Edice

Volume 3

Strany od

546

Strany do

550

Strany počet

5

BibTex

@inproceedings{BUT21492,
  author="Petr {Kaláb}",
  title="Two-Way Linear PC Grammar Systems and Their Descriptional Complexity",
  booktitle="Proceedings of the 11th Conference Student EEICT 2005",
  year="2005",
  series="Volume 3",
  pages="546--550",
  publisher="Publishing house of Brno University of Technology VUTIUM",
  address="Brno",
  isbn="80-214-2890-2"
}