5 citations · 6 across the 7 of their papers we have counts for
Showing 2018Show all
2 papers · 1 filter
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…