Publication detail

Two-Way Linear PC Grammar Systems and Their Descriptional Complexity

KALÁB, P.

Original Title

Two-Way Linear PC Grammar Systems and Their Descriptional Complexity

Type

conference paper

Language

English

Original Abstract

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.

Keywords

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

Authors

KALÁB, P.

RIV year

2005

Released

14. 5. 2005

Publisher

Publishing house of Brno University of Technology VUTIUM

Location

Brno

ISBN

80-214-2890-2

Book

Proceedings of the 11th Conference Student EEICT 2005

Edition

Volume 3

Pages from

546

Pages to

550

Pages count

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