Publication Details

Simple-Semi-Conditional Versions of Matrix Grammars with a Reduced Regulating Mechanism

KOPEČEK Tomáš and MEDUNA Alexander. Simple-Semi-Conditional Versions of Matrix Grammars with a Reduced Regulating Mechanism. Computing and Informatics, vol. 2004, no. 23, pp. 287-302. ISSN 1335-9150.

Czech title

Jednoduché polopodmínkové verze maticových gramatik s omezeným regulačním mechanizmem

Type

journal article

Language

english

Authors

Kopeček Tomáš, Ing. (DIFS FIT BUT)
Meduna Alexander, prof. RNDr., CSc. (DIFS FIT BUT)

Keywords

descriptional complexity, matrix grammars, simple-semi-conditional grammars

Abstract

This paper discusses some conditional versions of matrix grammars. It establishes several characterizations of the family of the recursively enumerable languages based on these grammars. In fact, making use of the Geffert Normal forms, the present paper demonstrates these characterizations based on matrix grammars with conditions of a limited length, a reduced number of nonterminals, and a reduced number and size of matrices.

Published

2004

Pages

287-302

Journal

Computing and Informatics, vol. 2004, no. 23, ISSN 1335-9150

Publisher

Slovak Academic Press

BibTeX

@ARTICLE{FITPUB7603,
   author = "Tom\'{a}\v{s} Kope\v{c}ek and Alexander Meduna",
   title = "Simple-Semi-Conditional Versions of Matrix Grammars with a Reduced Regulating Mechanism",
   pages = "287--302",
   journal = "Computing and Informatics",
   volume = 2004,
   number = 23,
   year = 2004,
   ISSN = "1335-9150",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/7603"
}