Technical Reports

The ICICS/CS Reading Room


UBC CS TR-94-14 Summary

Topological Aspects of Regular Languages, May 1994 Nicholas Pippenger, 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.


If you have any questions or comments regarding this page please send mail to help@cs.ubc.ca.