Das Entscheidungsproblem der Klasse von Formeln, die höchstens zwei Primformeln enthalten.
Data types as lattices : retractions, closures and projections
De beaux groupes
Dans une belle paire de modèles d’une théorie stable ayant élimination des imaginaires sans la propriété de recouvrement fini, tout groupe définissable se projette, à isogénie près, sur les points -rationnels d’un groupe définissable dans le réduit à paramètres dans . Le noyau de cette projection est un groupe définissable dans le réduit.Un groupe interprétable dans une paire de corps algébriquement clos où est une extension propre de est, à isogénie près, l’extension des points -rationnels...
De la notion d'opération à celle d'opérateur ou à la recherche de formalismes intrinsèques
De l'infinitésimal au local (Thèse de Doctorat d'État)
De Morgan's and strong De Morgan's laws in a topos of shaves
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 code properties
We explore the borderline between decidability and undecidability of the following question: “Let C be a class of codes. Given a machine of type X, is it decidable whether the language lies in C or not?” for codes in general, ω-codes, codes of finite and bounded deciphering delay, prefix, suffix and bi(pre)fix codes, and for finite automata equipped with different versions of push-down stores and counters.
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.
Decidability questions for some dynamic properties of Petri nets [Abstract of thesis]
Decidable Theories of Preordered Fields.
Deciding inclusion of set constants over infinite non-strict data structures
Various static analyses of functional programming languages that permit infinite data structures make use of set constants like Top, Inf, and Bot, denoting all terms, all lists not eventually ending in Nil, and all non-terminating programs, respectively. We use a set language that permits union, constructors and recursive definition of set constants with a greatest fixpoint semantics in the set of all, also infinite, computable trees, where all term constructors are non-strict. This...
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...