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}, }

Powered by bibtexbrowser