Abstract
We give a decidable necessary and sufficient condition on two semi commutations θ1, θ2 such that the composition of \(f_{\theta _1 }\) and \(f_{\theta _2 }\) is a semi commutation function. This characterization uses the commutation graphs of θ1 and θ2, and the non commutation graphs of θ1 and θ −12 . Then we deduce a decidable graphic characterization of confluent semi commutations.
This work is supported by the P.R.C. Mathématiques et Informatique, and by the EBRA project ALGEBRAIC and SYNTACTIC METHODS in COMPUTER SCIENCE.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
IJ.J. Aabersberg & G. Rozenberg. Theory of Traces. The. Comp. Sci. 60 (1986) 1–83.
J. Berstel & J. Sakarovich. Recents results in the theory of rational sets. Lect. Notes in Comp. Sci. 233 (1986) 15–28.
P.Cartier & D.Foata. Problèmes combinatoires de commutations et réarrangements. Lect. Notes in Math. 85 (1969).
M.Clerbout. Commutations partielles et familles de langages. Thèse Lille, 1984.
M. Clerbout & M. Latteux. Partial commutations and faithful rational transductions. The. Comp. Sci. 34 (1984) 241–254.
M.Clerbout & M.Latteux. On a generalization of partial commutations. in M.Arato, I.Katai, L.varga, eds, Prc.Fourth Hung. Computer Sci.Conf (1985) 15–24.
M. Clerbout & M. Latteux. Semi-commutations. Information and Computation 73 (1987) 59–74.
M. Clerbout. Compositions de fonctions de commutation partielle. RAIRO Inform. Theor. 23 (1986) 395–424.
M. Clerbout, M. Latteux & Y. Roos. Decomposition of partial commutations. ICALP'90 Lect. Notes in Comp. Sci. 443 (1990) 501–511.
M. Clerbout & D. Gonzalez. Decomposition of semi commutations. MFCS'90 Lect. Notes in Comp.Sci. 452 (1990) 209–216.
R. Cori & D. Perrin. Automates et commutations partielles. RAIRO Inform. Theor. 19 (1985) 21–32.
R. Cori. Partially abelian monoids. Invited lecture, STACS, Orsay (1986).
V.Diekert Combinatorics on Traces. Lect. Notes in Comp. Sci. 454 (1990)
V.Diekert, E.Ochmanski & K.Reinhardt. On confluent semi commutation systems — decidability and complexity results. To appear (ICALP'91).
M.Latteux. Rational cones and commutations. Machines, Languages and Complexity. J.Dassow and J.Kelemen eds., Lect. Notes in Comp.Sci. (1989) 37–54.
A.Mazurkiewicz. Concurrent program schemes and their interpretations. DAIMI PB 78, University of Aarhus (1977).
A. Mazurkiewicz. Traces, histories and graphs: instances of process monoids. Lect. Notes in Comp.Sci. 176 (1984) 115–133.
Y. Metivier. On recognizable subsets of free partially commutative monoids. Lect. Notes in Comp.Sci. 226 (1986) 254–264.
E. Ochmanski. Regular behaviour of concurrent systems. Bulletin of EATCS 27 (1985) 56–67.
D. Perrin. Words over a partially commutative alphabet. NATO ASI Series F12, Springer (1985) 329–340.
Y.Roos. Contribution à l'étude des fonctions de commutations partielles. Thèse, Université de Lille (1989).
W. Zielonka. Notes on asynchronous automata. RAIRO Inform. Theor. 21 (1987) 99–135.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1991 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Roos, Y., Wacrenier, P.A. (1991). Composition of two semi commutations. In: Tarlecki, A. (eds) Mathematical Foundations of Computer Science 1991. MFCS 1991. Lecture Notes in Computer Science, vol 520. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-54345-7_84
Download citation
DOI: https://doi.org/10.1007/3-540-54345-7_84
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-54345-9
Online ISBN: 978-3-540-47579-8
eBook Packages: Springer Book Archive