Prefer a chat interface with context about you and your work?
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 …