Publication Details

Two-Way Linear PC Grammar Systems

KALÁB, P. Two-Way Linear PC Grammar Systems. In Proceedings of 8th Spring International Conference ISIM'05 Information Systems Implementation and Modelling. 1st edition. Ostrava: 2005. p. 87-94. ISBN: 80-86840-09-3.

Czech title

Dvousměrné lineární PC gramatické systémy

Type

conference paper

Language

English

Authors

Kaláb Petr, Ing.

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.

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.

Published

2005

Pages

87–94

Proceedings

Proceedings of 8th Spring International Conference ISIM'05 Information Systems Implementation and Modelling

Series

1st edition

ISBN

80-86840-09-3

Place

Ostrava

BibTeX

@inproceedings{BUT21493,
  author="Petr {Kaláb}",
  title="Two-Way Linear PC Grammar Systems",
  booktitle="Proceedings of 8th Spring International Conference ISIM'05 Information Systems Implementation and Modelling",
  year="2005",
  series="1st edition",
  pages="87--94",
  address="Ostrava",
  isbn="80-86840-09-3"
}