Routes and Products of Monoids

• Autorzy: Mateescu A. , Freund R.
• Języki publikacji: EN

Abstrakty

EN

We investigate the problem of finding monoids that recognize languages of the form L1\JoinTL2 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.

Słowa kluczowe

EN

monoid; route; Schützenberger product; shuffle

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2006
• Tom: Vol. 73, nr 1-2
• Strony: 205--211
• Opis fizyczny: bibliogr. 12 poz.

Twórcy

autor

Mateescu A.

autor

Freund R.

• Technische Universität Wien, Institut für Computersprachen Favoritenstr.9, A-1040 Vienna, Austria,

Bibliografia

• [1] T. Harju, A. Mateescu, A. Salomaa: Shuffle on trajectories: a simplified approach to the Schützenberger product and related operations on families of languages. In Mathematical Foundations of Computer Sciences, MFCS'98, Brno, Czech Republic, August 1998 (L. Brim, J. Gruska, J. Zlatuska, eds.), LNCS 1450, Springer-Verlag, Berlin, 1998, 503-511.
• [2] L. Kari: On Insertion and Deletion in Formal Languages. PhD Thesis, University of Turku, Turku, Finland, 1991.
• [3] J. Kececioglu, D. Gusfield: Reconstructing a history of recombinations from a set of sequences. Proc. of the 5-th ACM-SIAM Symposium on Discrete Algorithms, 1994, 471-480.
• [4] A. Mateescu: Splicing on routes: a framework of DNA computation. In UnconventionalModels of Computation, UMC'98, Auckland, New Zealand (C.S. Calude, J. Casti, M.J. Dinneen, eds.), Springer-Verlag, London, 1998, 273-285.
• [5] A. Mateescu, G. Rozenberg, A. Salomaa: Shuffle on trajectories: syntactic constraints (fundamental study). Theoretical Computer Science, 197 (1998), 1-56.
• [6] A. Mateescu, Gh. P˘aun, G. Rozenberg, A. Salomaa: Simple splicing systems. Discrete Applied Mathematics, 84 (1998), 145-163.
• [7] V. Mitrana: On the interdependence between schuffle and crossing-over operations. Acta Informatica, 34 (1997), 257-266.
• [8] Gh. Pǎun, G. Rozenberg, A. Salomaa: Computing by splicing. Theoretical Computer Science, 168 (1996), 321-336.
• [9] J.E. Pin: Varieties of Formal Languages. North Oxford Academic, 1986.
• [10] J.E. Pin: Syntactic semigroups. In [11], 679-746.
• [11] G. Rozenberg, A. Salomaa, eds.: Handbook of Formal Languages, 3 vols. Springer-Verlag, Berlin, 1997.
• [12] M.P. Schützenberger: On finite monoids having only trivial subgroups. Information and Control, 8 (1965), 190-194.