10 citations · 23 across the 7 of their papers we have counts for
7 papers
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…
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…
Expansions of MSO by cardinality relations
Alexis Bès
We study expansions of the Weak Monadic Second Order theory of (N,<) by cardinality relations, which are predicates R(X1,...,Xn) whose truth value depends only on the cardinality o…
Decidable Expansions of Labelled Linear Orderings
Alexis Bes, Alexander Rabinovich
Consider a linear ordering equipped with a finite sequence of monadic predicates. If the ordering contains an interval of order type ωor -ω, and the monadic second-order theory of…
An Application of the Feferman-Vaught Theorem to Automata and Logics for<br> Words over an Infinite Alphabet
Alexis Bès
We show that a special case of the Feferman-Vaught composition theorem gives rise to a natural notion of automata for finite words over an infinite alphabet, with good closure and…