Publication result 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

English Title

Two-Way Linear PC Grammar Systems and Their Descriptional Complexity

Type

Paper in proceedings outside WoS and Scopus

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.

English 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

Key words in English

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.

Released

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