Routes and Products of Monoids

Issue title: SPECIAL ISSUE ON TRAJECTORIES OF LANGUAGE THEORY Dedicated to the memory of Alexandru Mateescu

Article type: Research Article

Authors: Mateescu, Alexandru | Freund, Rudolf

Affiliations: Institut für Computersprachen Technische Universität Wien Favoritenstr. 9, A-1040 Wien, Austria. E-mail: [email protected]

Abstract: We investigate the problem of finding monoids that recognize languages of the form L_1⋈_TL_2 where T is an arbitrary set of routes. We present a uniform method based on routes to find such monoids. Many classical operations from the theory of formal languages, such as catenation, bi-catenation, simple splicing, shuffle, literal shuffle, and insertion are shown to be just particular instances of the operation ⋈_T.

Keywords: Monoid, route, Schützenberger product, shuffle

Journal: Fundamenta Informaticae, vol. 73, no. 1-2, pp. 205-211, 2006