ISSN:
1433-0490
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Notes:
Abstract LetF be a monoid and letA={A i i∈I} be a set of disjoint subsets ofF, whereI is an index set. A congruence onF is calledA-separating if each of its congruence classes has a non-empty intersection with at most one Ai ∈A The setC ′ A of allA-separating congruences onF is a lower semi-lattice with respect to the partial ordering of congruence inclusion. A necessary and sufficient condition forC ′ A to be a complete lattice is derived and, in that case, the unique maximalA-separating congruence is characterized. The relation ofA-separating congruences with automata is described. An example of the case that the unique maximalA-separating congruence on a free monoid exists is worked out, and its realization by an incompletely specified finite automaton is given.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01695166
