5 citations · 6 across the 7 of their papers we have counts for
7 papers
Grammic monoids with three generators
Christian Choffrut
Young tableaux are combinatorial objects whose construction can be achieved from words over a finite alphabet by row or column insertion as shown by Schensted sixty years ago. Rece…
Decidability of definability issues in the theory of real addition
Alexis Bès, Christian Choffrut
Given a subset of we can associate with every point a vector space of maximal dimension with the property that for some ball c…
Theories of real addition with and without a predicate for integers
Alexis Bès, Christian Choffrut
We show that it is decidable whether or not a relation on the reals definable in the structure can be defined in the structure $\langl…
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…
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…
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…
Quantum finite automata and linear context-free languages: a decidable problem
A. Bertoni, Ch. Choffrut, F. D'Alessandro
We consider the so-called measure once finite quantum automata model introduced by Moore and Crutchfield in 2000. We show that given a language recognized by such a device and a li…