1 citations · 1 across the 1 of their papers we have counts for
3 papers
math.GR2019★ 1 cited
Quasi-automatic semigroups
Benjamin Blanchette, Christian Choffrut, Christophe Reutenauer
A quasi-automatic semigroup is defined by a finite set of generators, a rational (regular) set of representatives, such that if a is a generator or neutral, then the graph of right…
cs.LO2018
Decidability of the existential fragment of some infinitely generated trace monoids: an application to ordinals
Alexis Bès, Christian Choffrut
Diekert, Matiyasevich and Muscholl proved that the existential first-order theory of a trace monoid over a finite alphabet is decidable. We extend this result to a natural class of…
cs.LO2018
Complexity and (un)decidability of fragments of
Alexis Bès, Christian Choffrut
We specify the frontier of decidability for fragments of the first-order theory of ordinal multiplication. We give a NEXPTIME lower bound for the complexity of the existential frag…