Algebraic characterization of the finite power property

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F06%3A00017022" target="_blank" >RIV/00216224:14330/06:00017022 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—

Result language
angličtina
Original language name
Algebraic characterization of the finite power property
Original language description
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 finitepower 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 theboundedness problem for distance automata.
Czech name
Algebraická charakterizace vlastnosti konečné mocniny
Czech description
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ů.

Project
<a href="/en/project/1M0545" target="_blank" >1M0545: Institute for Theoretical Computer Science</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year
2006
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection
Automata, Languages and Programming: 33rd International Colloquium, ICALP 2006, Venice, Italy, July 10-14, 2006, Proceedings, Part I
ISBN
3-540-35904-4
ISSN
—
e-ISSN
—
Number of pages
12
Pages from-to
120
Publisher name
Springer
Place of publication
Berlin
Event location
Venice, Italy
Event date
Jan 1, 2006
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—

Similar results(10)