Publication detail

The Left-Most Derivation of Type Two in Matrix Grammars

ŠKRKAL, O.

Original Title

The Left-Most Derivation of Type Two in Matrix Grammars

English Title

The Left-Most Derivation of Type Two in Matrix Grammars

Type

conference paper

Language

en

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

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

Keywords

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

RIV year

2003

Released

24.04.2003

Publisher

Faculty of Electrical Engineering and Communication BUT

Location

Brno

ISBN

80-214-2379-X

Book

Proceedings of 9th Conference and Competition Student EEICT 2003

Pages from

566

Pages to

570

Pages count

5

Documents

BibTex


@inproceedings{BUT13992,
  author="Oto {Škrkal}",
  title="The Left-Most Derivation of Type Two in Matrix Grammars",
  annote="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.",
  address="Faculty of Electrical Engineering and Communication BUT",
  booktitle="Proceedings of 9th Conference and Competition Student EEICT 2003",
  chapter="13992",
  institution="Faculty of Electrical Engineering and Communication BUT",
  year="2003",
  month="april",
  pages="566--570",
  publisher="Faculty of Electrical Engineering and Communication BUT",
  type="conference paper"
}