Abstract
We prove several results on the commutation of languages. First, we prove that the largest set commuting with a given code X, i.e., its centralizer C(X), is always ρ(X)., where ρ(X) is the primitive rootof X. Using this result, we characterize the commutation with codes similarly as for words, polynomials, and formal power series: a language commutes with X if and only if it is a union of powers of ρ(X). This solves a conjecture of Ratoandromanana, 1989, and also gives an affermative answer to a special case of an intriguing problem raised by Conway in 1971. Second, we prove that for any nonperiodic ternary set of words F ⊆∑+,C(F) = F*., and moreover, a language commutes with F if and only if it is a union of powers of F, results previously known only for ternary codes. A boundary point is thus established, as these results do not hold for all languages with at least four words.
Work supported by Academy of Finland under grant 44087
Current address: Department of Computer Science, Åbo Akademi University, Turku 20520, Finland, ipetre@abo..
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
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Autebert, J.M., Boasson, L., Latteux, M.: Motifs et bases de langages, RAIRO Inform. Theor., 23(4) (1989) 379–393.
Bergman, G.: Centralizers in free associative algebras, Transactions of the American Mathematical Society 137 (1969) 327–344.
Berstel, J., Perrin, D.: Theory of Codes, Academic Press, New York (1985).
Choffrut, C., Karhumäki, J.: Combinatorics of Words. In Rozenberg, G., Salomaa, A. (eds.), Handbook of Formal Languages, Vol. 1, Springer-Verlag (1997) 329–438.
Choffrut, C., Karhumäki, J.: On Fatou properties of rational languages, in Martin-Vide, C., Mitrana, V. (eds.), Where mathematics, Computer Science, Linguistics and Biology Meet, Kluwer, Dordrecht (2000).
Choffrut, C., Karhumäki, J., Ollinger, N.: The commutation of finite sets: a challenging problem, Theoret. Comput. Sci., 273 (1–2) (2002) 69–79.
Cohn, P.M.: Factorization in noncommuting power series rings, Proc. Cambridge Philos. Soc. 58 (1962) 452–464.
Cohn, P.M.: Centralisateurs dans les corps libres, in Berstel, J. (ed.), Sℰies formelles, Paris, (1978) 45–54.
Conway, J.H.: Regular Algebra and Finite Machines, Chapman Hall (1971).
Devolder, J., Latteux, M., Litovsky, I., Staiger, L.: Codes and infinite words, Acta Cybernetica 11 (1994) 241–256.
Harju, T., Petre, I.: On commutation and primitive roots of codes, submitted. A preliminary version of this paper has been presented at WORDS 2001, Palermo, Italy.
Karhumäki, J.: Challenges of commutation: an advertisement, in Proc. of FCT 2001, LNCS 2138, Springer (2001) 15–23.
Karhumäki, J., Petre, I.: On the centralizer of a finite set, in Proc. of ICALP 2000, LNCS 1853, Springer (2000) 536–546.
Karhumäki, J., Petre, I.: Conway’s Problem for three-word sets, Theoret. Comput. Sci., 289/1 (2002) 705–725.
Karhumäki, J., Petre, I.: Conway’s problem and the commutation of languages, Bulletin of EATCS 74 (2001) 171–177.
Karhumäki, J., Petre, I.: The branching point approach to Conway’s problem, LNCS 2300, Springer (2002) 69–76.
Lothaire, M.: Combinatorics on Words (Addison-Wesley, Reading, MA., (1983).
Lothaire, M.: Algebraic Combinatorics on Words (Cambridge University Press), (2002).
Mateescu, A., Salomaa, A., Yu, S.: On the decomposition of finite languages, TUCS Technical Report 222, http://www.tucs../ (1998).
Petre, I.: Commutation Problems on Sets of Words and Formal Power Series, PhD Thesis, University of Turku (2002).
Ratoandromanana, B.: Codes et motifs, RAIRO Inform. Theor., 23(4) (1989) 425–444.
Restivo, A.: Some decision results for recognizable sets in arbitrary monoids, in Proc. of ICALP 1978, LNCS 62 Springer (1978) 363–371.
Shyr, H.J.: Free monoids and languages, Hon Min Book Company, (1991).
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Karhumäki, J., Latteux, M., Petre, I. (2003). The Commutation with Codes and Ternary Sets of Words. In: Alt, H., Habib, M. (eds) STACS 2003. STACS 2003. Lecture Notes in Computer Science, vol 2607. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-36494-3_8
Download citation
DOI: https://doi.org/10.1007/3-540-36494-3_8
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-00623-7
Online ISBN: 978-3-540-36494-8
eBook Packages: Springer Book Archive