Publication Details

Combined Leftmost Derivations in Matrix Grammars

MEDUNA, A.; ŠKRKAL, O. Combined Leftmost Derivations in Matrix Grammars. Proceedings of 7th International Conference ISIM'04 Information Systems Implementation and Modelling. 1st edition. Ostrava: 2004. p. 127-132. ISBN: 80-85988-99-2.
Czech title
Kombinované levé derivace v maticových gramatikách
Type
conference paper
Language
English
Authors
Meduna Alexandr, prof. RNDr., CSc. (DIFS)
Škrkal Oto, Ing.
Keywords

Formal language theory, regulated rewriting, matrix grammar, canonical derivation, generative power.

Abstract

It is an open problem, whether matrix grammars with erasing productions using leftmost derivation of type three generate the whole family of recursively enumerable languages. This paper proves that matrix grammars that apply one matrix using leftmost derivation of type one and all other matrices using leftmost derivation of type three generate the family of recursively enumerable languages.

Published
2004
Pages
127–132
Proceedings
Proceedings of 7th International Conference ISIM'04 Information Systems Implementation and Modelling
Series
1st edition
ISBN
80-85988-99-2
Place
Ostrava
BibTeX 
@inproceedings{BUT17119,
  author="Alexandr {Meduna} and Oto {Škrkal}",
  title="Combined Leftmost Derivations in Matrix Grammars",
  booktitle="Proceedings of 7th International Conference ISIM'04 Information Systems Implementation and Modelling",
  year="2004",
  series="1st edition",
  pages="127--132",
  address="Ostrava",
  isbn="80-85988-99-2"
}
Back to top