Structure in Computer Science primarily derives from the structure found in discrete finite mathematics. This includes the areas such as logic, set theory, and algebra. | |

CONGRUENCE RELATIONS |
Finite Transition Systems (FTS) are abstract structures consisting of a set of states, an input alphabet, an initial state and a transition function mapping state and letter pairs to states. By designating selected states as "final" or "accepting" states a FTS becomes a Finite State Automata (FSA). A congruence relation on a FTS is a partitioning of the states which preserves the transition structure. Two congruence relations always exist: the universal partition groups all states together and the identity relation which separates all states. Many questions about FTS and FSA, such as decomposition in simpler systems and minimization of states, are answered by studying the congruence relations of a system.
We are developing a web page which will allow a FTS to be specified and will compute the lattice of congruence relations and produce an image of the lattice such as the adjacent example. Until then you can view a QuickTime(TM) movie animating the lattice (0.5 meg) at the right. |