Publication detail

Combined Leftmost Derivations in Matrix Grammars

MEDUNA, A., ŠKRKAL, O.

Original Title

Combined Leftmost Derivations in Matrix Grammars

Type

conference paper

Language

English

Original Abstract

It is an open problem, whether matrix grammars with erasing productions using leftmost derivation of type three generate the whole family of recursively enumerable languages. This paper proves that matrix grammars that apply one matrix using leftmost derivation of type one and all other matrices using leftmost derivation of type three generate the family of recursively enumerable languages.

Keywords

Formal language theory, regulated rewriting, matrix grammar, canonical derivation, generative power.

Authors

MEDUNA, A., ŠKRKAL, O.

RIV year

2004

Released

19. 4. 2004

Location

Ostrava

ISBN

80-85988-99-2

Book

Proceedings of 7th International Conference ISIM'04 Information Systems Implementation and Modelling

Edition

1st edition

Pages from

127

Pages to

132

Pages count

6

BibTex

@inproceedings{BUT17119,
  author="Alexandr {Meduna} and Oto {Škrkal}",
  title="Combined Leftmost Derivations in Matrix Grammars",
  booktitle="Proceedings of 7th International Conference ISIM'04 Information Systems Implementation and Modelling",
  year="2004",
  series="1st edition",
  pages="127--132",
  address="Ostrava",
  isbn="80-85988-99-2"
}