On Free $\omega$-Continuous and Regular Ordered Algebras
We study varieties of certain ordered $\Sigma$-algebras with restricted completeness and continuity properties. We give a general characterization of their free algebras in terms of submonads of the monad of $\Sigma$-coterms. Varieties of this form are called \emph{quasi-regular}. For example, we sh...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Logical Methods in Computer Science e.V.
2019-10-01
|
| Series: | Logical Methods in Computer Science |
| Subjects: | |
| Online Access: | https://lmcs.episciences.org/2586/pdf |
| _version_ | 1797268561657331712 |
|---|---|
| author | Zoltan Esik Dexter Kozen |
| author_facet | Zoltan Esik Dexter Kozen |
| author_sort | Zoltan Esik |
| collection | DOAJ |
| description | We study varieties of certain ordered $\Sigma$-algebras with restricted
completeness and continuity properties. We give a general characterization of
their free algebras in terms of submonads of the monad of $\Sigma$-coterms.
Varieties of this form are called \emph{quasi-regular}. For example, we show
that if $E$ is a set of inequalities between finite $\Sigma$-terms, and if
$\mathcal{V}_\omega$ and $\mathcal{V}_\mathrm{reg}$ denote the varieties of all
$\omega$-continuous ordered $\Sigma$-algebras and regular ordered
$\Sigma$-algebras satisfying $E$, respectively, then the free
$\mathcal{V}_\mathrm{reg}$-algebra $F_\mathrm{reg}(X)$ on generators $X$ is the
subalgebra of the corresponding free $\mathcal{V}_\omega$-algebra $F_\omega(X)$
determined by those elements of $F_\omega(X)$ denoted by the regular
$\Sigma$-coterms. This is a special case of a more general construction that
applies to any quasi-regular family. Examples include the *-continuous Kleene
algebras, context-free languages, $\omega$-continuous semirings and
$\omega$-continuous idempotent semirings, OI-macro languages, and iteration
theories. |
| first_indexed | 2024-04-25T01:34:26Z |
| format | Article |
| id | doaj.art-610a89e9ca654cc18009c2bd86c555e3 |
| institution | Directory Open Access Journal |
| issn | 1860-5974 |
| language | English |
| last_indexed | 2024-04-25T01:34:26Z |
| publishDate | 2019-10-01 |
| publisher | Logical Methods in Computer Science e.V. |
| record_format | Article |
| series | Logical Methods in Computer Science |
| spelling | doaj.art-610a89e9ca654cc18009c2bd86c555e32024-03-08T10:29:38ZengLogical Methods in Computer Science e.V.Logical Methods in Computer Science1860-59742019-10-01Volume 15, Issue 410.23638/LMCS-15(4:4)20192586On Free $\omega$-Continuous and Regular Ordered AlgebrasZoltan EsikDexter KozenWe study varieties of certain ordered $\Sigma$-algebras with restricted completeness and continuity properties. We give a general characterization of their free algebras in terms of submonads of the monad of $\Sigma$-coterms. Varieties of this form are called \emph{quasi-regular}. For example, we show that if $E$ is a set of inequalities between finite $\Sigma$-terms, and if $\mathcal{V}_\omega$ and $\mathcal{V}_\mathrm{reg}$ denote the varieties of all $\omega$-continuous ordered $\Sigma$-algebras and regular ordered $\Sigma$-algebras satisfying $E$, respectively, then the free $\mathcal{V}_\mathrm{reg}$-algebra $F_\mathrm{reg}(X)$ on generators $X$ is the subalgebra of the corresponding free $\mathcal{V}_\omega$-algebra $F_\omega(X)$ determined by those elements of $F_\omega(X)$ denoted by the regular $\Sigma$-coterms. This is a special case of a more general construction that applies to any quasi-regular family. Examples include the *-continuous Kleene algebras, context-free languages, $\omega$-continuous semirings and $\omega$-continuous idempotent semirings, OI-macro languages, and iteration theories.https://lmcs.episciences.org/2586/pdfcomputer science - logic in computer science |
| spellingShingle | Zoltan Esik Dexter Kozen On Free $\omega$-Continuous and Regular Ordered Algebras Logical Methods in Computer Science computer science - logic in computer science |
| title | On Free $\omega$-Continuous and Regular Ordered Algebras |
| title_full | On Free $\omega$-Continuous and Regular Ordered Algebras |
| title_fullStr | On Free $\omega$-Continuous and Regular Ordered Algebras |
| title_full_unstemmed | On Free $\omega$-Continuous and Regular Ordered Algebras |
| title_short | On Free $\omega$-Continuous and Regular Ordered Algebras |
| title_sort | on free omega continuous and regular ordered algebras |
| topic | computer science - logic in computer science |
| url | https://lmcs.episciences.org/2586/pdf |
| work_keys_str_mv | AT zoltanesik onfreeomegacontinuousandregularorderedalgebras AT dexterkozen onfreeomegacontinuousandregularorderedalgebras |