A1 Refereed original research article in a scientific journal
Shuffle on trajectories: The Schutzenberger product and related operations
Authors: Harju T, Mateescu A, Salomaa A
Publication year: 1998
Journal:: Lecture Notes in Computer Science
Journal name in source: MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 1998
Journal acronym: LECT NOTES COMPUT SC
Volume: 1450
First page : 503
Last page: 511
Number of pages: 9
ISBN: 3-540-64827-5
ISSN: 0302-9743
Abstract
We investigate the problem of finding monoids that recognize languages of the form L-1 (sic)T L-2, where T is an arbitrary set of trajectories. Thereby, we describe two such methods: one based on the so-called trajectories monoids and the other based on monoids of matrices. Many well-known operations such as catenation, bi-catenation, shuffle, literal shuffle and insertion are just particular instances of the operation (sic)(T). Hence, our results offer a uniform treatment for classical methods, notably the Schutzenberger product. We also investigate some other related operations.
We investigate the problem of finding monoids that recognize languages of the form L-1 (sic)T L-2, where T is an arbitrary set of trajectories. Thereby, we describe two such methods: one based on the so-called trajectories monoids and the other based on monoids of matrices. Many well-known operations such as catenation, bi-catenation, shuffle, literal shuffle and insertion are just particular instances of the operation (sic)(T). Hence, our results offer a uniform treatment for classical methods, notably the Schutzenberger product. We also investigate some other related operations.
UTU Research Portal