Bounded statements in the theory of algebraically closed fields with distinguished automophisms.
Centraliser dimension and universal classes of groups.
Choice functions and well-orderings over the infinite binary tree
We give a new proof showing that it is not possible to define in monadic second-order logic (MSO) a choice function on the infinite binary tree. This result was first obtained by Gurevich and Shelah using set theoretical arguments. Our proof is much simpler and only uses basic tools from automata theory. We show how the result can be used to prove the inherent ambiguity of languages of infinite trees. In a second part we strengthen the result of the non-existence of an MSO-definable well-founded...
Church-Rosser property and decidability of monadic theories of unary algebras
Compacidad Y Decibilidad De Logicas Monadicas Con Cuantificadores Cardinales.
Comparing the succinctness of monadic query languages over finite trees
We study the succinctness of monadic second-order logic and a variety of monadic fixed point logics on trees. All these languages are known to have the same expressive power on trees, but some can express the same queries much more succinctly than others. For example, we show that, under some complexity theoretic assumption, monadic second-order logic is non-elementarily more succinct than monadic least fixed point logic, which in turn is non-elementarily more succinct than monadic datalog. Succinctness...
Comparing the succinctness of monadic query languages over finite trees
We study the succinctness of monadic second-order logic and a variety of monadic fixed point logics on trees. All these languages are known to have the same expressive power on trees, but some can express the same queries much more succinctly than others. For example, we show that, under some complexity theoretic assumption, monadic second-order logic is non-elementarily more succinct than monadic least fixed point logic, which in turn is non-elementarily more succinct than monadic datalog. Succinctness...
Complexity of the decidability of one class of formulas in quantifier-free set theory with a set-union operator.
Complexity of the decidability of the unquantified set theory with a rank operator.
Congruences parfaites et quasi-parfaites
Construction d'un plus petit ordre de simplification
Constructive analysis and thermodynamics formulations.
Critical theories of varieties of semigroups satisfying a permutation identity.
Das Entscheidungsproblem der Klasse von Formeln, die höchstens zwei Primformeln enthalten.
Decidability and definability results related to the elementary theory of ordinal multiplication
The elementary theory of ⟨α;×⟩, where α is an ordinal and × denotes ordinal multiplication, is decidable if and only if . Moreover if and respectively denote the right- and left-hand divisibility relation, we show that Th and Th are decidable for every ordinal ξ. Further related definability results are also presented.
Decidability and structure
Decidability and undecidability of theories of abelian groups with predicates for subgroups
Decidability of equational theories of coverings of semigroup varieties.
Decidability of the HD0L ultimate periodicity problem
In this paper we prove the decidability of the HD0L ultimate periodicity problem.
Decidability of the rings of real algebraic and p-adic algebraic integers.