The Finite Power Property for Rational Sets of the Free Group

F. D'Alessandro, J. Sakarovitch

IBP-Litp 1996/16: Rapport de Recherche Litp / Litp research reports
8 pages - Mars/March 1996 - Document en anglais.

PostScript : Ko /Kb

Titre / Title: The Finite Power Property for Rational Sets of the Free Group

Résumé : Un sous ensemble L d'un monoïde est dit "limité" si le sous monoïde engendré par L est égal à l'union d'un nombre fini de puissances de L . En terme d'automates, cela correspond au fait qu'une rétroaction sur une "boîte noire" réalisant L peut être remplacée par une suite finie de telles boîtes noires. Il a été montré en 1978 par Hashiguchi et Simon que la propriété de limitation est décidable pour les parties rationnelles du monoïde libre. Nous démontrons ici que la même propriété vaut pour les parties rationnelles du groupe libre.

Abstract : A subset L of a monoid is said to have the "finite power property" if the monoid generated by L is equal to a finite sum of powers of L. In terms of machines, it corresponds to the fact that a feedback around a device realizing L may be replaced by a finite series of such a device. The finite power property in the free monoid has been shown decidable for rational sets by Hashiguchi and Simon in 1978. We prove here that the finite power property is decidable for rational sets of the free group.

Publications internes Litp 1996 / Litp research reports 1996