| 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. |
Další formáty:
BibTeX
LaTeX
RIS
@inproceedings{639524,
author = {Kunc, Michal},
address = {Berlin},
booktitle = {Automata, Languages and Programming: 33rd International Colloquium, ICALP 2006, Venice, Italy, July 10-14, 2006, Proceedings, Part I},
keywords = {Finite power property; Regular language; Rational language; Syntactic semigroup; Rational monoid},
language = {eng},
location = {Berlin},
isbn = {3-540-35904-4},
pages = {120-131},
publisher = {Springer},
title = {Algebraic characterization of the finite power property},
url = {http://www.springerlink.com/link.asp?id=aqj66l4h5vw87737},
year = {2006}
}
TY - JOUR
ID - 639524
AU - Kunc, Michal
PY - 2006
TI - Algebraic characterization of the finite power property
PB - Springer
CY - Berlin
SN - 3540359044
KW - Finite power property
KW - Regular language
KW - Rational language
KW - Syntactic semigroup
KW - Rational monoid
UR - http://www.springerlink.com/link.asp?id=aqj66l4h5vw87737
N2 - 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.
ER -
KUNC, Michal. Algebraic characterization of the finite power property. In \textit{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.
|
