The power of commuting with finite sets of words

Warning

This publication doesn't include Faculty of Medicine. It includes Faculty of Science. Official publication website can be found on muni.cz.
Authors

KUNC Michal

Year of publication 2007
Type Article in Periodical
Magazine / Source Theory of Computing Systems
MU Faculty or unit

Faculty of Science

Citation
Web http://dx.doi.org/10.1007/s00224-006-1321-z
Field General mathematics
Keywords Commutation of languages; Language equation; Regular language; Recursively enumerable language; Minsky machine
Description We construct a finite language L such that the largest language commuting with L is not recursively enumerable. This gives a negative answer to the question raised by Conway in 1971 and also strongly disproves Conway's conjecture on context-freeness of maximal solutions of systems of semi-linear inequalities.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.

More info