D 2005

The power of commuting with finite sets of words

KUNC, Michal

Zá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

Vydání

Berlin, STACS 2005: 22nd Annual Symposium on Theoretical Aspects of Computer Science, Stuttgart, Germany, February 24-26, 2005. Proceedings, s. 569-580, 2005

Nakladatel

Springer-Verlag

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10101 Pure mathematics

Stát vydavatele

Německo

Utajení

není předmětem státního či obchodního tajemství

Odkazy

Kód RIV

RIV/00216224:14310/05:00013633

Organizační jednotka

Přírodovědecká fakulta

ISBN

3-540-24998-2

UT WoS

000229009500047

Klíčová slova anglicky

Commutation of languages; Language equation; Regular language; Recursively enumerable language; Minsky machine

Štítky

Změněno: 23. 1. 2006 14:55, doc. Mgr. Michal Kunc, Ph.D.

Anotace

ORIG CZ

V originále

We show that one can 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 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á.

Návaznosti

MSM 143100009, záměr
Název: Matematické struktury algebry a geometrie
Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Matematické struktury algebry a geometrie