Incomparable Elements in Algebraic Lattices with Applications to Formal Language Theory

P.R.J. Asveld

    Research output: Book/ReportReportOther research output

    Abstract

    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.
    Original languageUndefined
    Place of PublicationEnschede
    PublisherUniversity of Twente, Department of Computer Science
    Number of pages22
    Publication statusPublished - 1989

    Keywords

    • EWI-6081
    • HMI-SLT: Speech and Language Technology

    Cite this