We show that the finite power property is decidable for rational sets in the free group. The complexity of the construction involved in the decision procedure may be lowered to O(n(3))where n is the cardinality of the state set of the automaton that defines the rational set.
The finite power property in free groups / D'Alessandro, Flavio; Jacques, Sakarovitch. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - STAMPA. - 293:1(2003), pp. 55-82. (Intervento presentato al convegno Max-Plus Algebras tenutosi a Vendee nel 4 May 1998 through 7 May 1998) [10.1016/s0304-3975(02)00232-3].
The finite power property in free groups
D'ALESSANDRO, Flavio;
2003
Abstract
We show that the finite power property is decidable for rational sets in the free group. The complexity of the construction involved in the decision procedure may be lowered to O(n(3))where n is the cardinality of the state set of the automaton that defines the rational set.File allegati a questo prodotto
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
