Dichotomy conjecture for free products of automaton semigroups

Let A\mathcal{A} and B\mathcal{B} be automata, and let Σ(A)\Sigma(\mathcal{A}) and Σ(B)\Sigma(\mathcal{B}) be the automaton semigroups generated by their states. Their free product is denoted by Σ(A)Σ(B)\Sigma(\mathcal{A})\star\Sigma(\mathcal{B}). Dichotomy conjecture. One of the following holds: every free product of two, and hence of finitely many, automaton semigroups is itself an automaton semigroup; or it is undecidable, given two automata A\mathcal{A} and B\mathcal{B}, whether Σ(A)Σ(B)\Sigma(\mathcal{A})\star\Sigma(\mathcal{B}) is an automaton semigroup. This presents the unresolved closure question as a dichotomy between universal closure and undecidability of the corresponding decision problem.

Sources & referencesView supporting material

Primary source

Tara Macalister Brough, Jan Philipp Wächter and Janette Welker, “Preserving self-similarity in free products of semigroups”, arXiv:2003.12810 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.