Abstract
We prove that a trace monoid embeds into the queue monoid if and only if it embeds into the direct product of two free monoids. We also give a decidable characterization of these trace monoids.
Supported by the DFG-Project “Speichermechanismen als Monoide”, KU 1107/9-1.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
i.e., (u, v, w) is one of the triples \((u',v',w')\), \((v',w',u')\) and \((w',u',v')\).
References
Cori, P., Perrin, D.: Automates et commutations partielles. R.A.I.R.O. Informatique Théorique et Applications 19, 21–32 (1985)
Diekert, V.: Combinatorics on Traces. LNCS, vol. 454. Springer, Heidelberg (1990)
Diekert, V., Muscholl, A., Reinhardt, K.: On codings of traces. In: Mayr, E.W., Puech, C. (eds.) STACS 1995. LNCS, vol. 900. Springer, Heidelberg (1995)
Diekert, V., Rozenberg, G.: The Book of Traces. World Scientific Publ. Co., River Edge (1995)
Kuske, D., Prianychnykova, O.: The trace monoids in the queue monoid and in the direct product of two free monoids. arXiv:1603.07217 (2016)
Huschenbett, M., Kuske, D., Zetzsche, G.: The monoid of queue actions. In: Csuhaj-Varjú, E., Dietzfelbinger, M., Ésik, Z. (eds.) MFCS 2014, Part I. LNCS, vol. 8634, pp. 340–351. Springer, Heidelberg (2014)
Huschenbett, M., Kuske, D., Zetzsche, G.: The monoid of queue actions (2016, submitted)
Kunc, M.: Undecidability of the trace coding problem and some decidable cases. Theor. Comput. Sci. 310(1–3), 393–456 (2004)
Mazurkiewicz, A.: Concurrent program schemes and their interpretation. Technical report, DAIMI Report PB-78, Aarhus University (1977)
Seinsche, D.: On a property of the class of \(n\)-colorable graphs. J. Comb. Theory (B) 16, 191–193 (1974)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kuske, D., Prianychnykova, O. (2016). The Trace Monoids in the Queue Monoid and in the Direct Product of Two Free Monoids. In: Brlek, S., Reutenauer, C. (eds) Developments in Language Theory. DLT 2016. Lecture Notes in Computer Science(), vol 9840. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-53132-7_21
Download citation
DOI: https://doi.org/10.1007/978-3-662-53132-7_21
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-53131-0
Online ISBN: 978-3-662-53132-7
eBook Packages: Computer ScienceComputer Science (R0)