On the simplest centralizer of a language. (English) Zbl 1112.68097
Summary: Given a finite alphabet \(\Sigma\) and a language \(L\subseteq \Sigma^+\), the centralizer of \(L\) is defined as the maximal language commuting with it. We prove that if the primitive root of the smallest word of \(L\) (with respect to a lexicographic order) is prefix distinguishable in \(L\) then the centralizer of \(L\) is as simple as possible, that is, the submonoid \(L^\star\). This lets us obtain a simple proof of a known result concerning the centralizer of nonperiodic three-word languages.
References:
| [1] | J. Berstel and D. Perrin , Theory of codes . Academic Press, New York ( 1985 ). MR 797069 | Zbl 0587.68066 · Zbl 0587.68066 |
| [2] | J.A. Brzozowski and E. Leiss , On equations for regular languages, finite automata, and sequential networks . Theor. Comp. Sci. 10 ( 1980 ) 19 - 35 . Zbl 0415.68023 · Zbl 0415.68023 · doi:10.1016/0304-3975(80)90069-9 |
| [3] | C. Choffrut , J. Karhumäki and N. Ollinger , The commutation of finite sets: a challenging problem . Theor. Comp. Sci. 273 ( 2002 ) 69 - 79 . Zbl 1014.68128 · Zbl 1014.68128 · doi:10.1016/S0304-3975(00)00434-5 |
| [4] | N. Chomsky and M.P. Schützenberger , The algebraic theory of context-free languages . Computer Programming and Formal Systems, edited by P. Braffort and D. Hirschberg. North-Holland, Amsterdam ( 1963 ) 118 - 161 . Zbl 0148.00804 · Zbl 0148.00804 |
| [5] | J.H. Conway , Regular Algebra and Finite Machines . Chapman & Hall, London ( 1971 ). Zbl 0231.94041 · Zbl 0231.94041 |
| [6] | J. Karhumäki and I. Petre , The branching point approach to Conway’s problem , in Formal and Natural Computing, edited by W. Brauer, H. Ehrig, J. Karhumäki, A. Salomaa. Lect. Notes Comput. Sci. 2300 ( 2002 ) 69 - 76 . Zbl 1060.68095 · Zbl 1060.68095 |
| [7] | J. Karhumäki and I. Petre , Conway’s problem for three-word sets . Theor. Comp. Sci. 289 ( 2002 ) 705 - 725 . Zbl 1061.68097 · Zbl 1061.68097 · doi:10.1016/S0304-3975(01)00389-9 |
| [8] | J. Karhumäki , M. Latteux and I. Petre , Commutation with codes . Theor. Comp. Sci. 340 ( 2005 ) 322 - 333 . Zbl 1079.68051 · Zbl 1079.68051 · doi:10.1016/j.tcs.2005.03.037 |
| [9] | J. Karhumäki , M. Latteux and I. Petre , Commutation with ternary sets of words . Theory Comput. Syst. 38 ( 2005 ) 161 - 169 . Zbl 1066.68102 · Zbl 1066.68102 · doi:10.1007/s00224-004-1191-1 |
| [10] | M. Kunc , The power of commuting with finite sets of words , in Proc. of STACS 2005. Lect. Notes Comput. Sci. 3404 ( 2005 ) 569 - 580 . Zbl 1119.68108 · Zbl 1119.68108 · doi:10.1007/b106485 |
| [11] | R.C. Lyndon and M.P. Schützenberger , The equation \(a^m=b^nc^p\) in a free group . Michigan Math. J. 9 ( 1962 ) 289 - 298 . Article | Zbl 0106.02204 · Zbl 0106.02204 · doi:10.1307/mmj/1028998766 |
| [12] | P. Massazza , On the equation \(XL=LX\) , in Proc. of WORDS 2005, Publications du Laboratoire de Combinatoire et d’Informatique Mathématique, Montréal 36 ( 2005 ) 315 - 322 . |
| [13] | D. Perrin , Codes conjugués . Inform. Control 20 ( 1972 ) 222 - 231 . Zbl 0254.94015 · Zbl 0254.94015 · doi:10.1016/S0019-9958(72)90406-8 |
| [14] | B. Ratoandromanana , Codes et motifs . RAIRO-Inf. Theor. Appl. 23 ( 1989 ) 425 - 444 . Numdam | Zbl 0689.68102 · Zbl 0689.68102 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
