-quasiminimal enumeration degrees.
Call-by-value solvability
Call-by-value Solvability
The notion of solvability in the call-by-value λ-calculus is defined and completely characterized, both from an operational and a logical point of view. The operational characterization is given through a reduction machine, performing the classical β-reduction, according to an innermost strategy. In fact, it turns out that the call-by-value reduction rule is too weak for capturing the solvability property of terms. The logical characterization is given through an intersection type assignment system,...
Caractérisation algébrique des groupes de type fini ayant un problème de mots résoluble (théorème de Boone-Higman, travaux de B. H. Neumann et MacIntyre)
Catégories de Peano et catégories algorithmiques, récursivité
Characterizing the polynomial hierarchy by alternating auxiliary pushdown automata
Charakterisierung der Aufzählungsreduzierbarkeit.
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...
Closedness properties and decision problems for finite multi-tape automata
Coding in the existential theory of concatenation.
Coherent randomness tests and computing the -trivial sets
We introduce Oberwolfach randomness, a notion within Demuth’s framework of statistical tests with moving components; here the components’ movement has to be coherent across levels. We show that a ML-random set computes all -trivial sets if and only if it is not Oberwolfach random, and indeed that there is a -trivial set which is not computable from any Oberwolfach random set. We show that Oberwolfach random sets satisfy effective versions of almost-everywhere theorems of analysis, such as the...
Combinatorial systems defined over one- and two-letter alphabets.
Combined complexity classes for finite functions
Comparing sets of the Baire space by means of general recursive operators
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...
Comparisons between some generalizations of recursion theory
Complete index sets of recursively enumerable families
Complexité de l'arboricité linéaire d'un graphe
Complexity of some natural problems in automatic structures.