Publication Details

Combined Leftmost Derivations in Matrix Grammars

MEDUNA, A.; ŠKRKAL, O. Combined Leftmost Derivations in Matrix Grammars. 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

Conference

7th International Conference on Information Systems Implementation and Modelling, Rožnov pod Radhošťem, CZ

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