Algebraic characterization of the finite power property

KUNC, Michal. Algebraic characterization of the finite power property. In Automata, Languages and Programming: 33rd International Colloquium, ICALP 2006, Venice, Italy, July 10-14, 2006, Proceedings, Part I. Berlin: Springer, 2006, s. 120-131. ISBN 3-540-35904-4.

Základní údaje

Originální název

Algebraic characterization of the finite power property

Název česky

Algebraická charakterizace vlastnosti konečné mocniny

Autoři

KUNC, Michal (203 Česká republika, garant)

Vydání

Berlin, Automata, Languages and Programming: 33rd International Colloquium, ICALP 2006, Venice, Italy, July 10-14, 2006, Proceedings, Part I, s. 120-131, 2006

Nakladatel

Springer

---

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

URL

Kód RIV

RIV/00216224:14330/06:00017022

Organizační jednotka

Fakulta informatiky

ISBN

3-540-35904-4

UT WoS

000239474500012

Klíčová slova anglicky

Finite power property; Regular language; Rational language; Syntactic semigroup; Rational monoid

Štítky

Finite power property, Rational language, Rational monoid, Regular language, Syntactic semigroup

---

Anotace

V originále

We give a transparent characterization, by means of a certain syntactic semigroup, of regular languages possessing the finite power property. Then we use this characterization to obtain a short elementary proof for the uniform decidability of the finite power property for rational languages in all monoids defined by a confluent regular system of deletion rules. This result in particular covers the case of free groups solved earlier by d'Alessandro and Sakarovitch by means of an involved reduction to the boundedness problem for distance automata.

Česky

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ů.

---

Návaznosti

MSM0021622409, záměr	Název: Matematické struktury a jejich fyzikální aplikace Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Matematické struktury a jejich fyzikální aplikace
1M0545, projekt VaV	Název: Institut Teoretické Informatiky Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Institut Teoretické Informatiky