Publication Details

The Left-Most Derivation of Type Two in Matrix Grammars

ŠKRKAL Oto. The Left-Most Derivation of Type Two in Matrix Grammars. In: Proceedings of 9th Conference and Competition Student EEICT 2003. Brno: Faculty of Electrical Engineering and Communication BUT, 2003, pp. 566-570. ISBN 80-214-2379-X.
Czech title
Levá derivace typu dvě v maticových gramatikách
Type
conference paper
Language
english
Authors
Škrkal Oto, Ing. (DIFS FIT BUT)
Keywords

Formal language theory, regulated rewriting, matrix grammars, canonical derivations, complexity reduction.

Abstract

This contribution discusses the descriptional complexity of matrix grammars using left-most derivation of type two with respect to the number of nonterminals and matrices with two or more productions. It proves that these matrix grammars need only nine nonterminals and six matrices of length two or more to generate recursively enumerable languages.

Published
2003
Pages
566-570
Proceedings
Proceedings of 9th Conference and Competition Student EEICT 2003
Conference
STUDENT EEICT 2003, Brno, CZ
ISBN
80-214-2379-X
Publisher
Faculty of Electrical Engineering and Communication BUT
Place
Brno, CZ
BibTeX
@INPROCEEDINGS{FITPUB7200,
   author = "Oto \v{S}krkal",
   title = "The Left-Most Derivation of Type Two in Matrix Grammars",
   pages = "566--570",
   booktitle = "Proceedings of 9th Conference and Competition Student EEICT 2003",
   year = 2003,
   location = "Brno, CZ",
   publisher = "Faculty of Electrical Engineering and Communication BUT",
   ISBN = "80-214-2379-X",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/7200"
}
Back to top