Detail výsledku
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: Marq software s.r.o., 2003. p. 195-199. ISBN: 80-85988-84-4.
Typ
článek ve sborníku konference
Jazyk
anglicky
Autoři
Škrkal Oto, Ing.
Abstrakt
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.
Klíčová slova
Formal language theory, regulated rewriting, matrix grammars, canonical derivations, complexity reduction.
Rok
2003
Strany
195–199
Sborník
Proceedings of 6th International Conference ISIM'03 Information System Implementation and Modeling
Konference
MOSIS 2003 - Modelling and Simulation of Systems
ISBN
80-85988-84-4
Vydavatel
Marq software s.r.o.
Místo
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",
publisher="Marq software s.r.o.",
address="Ostrava",
isbn="80-85988-84-4"
}
Pracoviště
Ústav informačních systémů
(UIFS)