Search

• < Previous
• 1
• Next >

---

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 \omega or -\omega, and the monadic second-order theory of the combined structure is decidable, there exists a non-trivial expansion by a further monadic predicate that&nbsp;[&hellip;]

---

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 of the sets X1, ...,Xn. We first provide a (definable) criterion for definability of a cardinality relation in (N,<), and&nbsp;[&hellip;]

---

An Application of the Feferman-Vaught Theorem to Automata and Logics for 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 decidability properties, as well as several logical characterizations. We also consider a slight extension of the&nbsp;[&hellip;]

---

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 $\langle \mathbb{R}, +,<, \mathbb{Z} \rangle$ can be defined in the structure $\langle \mathbb{R}, +,<, 1 \rangle$. This result is achieved by obtaining a topological characterization of $\langle&nbsp;[&hellip;]

---