✦ LIBER ✦

The finite power property in free groups

✍ Scribed by Flavio d'Alessandro; Jacques Sakarovitch

Publisher: Elsevier Science
Year: 2003
Tongue: English
Weight: 368 KB
Volume: 293
Category: Article
ISSN: 0304-3975
DOI: 10.1016/s0304-3975(02)00232-3

No coin nor oath required. For personal study only.

✦ Synopsis

We show that the ÿnite 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 deÿnes the rational set.

RÃ esumÃ e

La propriÃ etÃ e de puissance ÿnie est dÃ ecidable pour les parties rationnelles du groupe libre. La complexitÃ e de la construction utilisÃ ee par la procÃ edure de dÃ ecision peut être ramenÃ ee Â a O(n 3 )-oÂ u n est le nombre d'Ã etats de l'automate qui dÃ eÿnit la partie rationnelle.

📜 SIMILAR VOLUMES

The finite power property for context-fr

The finite power property for context-free languages

✍ Charles E. Hughes; Stanley M. Selkow 📂 Article 📅 1981 🏛 Elsevier Science 🌐 English ⚖ 280 KB

Residual properties of free products of

Residual properties of free products of finite groups

✍ Martin W. Liebeck; Aner Shalev 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 144 KB

Using a probabilistic approach we establish a new residual property of free products of finite groups.

On finite groups with the cayley isomorp

On finite groups with the cayley isomorphism property

✍ Li, Cai Heng; Praeger, Cheryl E.; Xu, Ming Yao 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 197 KB

Let G be a finite group, and let Cay(G, S) be a Cayley digraph of G. If, for all T ⊂ G, Cay(G, S) ∼ = Cay(G, T ) implies S α = T for some α ∈ Aut(G), then Cay(G, S) is called a CI-graph of G. For a group G, if all Cayley digraphs of valency m are CI-graphs, then G is said to have the m-DCI property;

Souslin property in free topological gro

Souslin property in free topological groups on bicompacta

✍ M. G. Tkachenko 📂 Article 📅 1983 🏛 SP MAIK Nauka/Interperiodica 🌐 English ⚖ 342 KB

Almost free groups and the M. Hall prope

Almost free groups and the M. Hall property

✍ O. V. Bogopol'skii 📂 Article 📅 1994 🏛 Springer US 🌐 English ⚖ 1022 KB

On Finite Groups with the Cayley Isomorp

On Finite Groups with the Cayley Isomorphism Property, II

✍ Cai Heng Li 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 184 KB

For a positive integer m, a group G is said to have the m-DCI property if, for any Cayley digraphs Cay(G, S) and Cay(G, T ) of G of valency m (that is, |S| = |T | =m), Cay(G, S)$Cay(G, T ) if and only if S \_ =T for some \_ # Aut(G). This paper is one of a series of papers towards characterizing fin