Two special types of algebraic (or compactly generated) lattices -- called A1- and A2-lattice -- are introduced. These lattices are uncountable, and each element in these lattices, apart from the zero and unit, possesses an incomparable element. The main results characterize those elements that have a largest incomparable element. Then two particular kinds of algebras -- called A1- and A2-algebra -- are defined and it is shown that the lattice of subalgebras of an A1-algebra [A2-algebra] is an A1-lattice [A2-lattice, respectively]. These results are established in order to apply them in formal language theory; viz. they yield necessary and sufficient conditions for a language family to possess a largest incomparable ``similar'' language family. On the other hand formal language theory provides language families that may serve as (counter)example in algebra. In this way we show that, although each A2-algebra [A2-lattice] is an A1-algebra [A1-lattice, respectively], the converse implication does not hold.
|Place of Publication||Enschede|
|Publisher||University of Twente, Department of Computer Science|
|Number of pages||22|
|Publication status||Published - 1989|
- HMI-SLT: Speech and Language Technology