Data types as lattices : retractions, closures and projections
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 questions for some dynamic properties of Petri nets [Abstract of thesis]
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 and forcing in E-recursion.
Definability degrees for classes in the alternative set theory
Definable hereditary families in the projective hierarchy
We show that if ℱ is a hereditary family of subsets of satisfying certain definable conditions, then the reals are precisely the reals α such that . This generalizes the results for measure and category. Appropriate generalization to the higher levels of the projective hierarchy is obtained under Projective Determinacy. Application of this result to the -encodable reals is also shown.
Degrees of dependence in the theory of semisets.
Degrees of interpretability
Degrees of unsolvability within a regressive isol
Degree-theoretic bounds on the Morley rank.
Derivation-Bounded Groups.
Descriptive set theoretical complexity of randomness notions
We study the descriptive set theoretical complexity of various randomness notions.
Determinateness in the low protective hierarchy
Die m-Grade logischer Entscheidungsprobleme.
Die mit Nestedstackautomaten berechenbaren Funktionen sind elementar.
Die Nichtaxiomatisierbarkeit der unendlichwertigen Mengenlehre.
Die Unentscheidbarkeit der einstelligen unendlichwertigen Prädikatenlogik.
Different levels of word problems for some varieties.