Publication result detail

The Leftmost Derivation of Type Two in Matrix Grammars

ŠKRKAL, O.

Original Title

The Leftmost Derivation of Type Two in Matrix Grammars

English Title

The Leftmost Derivation of Type Two in Matrix Grammars

Type

Paper in proceedings outside WoS and Scopus

Original 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.

English 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.

Keywords

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

Key words in English

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

Authors

ŠKRKAL, O.

RIV year

2011

Released

28.04.2003

Publisher

Marq software s.r.o.

Location

Ostrava

ISBN

80-85988-84-4

Book

Proceedings of 6th International Conference ISIM'03 Information System Implementation and Modeling

Pages from

195

Pages to

199

Pages count

5

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