Publication Details

Combined Leftmost Derivations in Matrix Grammars

MEDUNA, A., ŠKRKAL, O. Combined Leftmost Derivations in Matrix Grammars. In Proceedings of 7th International Conference ISIM'04 Information Systems Implementation and Modelling. 1st edition. Ostrava: 2004. p. 127-132. ISBN: 80-85988-99-2.

Czech title

Kombinované levé derivace v maticových gramatikách

Type

conference paper

Language

English

Authors

Meduna Alexandr, prof. RNDr., CSc. (DIFS)
Škrkal Oto, Ing.

Keywords

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

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.

Published

2004

Pages

127–132

Proceedings

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

Series

1st edition

ISBN

80-85988-99-2

Place

Ostrava

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