Publication Details

The Leftmost Derivation of Type Two in Matrix Grammars

ŠKRKAL Oto. The Leftmost Derivation of Type Two in Matrix Grammars. In: Proceedings of 6th International Conference ISIM'03 Information System Implementation and Modeling. Ostrava, 2003, pp. 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. (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
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, CZ
BibTeX 
@INPROCEEDINGS{FITPUB7201,
   author = "Oto \v{S}krkal",
   title = "The Leftmost Derivation of Type Two in Matrix Grammars",
   pages = "195--199",
   booktitle = "Proceedings of 6th International Conference ISIM'03 Information System Implementation and Modeling",
   year = 2003,
   location = "Ostrava, CZ",
   ISBN = "80-85988-84-4",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/7201"
}
Back to top