Publication Details

Two-Way Metalinear PC Grammar Systems and Their Descriptional Complexity

MEDUNA, A. Two-Way Metalinear PC Grammar Systems and Their Descriptional Complexity. Acta Cybernetica, 2004, vol. 2004, no. 16, p. 385-397. ISSN: 0324-721X.

Czech title

Dvousměrné metalineární PC gramatické systémy.

Type

journal article

Language

English

Authors

Meduna Alexandr, prof. RNDr., CSc. (DIFS)

Keywords

two-way metalinear PC grammar systems

Abstract

A discussion of two-way metalinear PC grammar systems and their descriptional complexity.

Annotation

Besides a derivation step and a communication step, a two-way PC grammar sytem 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, \Gamma, with two metalinear componets in a very economical way. Indeed, \Gamma's master has only three nonterminals and one communication production; furthermore, it produces all sentential forms with no more than two occurances of nonterminals. In addition, during every computation, \Gamma makes a single communication step. Some variants of two-way PC grammar systems are discussed in the conclusion of the paper.

Published

2004

Pages

385–397

Journal

Acta Cybernetica, vol. 2004, no. 16, ISSN 0324-721X

Book

Acta Informatica

Publisher

Szegedi Tudomanyegyetem

Place

Szeged

BibTeX

@article{BUT42297,
  author="Alexandr {Meduna}",
  title="Two-Way Metalinear PC Grammar Systems and Their Descriptional Complexity",
  journal="Acta Cybernetica",
  year="2004",
  volume="2004",
  number="16",
  pages="385--397",
  issn="0324-721X"
}