Topological Aspects of Regular Languages

Nicholas Pippenger
Publishing date
May 1994
17 pages
We establish a number of new results (and rederive some old results) concerning regular languages, using essentially topological methods. Our development is based on the duality (established by Stone) between Boolean algebras and certain topological spaces (which are now called "Stone spaces"). (This duality does not seem to have been recognized in the literature on regular languages, even though it is well known that the regular languages over a fixed alphabet form a Boolean algebra and that the "implicit operations" with a fixed number of operands form a Stone space!) By exploiting this duality, we are able to obtain a much more accessible account of the Galois correspondence between varieties of regular languages (in the sense of Eilenberg) and certain sets of "implicit identities". The new results include an analogous Galois correspondence for a generalization of varieties, and an explicit characterization by means of closure conditions of the sets of implicit identities involved in these correspondences.