A calculus for finitely satisfiable formulas with identity.
A certain reducibility on admissible sets.
A characterization of determinacy for Turing degree games
A characterization of generalized Rudin-Shapiro sequences with values in a locally compact abelian group
A characterization of r-maximal sets.
A Characterization of the Veblen-Schütte Functions by Means of Functionals
A classification of an iterative hierarchy.
A classification of the one-argument primitive recursive functions.
A classification of the ordinal recursive functions.
A combinatorial analysis of functions provably recursive in
A complete characterization of primitive recursive intensional behaviours
We give a complete characterization of the class of functions that are the intensional behaviours of primitive recursive (PR) algorithms. This class is the set of primitive recursive functions that have a null basic case of recursion. This result is obtained using the property of ultimate unarity and a geometrical approach of sequential functions on N the set of positive integers.
A conjecture of Ershov for a relative hierarchy fails near .
A decidable -categorical theory with a non-recursive Ryll-Nardzewski function
A deterministic subclass of context-free languages
A few results on the complexity of classes of identifiable recursive function sets
A Game Theoretical Approach to The Algebraic Counterpart of The Wagner Hierarchy : Part II
The algebraic counterpart of the Wagner hierarchy consists of a well-founded and decidable classification of finite pointed ω-semigroups of width 2 and height ωω. This paper completes the description of this algebraic hierarchy. We first give a purely algebraic decidability procedure of this partial ordering by introducing a graph representation of finite pointed ω-semigroups allowing to compute their precise Wagner degrees. The Wagner degree of any ω-rational language can therefore be computed...
A game theoretical approach to the algebraic counterpart of the Wagner hierarchy : Part I
The algebraic study of formal languages shows that ω-rational sets correspond precisely to the ω-languages recognizable by finite ω-semigroups. Within this framework, we provide a construction of the algebraic counterpart of the Wagner hierarchy. We adopt a hierarchical game approach, by translating the Wadge theory from the ω-rational language to the ω-semigroup context. More precisely, we first show that the Wagner degree is indeed a syntactic invariant. We then define a reduction relation on...
A generalization of elementary formal systems
A generalized Feiner hierarchy.
A Hierarchy of Automatic ω-Words having a Decidable MSO Theory
We investigate automatic presentations of ω-words. Starting points of our study are the works of Rigo and Maes, Caucal, and Carton and Thomas concerning lexicographic presentation, MSO-interpretability in algebraic trees, and the decidability of the MSO theory of morphic words. Refining their techniques we observe that the lexicographic presentation of a (morphic) word is in a certain sense canonical. We then generalize our techniques to a hierarchy of classes of ω-words enjoying the above...