2007
The power of commuting with finite sets of words
KUNC, MichalZákladní údaje
Originální název
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
KUNC, Michal (203 Česká republika, garant)
Vydání
Theory of Computing Systems, New York, Springer, 2007, 1432-4350
Další údaje
Jazyk
angličtina
Typ výsledku
Článek v odborném periodiku
Obor
10101 Pure mathematics
Stát vydavatele
Spojené státy
Utajení
není předmětem státního či obchodního tajemství
Odkazy
Impakt faktor
Impact factor: 0.625
Kód RIV
RIV/00216224:14310/07:00022354
Organizační jednotka
Přírodovědecká fakulta
UT WoS
000245244400013
Klíčová slova anglicky
Commutation of languages; Language equation; Regular language; Recursively enumerable language; Minsky machine
Štítky
Příznaky
Mezinárodní význam, Recenzováno
Změněno: 31. 8. 2007 10:40, doc. Mgr. Michal Kunc, Ph.D.
V originále
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.
Česky
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á.
Návaznosti
| MSM0021622409, záměr |
|