Abstract
Many interesting combinatorial problems on words deal with rearrangements of words. One of the goals of such rearrangements is to provide bijective mappings between sets of words satisfying certain properties and therefore give some enumeration results on words. The interested reader may consult the Chapter by D. Foata in Lothaire’s book [11] where some examples of rearrangements are developped. The algorithms involved in such rearrangements are, by the way, close to the more popular ones since many sorting problems can usefully be formulated in terms of rearrangements. The study of rearrangements has lead D. Foata to consider words over an alphabet in which some of the letters are allowed to commute. And this, in turn, could have raised the interest for studying “in abstracto” problems concerning these words and the structure of the commutation monoids which is their habitat. Nonetheless, it happened on the contrary that words on partially commutative alphabets became of interest to computer scientists studying problems of concurrency control. Roughly speaking, the alphabet considered in this framework is made of functions and the commutation between these functions corresponds to the commutation of mappings under composition. A typical problem is then to decide wether, up to the commutation rule, a given word is equivalent to one in a special form (see [13], chapter 10 for an exposition of this problem). My own interest in such questions was motivated by the work of M.P. Flé and G. Roucairol [9] who proved a surprising result on finite automata in commutation monoids motivated by problems of concurrency control. The aim of this paper is to present a survey of results obtained recently on commutation monoids including a generalization of the above mentionned. It does not intend to be a comprehensive exposition and many facets of the question have been left in the dark. The first section introduces some terminology and definitions. The second section contains the discussion of two normal form theorems in commutation monoids. The third section contains some results on the structure of commutation monoids. Finally, in the last section, I will discuss the problem of finite automata and commutation monoids.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Anisimov, A.V., Knuth D., Inhomogeneous sorting, unpublished
Manuscript Berstel, J. Transductions and Context Free Languages,Teubner, 1979.
Cartier, P., Foata, D., Problèmes Combinatoires de Commutation et Réarrangements, Lecture Notes in Math., 85, Springer Verlag, 1969.
Clerbout, M., Latteux, M., Partial Commutations and faithful rational transductions, research report, Univ. Lille.
Cori, R., Métivier, Y. Rational subsets of some partially commutative monoids, Theoret. Comput. Sci.,to appear.
Cori, R., Perrin, D., Sur la reconnaissabilité dans les monoides partiellement commutatifs libres, Rairo In format. Theor., to appear
Duboc, C., Some properties of commutations in free partially commutative monoids Inform. Processing Letters,to appear.
Dulucq, S., Viennot, G., Bijective proof and generalizations of McMahon Master Theorem, unpublished manuscript.
Flé, M.P., Roucairol, G., Maximal serializability of iterated transactions, Theoret. Comput. Sci. to appear (see also ACM SIGACT SIGOPS, 1982, 194–200 ).
Lallement, G., Semigroups and Combinatorial Applications,Wiley, 1979.
Lothaire, M., Combinatorics on Words,Addison Wesley, 1983.
Métivier, Y., Une condition suffisante de reconnaissabilité dans les monoides partiellement commutatifs, Rairo In format. Theor.,to appear.
Ullman, J., Principles of Database Systems,Computer Science Press, 1980.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1985 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Perrin, D. (1985). Words over a Partially Commutative Alphabet. In: Apostolico, A., Galil, Z. (eds) Combinatorial Algorithms on Words. NATO ASI Series, vol 12. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-82456-2_23
Download citation
DOI: https://doi.org/10.1007/978-3-642-82456-2_23
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-82458-6
Online ISBN: 978-3-642-82456-2
eBook Packages: Springer Book Archive