Abstract
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 language | English |
|---|---|
| Title of host publication | Lindenmayer Systems |
| Subtitle of host publication | Impacts on Theoretical Computer Science, Computer Graphics, and Developmental Biology |
| Editors | Grzegorz Rozenberg, Arto Salomaa |
| Place of Publication | Berlin |
| Publisher | Springer |
| Pages | 455-475 |
| Number of pages | 21 |
| ISBN (Electronic) | 978-3-642-58117-5 |
| ISBN (Print) | 978-3-642-63474-1 |
| DOIs | |
| Publication status | Published - 1992 |
Keywords
- 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