×

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
Full Text: DOI

References:

[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.