Shuffle on trajectories: The Schutzenberger product and related operations



: Harju T, Mateescu A, Salomaa A

: 1998

Lecture Notes in Computer Science

MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 1998

: LECT NOTES COMPUT SC

: 1450

: 503

: 511

: 9

: 3-540-64827-5

: 0302-9743


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.



Last updated on 2025-13-10 at 12:37