RATIONAL SPACES AND SET CONSTRAINTS

Set constraints are inclusions between expressions denoting sets of gr ound terms. They have been used extensively in program analysis and ty pe inference. In this paper we investigate the topological structure o f the spaces of solutions to systems of set constraints. We identify a family of topological spaces called rational spaces, which formalize the notion of a topological space with a regular or self-similar struc ture, such as the Canter discontinuum or the space of runs of a finite automaton. We develop the basic theory of rational spaces and derive generalizations and proofs from topological principles of some results in the literature on set constraints.