Informace o publikaci
Algebraic characterization of the finite power property
| Název česky | Algebraická charakterizace vlastnosti konečné mocniny |
|---|---|
| Autoři | |
| 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 | |
| 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: |