Decidability of weak equational theories
Decidability problems for the variety generated by tournaments.
Decidable Theories of Preordered Fields.
Deciding whether a relation defined in Presburger logic can be defined in weaker logics
We consider logics on and which are weaker than Presburger arithmetic and we settle the following decision problem: given a k-ary relation on and which are first order definable in Presburger arithmetic, are they definable in these weaker logics? These logics, intuitively, are obtained by considering modulo and threshold counting predicates for differences of two variables.
Decision problems among the main subfamilies of rational relations
We consider the four families of recognizable, synchronous, deterministic rational and rational subsets of a direct product of free monoids. They form a strict hierarchy and we investigate the following decision problem: given a relation in one of the families, does it belong to a smaller family? We settle the problem entirely when all monoids have a unique generator and fill some gaps in the general case. In particular, adapting a proof of Stearns, we show that it is recursively decidable whether...
Definability of arithmetical operations from binary quadratic forms
Definability within structures related to Pascal’s triangle modulo an integer
Let Sq denote the set of squares, and let be the squaring function restricted to powers of n; let ⊥ denote the coprimeness relation. Let . For every integer n ≥ 2 addition and multiplication are definable in the structures ⟨ℕ; Bn,⊥⟩ and ⟨ℕ; Bn,Sq⟩; thus their elementary theories are undecidable. On the other hand, for every prime p the elementary theory of ⟨ℕ; Bp,SQp⟩ is decidable.
Der Cohensche Eliminationssatz in positiver Charakteristik
Deux propriétés décidables des suites récurrentes linéaires
Diagonal reasonings in mathematical logic
First we show a few well known mathematical diagonal reasonings. Then we concentrate on diagonal reasonings typical for mathematical logic.
Die m-Grade logischer Entscheidungsprobleme.
Die Vollständigkeit einer unverzweigten Variante des "analytischen" Entscheidungsverfahrens der klassischen Logik.
Diophantine geometry over groups I : Makanin-Razborov diagrams
This paper is the first in a sequence on the structure of sets of solutions to systems of equations in a free group, projections of such sets, and the structure of elementary sets defined over a free group. In the first paper we present the (canonical) Makanin-Razborov diagram that encodes the set of solutions of a system of equations. We continue by studying parametric families of sets of solutions, and associate with such a family a canonical graded Makanin-Razborov diagram, that encodes the collection...
Diophantine undecidability for addition and divisibility in polynomial rings
We prove that the positive-existential theory of addition and divisibility in a ring of polynomials in two variables A[t₁,t₂] over an integral domain A is undecidable and that the universal-existential theory of A[t₁] is undecidable.
Embedding relations in the lattice of recursively enumerable sets.
Entscheidungsprobleme der Theorie zweier Äquivalenzrelationen mit beschränkter Zahl vоn Elementen in den Klassen
Errata to the paper "Remarks of the elementary theories of formal and convergent power series" Fundamenta Mathematicae 105 (1980), pp. 229-239
E-unification by means of tree tuple synchronized grammars.
Extensions of Büchi's problem: Questions of decidability for addition and kth powers
We generalize a question of Büchi: Let R be an integral domain, C a subring and k ≥ 2 an integer. Is there an algorithm to decide the solvability in R of any given system of polynomial equations, each of which is linear in the kth powers of the unknowns, with coefficients in C? We state a number-theoretical problem, depending on k, a positive answer to which would imply a negative answer to the question for R = C = ℤ. We reduce a negative answer for k = 2 and for...
Finiteness results on rewriting systems