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í | 2005 |
| Druh | Článek ve sborníku |
| Konference | STACS 2005: 22nd Annual Symposium on Theoretical Aspects of Computer Science, Stuttgart, Germany, February 24-26, 2005. Proceedings |
| Fakulta / Pracoviště MU | |
| Citace | |
| www | http://www.springerlink.com/link.asp?id=72ul1qvmpr3utqyp |
| Obor | Obecná matematika |
| Klíčová slova | Commutation of languages; Language equation; Regular language; Recursively enumerable language; Minsky machine |
| Popis | V práci ukazujeme, že lze zkonstruovat 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: |