Abstract
Morphisms of trace monoids are studied in the paper. Their relations to morphisms of free monoids are described. Injective trace morphisms are investigated and decidability of injectivity is proved for morphisms of abelian trace monoids. An effective general characterization of trace morphisms preserving regularity (recognizability) is given.
Preview
Unable to display preview. Download preview PDF.
References
IJ.J. Aalbersberg & G. Rozenberg — Theory of Traces — University of Leiden, Report 86-16 (1986)
J. Berstel — Transductions and Context-Free Languages — Teubner Studienbucher Informatik, Stuttgart (1979)
P. Cartier & D. Foata — Problèmes Combinatoires de Commutation et Réarrangements — Lecture Notes in Mathematics 85 (1969)
R. Cori — Partially Abelian Monoids — Université de Bordeaux I, R.G. 1.86 (1986)
R. Cori & Y. Métivier — Recognizable Subsets of Some Partially Abelian Monoids — Theoretical Computer Science 35 (1985)
R. Cori & D. Perrin — Automates et Commutations Partielles — RAIRO Informatique Théorique et Application 19 (1985)
C. Duboc — Some Properties of Commutation in F-P-C Monoids — Information Processing Letters 20 (1985)
C. Duboc — Equations in Free Partially Commutative Monoids — Lecture Notes in Computer Science 210 (1986)
G. Lallement — Semigroups and Combinatorial applications — Wiley & Sons, New York (1979)
A. Mazurkiewicz — Concurrent Program Schemes and Their Interpretations — Aarhus University, DAIMI-PB-78 (1977)
A. Mazurkiewicz — Trace Theory — Lecture Notes in Computer Science 255 (1987)
Y. Métivier — On Recognizable Subsets of Free Partially Abelian Monoids — Lecture Notes in Computer Science 226 (1986)
E. Ochmanski — Regular Behaviour of Concurrent Systems — Bulletin of EATCS 27 (1985)
D. Perrin — Words — Combinatorics on Words by M. Lothaire, Addison-Wesley (1983)
W. Zielonka — Notes on Finite Asynchronous Automata — RAIRO Informatique théorique et Applications 21 (1987)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1988 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ochmanski, E. (1988). On morphisms of trace monoids. In: Cori, R., Wirsing, M. (eds) STACS 88. STACS 1988. Lecture Notes in Computer Science, vol 294. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0035858
Download citation
DOI: https://doi.org/10.1007/BFb0035858
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-18834-6
Online ISBN: 978-3-540-48190-4
eBook Packages: Springer Book Archive