Contextual Grammars with Subregular Choice

Issue title: Contagious Creativity – In Honor of the 80th Birthday of Professor Solomon Marcus

Article type: Research Article

Authors: Dassow, Jürgen

Affiliations: Otto-von-Guericke-Universität Magdeburg, Fakultät für Informatik, PSF 4120, D-39016 Magdeburg, Germany. dassow@iws.cs.uni-magdeburg.de

Note: [] Address for correspondence: Otto-von-Guericke-Universität Magdeburg, Fakultät für Informatik, PSF 4120, D-39016 Magdeburg, Germany

Abstract: We discuss external contextual grammars with choice where the choice language belongs to a family of subregular languages. We determine the hierarchy of language families of contextual languages which is obtained by the use of nilpotent, combinational, definite, regular suffix closed, and regular commutative languages as choice languages.

Keywords: Contextual grammars, controlled derivations, subregular languages

Journal: Fundamenta Informaticae, vol. 64, no. 1-4, pp. 109-118, 2005