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.
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...