Publication result detail

Homogeneous Multicontinuous Grammars and Their Reduction

MEDUNA, A.; LUKÁŠ, R.; FIALA, J.

Original Title

Homogeneous Multicontinuous Grammars and Their Reduction

English Title

Homogeneous Multicontinuous Grammars and Their Reduction

Type

Paper in proceedings outside WoS and Scopus

Original 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.

English 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.

Keywords

multicontinuous grammars, homogeneous grammars, descriptional complexity

Key words in English

multicontinuous grammars, homogeneous grammars, descriptional complexity

Authors

MEDUNA, A.; LUKÁŠ, R.; FIALA, J.

Released

26.10.2007

Publisher

Ing. Zdeněk Novotný, CSc.

Location

Znojmo

ISBN

978-80-7355-077-6

Book

MEMICS 2007 Proceedings

Pages from

90

Pages to

96

Pages count

7

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"
}