Search


Volume

Author

Year

  • < Previous
  • 1
  • Next >
4 results

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;]
Published on May 7, 2011

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;]
Published on December 5, 2013

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;]
Published on March 25, 2008

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;]
Published on May 26, 2021

  • < Previous
  • 1
  • Next >