Publication details
Algebraic characterization of the finite power property
| Authors | |
|---|---|
| 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 | |
| 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: |