Publication detail

Two-way PC Grammar Systems Based on Regular Grammars

KALÁB, P.

Original Title

Two-way PC Grammar Systems Based on Regular Grammars

Type

article in a collection out of WoS and Scopus

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 three 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. Some variants of two-way PC grammar system are discussed in the conclusion of this paper.

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

2004

Released

21. 4. 2004

Location

Ostrava

ISBN

80-85988-99-2

Book

Proceedings of 7th International Conference ISIM'04 Information Systems Implementation and Modeling

Edition

1st edition

Pages from

111

Pages to

118

Pages count

8

BibTex

@inproceedings{BUT16915,
  author="Petr {Kaláb}",
  title="Two-way PC Grammar Systems Based on Regular Grammars",
  booktitle="Proceedings of 7th International Conference ISIM'04  Information Systems Implementation and Modeling",
  year="2004",
  series="1st edition",
  pages="111--118",
  address="Ostrava",
  isbn="80-85988-99-2"
}