Algebraic, Linear and Rational Languages Defined by Mix Operation

Article type: Research Article

Authors: Kudlek, Manfred | Mateescu, Alexandru^;

Affiliations: Fachbereich Informatik, Universität Hamburg, Hamburg, Germany. [email protected] | Faculty of Mathematics, University of Bucharest, Romania | Turku Centre for Computer Science, Turku, Finland. [email protected]

Abstract: We consider operations between languages, based on splitting the underlying alphabet into two disjoint sets, one of them having some priority. Such operations are generalizations of the classical catenation or shuffle operation, with which rational, linear and algebraic languages can be defined similar to the classical case. The basic properties of the corresponding language families are investigated too.

Keywords: Rational, Linear, Algebraic, Mix operation, Language classes

DOI: 10.3233/FI-1998-33303

Journal: Fundamenta Informaticae, vol. 33, no. 3, pp. 249-264, 1998