ONE FAST ALGORITHM FOR FINDING AUTOMATON CONGRUENCES

摘要

Even though congruences on a finite automaton play an important role when investigating the structure of a given automaton, not much attention has been given to finding a fast algorithm for constructing them. This contribution brings a fast algorithm for construction the smallest congruence containing a given relation, which can be used for finding elementary congruences, i.e. congruences merging two distinct states.