Publication Details

Two-Way Linear PC Grammar Systems

KALÁB Petr. Two-Way Linear PC Grammar Systems. In: Proceedings of 8th Spring International Conference ISIM'05 Information Systems Implementation and Modelling. 1st edition. Ostrava, 2005, pp. 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. (DIFS FIT BUT)
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
Conference
8th International Conference on Information Systems Implementation and Modelling, Hradec nad Moravicí, CZ
ISBN
80-86840-09-3
Place
Ostrava, CZ
BibTeX 
@INPROCEEDINGS{FITPUB7774,
   author = "Petr Kal\'{a}b",
   title = "Two-Way Linear PC Grammar Systems",
   pages = "87--94",
   booktitle = "Proceedings of 8th Spring International Conference ISIM'05 Information Systems Implementation and Modelling",
   series = "1st edition",
   year = 2005,
   location = "Ostrava, CZ",
   ISBN = "80-86840-09-3",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/7774"
}
Back to top