Investigations into the Expressiveness of First-order Logic and Weak Path Automata on Infinite Trees
Chase Ford

Abstract:
In this thesis, we investigate the expressive power of first-order logic and alternating parity automata on unranked trees with no leaves. While the initial aim of this thesis was to provide a full characterization of first-order logic as a class of automata, slightly less is achieved. In particular, we introduce several closely related classes of alternating parity automata and prove that they effectively bound the expressive power of first-order logic over such structures. Inspired by automata-theoretic characterizations of first-order logic over word structures, the automata classes considered in this thesis are obtained by imposing weak acceptance conditions, antisymmetry of the reachability relation on states (also known as aperiodicity), and what we call the path condition. The essence of the latter is the semantic notion of complete additivity. In the final chapter, we investigate the bisimulation-invariant subclass of the lower bound of the first-order ‘sandwich’ given in this thesis using methods developed in the work of Janin and Walukiewicz.