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.
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.