Fibrations and recursivity
Finite alogorithmic procedures and computation theories.
Finite alogorithmic procedures and inductive definability.
Finite models and finitely many variables
This paper is a survey of results on finite variable logics in finite model theory. It focusses on the common underlying techniques that unite many such results.
Finiteness results on rewriting systems
First-order properties of trees, star-free expressions, and aperiodicity
Fixpoint alternation : arithmetic, transition systems, and the binary tree
Fixpoint alternation: arithmetic, transition systems, and the binary tree
We provide an elementary proof of the fixpoint alternation hierarchy in arithmetic, which in turn allows us to simplify the proof of the modal mu-calculus alternation hierarchy. We further show that the alternation hierarchy on the binary tree is strict, resolving a problem of Niwiński.
Fractions continues limitées et théorie des langages
Function operators spanning the arithmetical and the polynomial hierarchy
A modified version of the classical µ-operator as well as the first value operator and the operator of inverting unary functions, applied in combination with the composition of functions and starting from the primitive recursive functions, generate all arithmetically representable functions. Moreover, the nesting levels of these operators are closely related to the stratification of the arithmetical hierarchy. The same is shown for some further function operators known from computability and complexity theory....
Functions provably total in
Functions provably total in