Search

(Labelled) transition systems are relatively common in theoretical computer science, chiefly as vehicles for operational semantics. The first part of this paper constructs a hierarchy of canonical transition systems and associated maps, aiming to give a strongly extensional theory of transition systems, where any two points with equivalent behaviors are identified. The cornerstone of the development is a notion of convergence in arbitrary transition systems, generalizing the idea of finite (n-step) approximations to a given point. In particular, our canonical transition systems are also uniform spaces. The resulting hierarchy has very rich combinatorial (and topological) structure, and a lot of the first part of the paper is devoted to its study. We also discuss fixed points in this framework. In the second part of the paper, we show how to obtain a model of set theory with Aczel's Anti-Foundation Axiom (AFA) from canonical transition systems constructed earlier. We study further the structure of the model thus obtained, and also give a few more abstract results, concerning consistency and independence in the presence of AFA.