Publication Details

The Leftmost Derivation of Type Two in Matrix Grammars

ŠKRKAL, O. The Leftmost Derivation of Type Two in Matrix Grammars. Proceedings of 6th International Conference ISIM'03 Information System Implementation and Modeling. Ostrava: 2003. p. 195-199. ISBN: 80-85988-84-4.
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 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
195–199
Proceedings
Proceedings of 6th International Conference ISIM'03 Information System Implementation and Modeling
ISBN
80-85988-84-4
Place
Ostrava
BibTeX 
@inproceedings{BUT13993,
  author="Oto {Škrkal}",
  title="The Leftmost Derivation of Type Two in Matrix Grammars",
  booktitle="Proceedings of 6th International Conference ISIM'03 Information System Implementation and Modeling",
  year="2003",
  pages="195--199",
  address="Ostrava",
  isbn="80-85988-84-4"
}
Back to top