Detail výsledku

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.
Typ
článek ve sborníku konference
Jazyk
anglicky
Autoři
Škrkal Oto, Ing., FIT (FIT)
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
566–570
Sborník
Proceedings of 9th Conference and Competition Student EEICT 2003
Konference
STUDENT EEICT 2003
ISBN
80-214-2379-X
Vydavatel
Faculty of Electrical Engineering and Communication BUT
Místo
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"
}
Pracoviště
Ústav informačních systémů (UIFS)
Nahoru