Publication Details

Combined Leftmost Derivations in Matrix Grammars

MEDUNA Alexander and ŠKRKAL Oto. Combined Leftmost Derivations in Matrix Grammars. In: Proceedings of 7th International Conference ISIM'04 Information Systems Implementation and Modelling. 1st edition. Ostrava, 2004, pp. 127-132. ISBN 80-85988-99-2.
Czech title
Kombinované levé derivace v maticových gramatikách
Type
conference paper
Language
english
Authors
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
Conference
7th International Conference on Information Systems Implementation and Modelling, Rožnov pod Radhošťem, CZ
ISBN
80-85988-99-2
Place
Ostrava, CZ
BibTeX
@INPROCEEDINGS{FITPUB7468,
   author = "Alexander Meduna and Oto \v{S}krkal",
   title = "Combined Leftmost Derivations in Matrix Grammars",
   pages = "127--132",
   booktitle = "Proceedings of 7th International Conference ISIM'04 Information Systems Implementation and Modelling",
   series = "1st edition",
   year = 2004,
   location = "Ostrava, CZ",
   ISBN = "80-85988-99-2",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/7468"
}
Back to top