The Freeness Problem for Automaton Semigroups
<|reference_start|>The Freeness Problem for Automaton Semigroups: We show that the freeness problems for automaton semigroups and for automaton monoids are undecidable by giving a reduction from Post's Correspondence Problem. This construction seems to be quite versatile and we also immediately obtain that the problems of testing whether a given automaton semigroup (monoid) is (left) cancellative or whether it is equidivisible are undecidable. We also obtain that it is undecidable whether a given map extends into a homomorphism of automaton semigroups. Finally, we adapt our construction to show that it is undecidable whether a given automaton generates a free monoid whose basis is given by the states (but where we allow one state to act as the identity). In the semigroup case, we show a weaker version of this statement.<|reference_end|>
@article{d'angeli2024the,
    title={The Freeness Problem for Automaton Semigroups},
    author={Daniele D'Angeli and Emanuele Rodaro and Jan Philipp W"achter},
    journal={arXiv preprint arXiv:2402.01372},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.01372},
    primaryClass={cs.FL math.GR}
}