An Algebraic Approach to Incomparable Families of Formal Languages

Peter R.J. Asveld

    Research output: Chapter in Book/Report/Conference proceedingChapterAcademicpeer-review


    We extend some results of Ginsburg and Spanier [S. Ginsburg & E.H. Spanier, On incomparable Abstract Families of Languages (AFL), J. Comput. Systems Sci. 9 (1974) 88-108] on incomparable full AFL's (full Abstract Families of Languages) to similar structures like full hyper-AFL's, full hyper(1)-AFL's and prequasoids. A general approach based on universal algebra and lattice theory enables us to establish Ginsburg and Spanier-like theorems for several types of language families. It turns out that a considerable part of those proofs is algebraic or lattice-theoretic in nature. On the other hand formal language theory provides language families that may serve as (counter)examples in algebra. Keywords: lattice, universal algebra, family of languages, prequasoid, quasoid, full trio, full AFL (Abstract Family of Languages), full super-AFL, full hyper-AFL.
    Original languageEnglish
    Title of host publicationLindenmayer Systems
    Subtitle of host publicationImpacts on Theoretical Computer Science, Computer Graphics, and Developmental Biology
    EditorsGrzegorz Rozenberg, Arto Salomaa
    Place of PublicationBerlin
    Number of pages21
    ISBN (Electronic)978-3-642-58117-5
    ISBN (Print)978-3-642-63474-1
    Publication statusPublished - 1992


    • MSC-68Q45
    • HMI-SLT: Speech and Language Technology
    • MSC-08A70
    • Lattice
    • Universal algebra
    • Family of languages
    • Prequasoid
    • Quasoid
    • Full trio
    • full AFL (full Abstract Family of Languages)
    • Full super-AFL
    • Full hyper-AFL

    Cite this