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:

You are running an old browser version. We recommend updating your browser to its latest version.