Author name cluster

Thibault Godin

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

3 papers

2 author rows

Highlights Conference 2018 Conference Abstract

A new hierarchy for automaton semigroups

Thibault Godin

ABSTRACT. We define a new strict and computable hierarchy for the family of automaton semigroups, which reflects the various asymptotic behaviours of the state-activity growth. This hierarchy extends that given by Sidki for automaton groups, and also gives new insights into the latter. Its exponential part coincides with a notion of entropy for some associated automata. We prove that the Order Problem is decidable when the state-activity is bounded. The Order Problem remains open for the next level of this hierarchy, that is, when the state-activity is linear. Gillibert showed that it is undecidable in the whole family.

Details

TCS Journal 2018 Journal Article

On bireversible Mealy automata and the Burnside problem

Thibault Godin
Ines Klimann

There exist undoubtedly strong links between the Burnside problem and the class of automaton groups. Indeed, many interesting examples of infinite Burnside groups are automaton groups, in particular for any prime p, there exist an infinite Burnise p-group generated by a Mealy automaton. Moreover the simplest known example of an infinite Burnside group arises in this class. However there is no known example of such a group generated by a reversible Mealy automaton. In this paper we prove that, in fact, no connected reversible Mealy automaton of prime size can generate an infinite Burnside group. In addition we explain how our method can be applied for some Mealy automata of non prime size.

Details DOI

MFCS Conference 2016 Conference Paper

Connected Reversible Mealy Automata of Prime Size Cannot Generate Infinite Burnside Groups

Thibault Godin
Ines Klimann

The simplest example of an infinite Burnside group arises in the class of automaton groups. However there is no known example of such a group generated by a reversible Mealy automaton. It has been proved that, for a connected automaton of size at most 3, or when the automaton is not bireversible, the generated group cannot be Burnside infinite. In this paper, we extend these results to automata with bigger stateset, proving that, if a connected reversible automaton has a prime number of states, it cannot generate an infinite Burnside group.

Details