Closed subgroups in pro-\(\mathbf V\) topologies and the extension problem for inverse automata. (English) Zbl 1027.20036
Summary: We relate the problem of computing the closure of a finitely generated subgroup of the free group in the pro-\(\mathbf V\) topology, where \(\mathbf V\) is a pseudovariety of finite groups, with an extension problem for inverse automata which can be stated as follows: given partial one-to-one maps on a finite set, can they be extended into permutations generating a group in \(\mathbf V\)? The two problems are equivalent when \(\mathbf V\) is extension-closed. Turning to practical computations, we modify Ribes and Zalesskij’s algorithm to compute the pro-\(p\) closure of a finitely generated subgroup of the free group in polynomial time, and to effectively compute its pro-nilpotent closure. Finally, we apply our results to a problem in finite monoid theory, the membership problem in pseudovarieties of inverse monoids which are Mal’cev products of semilattices and a pseudovariety of groups.
MSC:
20M07 | Varieties and pseudovarieties of semigroups |
20M35 | Semigroups in automata theory, linguistics, etc. |
20M05 | Free semigroups, generators and relations, word problems |
68Q70 | Algebraic theory of languages and automata |
20E18 | Limits, profinite groups |
Keywords:
pseudovarieties of finite groups; extension problem; inverse automata; pro-\(p\) closures; free groups; pro-nilpotent closures; inverse monoids; Mal’cev products; membership problemReferences:
[1] | DOI: 10.1142/S0218196791000079 · Zbl 0722.20039 · doi:10.1142/S0218196791000079 |
[2] | Gildenhuys D., Trans. Amer. Math. Soc. 186 pp 309– (1973) |
[3] | DOI: 10.1090/S0002-9947-1949-0032642-4 · doi:10.1090/S0002-9947-1949-0032642-4 |
[4] | DOI: 10.2307/1969513 · doi:10.2307/1969513 |
[5] | DOI: 10.1142/S0218196791000298 · Zbl 0791.20079 · doi:10.1142/S0218196791000298 |
[6] | DOI: 10.1142/S021819679300007X · Zbl 0798.20056 · doi:10.1142/S021819679300007X |
[7] | DOI: 10.1016/0021-8693(91)90094-O · Zbl 0739.20032 · doi:10.1016/0021-8693(91)90094-O |
[8] | DOI: 10.1006/jabr.1996.0192 · Zbl 0857.20040 · doi:10.1006/jabr.1996.0192 |
[9] | DOI: 10.1112/blms/25.1.37 · Zbl 0811.20026 · doi:10.1112/blms/25.1.37 |
[10] | DOI: 10.1142/S021819679400004X · Zbl 0839.20041 · doi:10.1142/S021819679400004X |
[11] | DOI: 10.1007/BF02095993 · Zbl 0521.20013 · doi:10.1007/BF02095993 |
[12] | DOI: 10.1142/S0218196701000462 · Zbl 1024.68064 · doi:10.1142/S0218196701000462 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.