Publication Details

Homogeneous Multicontinuous Grammars and Their Reduction

MEDUNA, A.; LUKÁŠ, R.; FIALA, J. Homogeneous Multicontinuous Grammars and Their Reduction. MEMICS 2007 Proceedings. Znojmo: Ing. Zdeněk Novotný, CSc., 2007. p. 90-96. ISBN: 978-80-7355-077-6.

Czech title

Homogenní rozšířené multigramatiky a jejich redukce

Type

conference paper

Language

English

Authors

Meduna Alexandr, prof. RNDr., CSc. (DIFS)
Lukáš Roman, Ing., Ph.D.
Fiala Jiří, Ing.

Keywords

multicontinuous grammars, homogeneous grammars, descriptional complexity

Abstract

This paper discusses homogeneous multicontinuous grammars in which each selector has all its activated parts identical. It is demonstrated that every recursive enumerable language is generated by a homogeneous five-nonterminal multicontinuous grammar that has no more than five selectors and each of these selectors contains no more than two activated parts.

Published

2007

Pages

90–96

Proceedings

MEMICS 2007 Proceedings

ISBN

978-80-7355-077-6

Publisher

Ing. Zdeněk Novotný, CSc.

Place

Znojmo

BibTeX

@inproceedings{BUT26073,
  author="Alexandr {Meduna} and Roman {Lukáš} and Jiří {Fiala}",
  title="Homogeneous Multicontinuous Grammars and Their Reduction",
  booktitle="MEMICS 2007 Proceedings",
  year="2007",
  pages="90--96",
  publisher="Ing. Zdeněk Novotný, CSc.",
  address="Znojmo",
  isbn="978-80-7355-077-6"
}