Algebraic characterization of the finite power property

Warning

This publication doesn't include Faculty of Arts. It includes Faculty of Informatics. Official publication website can be found on muni.cz.

Authors	KUNC Michal
Year of publication	2006
Type	Article in Proceedings
Conference	Automata, Languages and Programming: 33rd International Colloquium, ICALP 2006, Venice, Italy, July 10-14, 2006, Proceedings, Part I
MU Faculty or unit	Faculty of Informatics
Citation
Web	http://www.springerlink.com/link.asp?id=aqj66l4h5vw87737
Field	General mathematics
Keywords	Finite power property; Regular language; Rational language; Syntactic semigroup; Rational monoid
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 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.
Related projects:	Institute for Theoretical Computer Science Mathematical structures and their physical applications