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

Označené pro přenos do RIV

Ano

Kód RIV

RIV/00216224:14310/05:00013633

Organizační jednotka

Přírodovědecká fakulta

ISBN

3-540-24998-2

UT WoS

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