On the centralizer of a finite set (bibtex)
by Karhumaki, Juhani and Petre, Ion
Abstract:
We prove two results on commutation of languages. First, we show that the maximal language commuting with a three element language, i.e. its em centralizer, is rational, thus giving an affirmative answer to a special case of a problem proposed by Conway in 1971. Second, we characterize all languages commuting with a three element code. The characterization is similar to the one proved by Bergman for polynomials over noncommuting variables, cf. Bergman, 1969 and Lothaire, 2000: A language commutes with a three element code $X$ if and only if it is a union of powers of $X$.
Reference:
On the centralizer of a finite set (Karhumaki, Juhani and Petre, Ion), In Proceedings of ICALP 2000, Springer, volume 1853, 2000.
Bibtex Entry:
@InProceedings{inp39,
author    = {Karhumaki, Juhani AND Petre, Ion},
title     = {On the centralizer of a finite set},
booktitle = {Proceedings of ICALP 2000},
year      = {2000},
volume    = {1853},
series    = {Lecture Notes in Computer Science},
pages     = {536-546},
publisher = {Springer},
abstract  = {We prove two results on commutation of languages. First, we show that the maximal language commuting with a three element language, i.e. its {em centralizer}, is rational, thus giving an affirmative answer to a special case of a problem proposed by Conway in 1971. Second, we characterize all languages commuting with a three element code. The characterization is similar to the one proved by Bergman for polynomials over noncommuting variables, cf. Bergman, 1969 and Lothaire, 2000: A language commutes with a three element code $X$ if and only if it is a union of powers of $X$.},
file      = {KP2000a.pdf:pdfs/KP2000a.pdf:PDF},
}