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 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
195–199
Proceedings
Proceedings of 6th International Conference ISIM'03 Information System Implementation and Modeling
Conference
MOSIS 2003 - Modelling and Simulation of Systems, Brno, CZ
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