Detail publikace

The Left-Most Derivation of Type Two in Matrix Grammars

ŠKRKAL, O.

Originální název

The Left-Most Derivation of Type Two in Matrix Grammars

Typ

článek ve sborníku ve WoS nebo Scopus

Jazyk

angličtina

Originální abstrakt

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.

Klíčová slova

Formal language theory, regulated rewriting, matrix grammars, canonical derivations, complexity reduction.

Autoři

ŠKRKAL, O.

Rok RIV

2003

Vydáno

24. 4. 2003

Nakladatel

Faculty of Electrical Engineering and Communication BUT

Místo

Brno

ISBN

80-214-2379-X

Kniha

Proceedings of 9th Conference and Competition Student EEICT 2003

Strany od

566

Strany do

570

Strany počet

5

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"
}