The Finite Power Property in Free Group

F. D'ALESSANDRO, J. SAKAROVITCH

IBP-Litp 1996/33: Rapport de Recherche Litp / Litp research reports
34 pages - Octobre/October 1996 - Document en anglais.

PostScript : Ko /Kb

Titre / Title: The Finite Power Property in Free Group

Résumé : La propriété de puissance finie est décidable pour les parties rationnelles du groupe libre. La complexité de la construction utilisée par la procédure de décision peut être ramenée à $O(n^3)$ ‹ où $n$ est le nombre d'états de l'automate qui définit la partie rationnelle.

Abstract : We show that the finite power property is decidable for rational sets in free group. The complexity of the construction involved in the decision procedure may be lowered down to $O(n^3)$ ‹ where $n$ is the cardinality of the state set of the automaton that defines the rational set.

Publications internes Litp 1996 / Litp research reports 1996