Inevitable graphs and profinite topologies: some solutions to algorithmic problems in monoid and automata theory, stemming from group theory

摘要

This paper deals with several algorithmic problems in monoid and automata theory arising from group theory. For H a pseudovariety of groups, we give a characterization of the regular elements of the H-kernel of a finite monoid. In particular, we show that if the extension problem for partial one-to-one maps for H is decidable, then so is the set of regular elements of the H-kernel. The extension problem for partial one-to-one maps for H asks if there is an algorithm to determine, given a finite set X and a set S of partial one-to-one maps on X, whether these is a finite set Y containing X so that each of the maps of S can be extended to permutations of Y in such a manner that the group generated by these permutations is in H. This problem is decidable for the pseudovariety of p-groups and nilpotent groups. We explore some other examples here. We also show that if the above problem is decidable, then so is the membership problem for J m H. Some applications to the membership problem for J * H are given. Finally, we show that certain pseudovarieties of groups, including the pseudovarieties of p-groups for p prime, are hyperdecidable. The techniques used here lay the groundwork for several future results on problems of this nature.