zbMATH — the first resource for mathematics

Playing with Conway’s problem. (English) Zbl 1156.68030
Summary: The centralizer of a language is the maximal language commuting with it. The question, raised by Conway in [J. H. Conway, Regular algebra and finite machines. London: Chapman and Hall (1971; Zbl 0231.94041)], whether the centralizer of a rational language is always rational, recently received a lot of attention. In [M. Kunc, “The power of commuting with finite sets of words”, Lect. Notes Comput. Sci. 3404, 569–580 (2005; Zbl 1119.68108)], a strong negative answer to this problem was given by showing that even complete co-recursively enumerable centralizers exist for finite languages. Using a combinatorial game approach, we give here an incremental construction of rational languages embedding any recursive computation in their centralizers.
68Q45 Formal languages and automata
Full Text: DOI
[1] Choffrut, C.; Karhumäki, J.; Ollinger, N., The commutation of finite sets: A challenging problem, Theoret. comput. sci., 273, 69-79, (2002) · Zbl 1014.68128
[2] Conway, J.H., Regular algebra and finite machines, (1971), Chapman Hall · Zbl 0231.94041
[3] Ratoandramanana, B., Codes et motifs, RAIRO theor. inform., 23, 425-444, (1989) · Zbl 0689.68102
[4] Karhumäki, J.; Latteux, M.; Petre, I., The commutation with codes and ternary sets of words, Theoret. comput. sci., 340, 322-333, (2005) · Zbl 1079.68051
[5] Karhumäki, J.; Petre, I., Conway’s problem for three-word sets, Theoret. comput. sci., 289, 705-725, (2002) · Zbl 1061.68097
[6] Okhotin, A., Decision problems for language equations with Boolean operations, (), 239-251 · Zbl 1039.68069
[7] Karhumäki, J., Challenges of commutation: an advertisement, (), 15-23 · Zbl 0999.68517
[8] Harju, T.; Ibarra, O.; Karhumäki, J.; Salomaa, A., Decision questions in semilinearity and commutation, J. comput. system. sci., 65, 278-294, (2002) · Zbl 1059.68061
[9] I. Petre, Commutation problems on sets of words and formal power series, Ph.D. thesis, University of Turku, 2002
[10] Karhumäki, J.; Petre, I., Two problems on commutation of languages, () · Zbl 1065.68079
[11] Kunc, M., Regular solutions of language inequalities and well quasi-orders, (), 870-881 · Zbl 1099.68664
[12] Kunc, M., The power of commuting with finite sets of words, (), 569-580 · Zbl 1119.68108
[13] Kunc, M., The power of commuting with finite sets of words, Theory comput. syst., 40, 4, 521-551, (2007) · Zbl 1121.68065
[14] Minsky, M., Computation: finite and infinite machines, (1967), Prentice Hall · Zbl 0195.02402
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.