Publication detail

Two-Way Metalinear PC Grammar Systems and Their Descriptional Complexity

MEDUNA, A.

Original Title

Two-Way Metalinear PC Grammar Systems and Their Descriptional Complexity

English Title

Two-Way Metalinear PC Grammar Systems and Their Descriptional Complexity

Type

journal article - other

Language

en

Original Abstract

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.

English abstract

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.

Keywords

two-way metalinear PC grammar systems

RIV year

2003

Released

26.02.2004

Publisher

Szegedi Tudomanyegyetem

Location

Szeged

ISBN

0324-721X

Periodical

Acta Cybernetica

Year of study

2004

Number

16

State

US

Pages from

385

Pages to

397

Pages count

12

Documents

BibTex


@article{BUT42297,
  author="Alexandr {Meduna}",
  title="Two-Way Metalinear PC Grammar Systems and Their Descriptional Complexity",
  annote="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.",
  address="Szegedi Tudomanyegyetem",
  booktitle="Acta Informatica",
  chapter="42297",
  institution="Szegedi Tudomanyegyetem",
  journal="Acta Cybernetica",
  number="16",
  volume="2004",
  year="2004",
  month="february",
  pages="385--397",
  publisher="Szegedi Tudomanyegyetem",
  type="journal article - other"
}