Publication Details

The Left-Most Derivation of Type Two in Matrix Grammars

ŠKRKAL, O. The Left-Most Derivation of Type Two in Matrix Grammars. Proceedings of 9th Conference and Competition Student EEICT 2003. Brno: Faculty of Electrical Engineering and Communication BUT, 2003. p. 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.
Keywords

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

Abstract

This contribution discusses the descriptional complexity of matrixgrammars using left-most derivation of type two with respect to thenumber of nonterminals and matrices with two or more productions. Itproves that these matrix grammars need only nine nonterminals and sixmatrices of length two or more to generate recursively enumerablelanguages.

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
BibTeX 
@inproceedings{BUT13992,
  author="Oto {Škrkal}",
  title="The Left-Most Derivation of Type Two in Matrix Grammars",
  booktitle="Proceedings of 9th Conference and Competition Student EEICT 2003",
  year="2003",
  pages="566--570",
  publisher="Faculty of Electrical Engineering and Communication BUT",
  address="Brno",
  isbn="80-214-2379-X"
}
Back to top