Informace o publikaci
The power of commuting with finite sets of words
| Název česky | Síla komutování s konečnými množinami slov |
|---|---|
| Autoři | |
| Rok publikování | 2007 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | Theory of Computing Systems |
| Fakulta / Pracoviště MU | |
| Citace | |
| www | http://dx.doi.org/10.1007/s00224-006-1321-z |
| Obor | Obecná matematika |
| Klíčová slova | Commutation of languages; Language equation; Regular language; Recursively enumerable language; Minsky machine |
| Popis | V práci konstruujeme konečný jazyk L takový, že největší jazyk komutující s L není rekurzívně vyčíslitelný. Tímto dáváme negativní odpověď na otázku, kterou položil Conway v roce 1971, a rovněž silně vyvracíme jeho hypotézu, že maximální řešení systémů pololineárních nerovnic jsou bezkontextová. |
| Související projekty: |