Algebraic characterization of the finite power property

Varování

Publikace nespadá pod Fakultu sportovních studií, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.
Název česky Algebraická charakterizace vlastnosti konečné mocniny
Autoři

KUNC Michal

Rok publikování 2006
Druh Článek ve sborníku
Konference Automata, Languages and Programming: 33rd International Colloquium, ICALP 2006, Venice, Italy, July 10-14, 2006, Proceedings, Part I
Fakulta / Pracoviště MU

Fakulta informatiky

Citace
www http://www.springerlink.com/link.asp?id=aqj66l4h5vw87737
Obor Obecná matematika
Klíčová slova Finite power property; Regular language; Rational language; Syntactic semigroup; Rational monoid
Popis Pomocí jisté syntaktické pologrupy transparentně charakterizujeme regulární jazyky mající vlastnost konečné mocniny. Tuto charakterizaci potom používáme ke získání krátkého elementárního důkazu uniformní rozhodnutelnosti vlastnosti konečné mocniny pro racionální jazyky ve všech monoidech definovaných konfluentním regulárním systémem mazacích pravidel. Tento výsledek zahrnuje zejména případ volných grup, který vyřešili dříve d'Alessandro a Sakarovitch obtížnou redukcí na problém omezenosti distančních automatů.
Související projekty:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.

Další info