Quantifiers on languages and codensity monads
This paper contributes to the techniques of topoalgebraic recognition for languages beyond the regular setting as they relate to logic on words. In particular, we provide a general construction on recognisers corresponding to adding one layer of various kinds of quantifiers and prove a related Reute...
| Glavni autori: | , , |
|---|---|
| Format: | Conference item |
| Jezik: | English |
| Izdano: |
IEEE
2017
|
| _version_ | 1826297592971001856 |
|---|---|
| author | Gehrke, M Petrişan, D Reggio, L |
| author_facet | Gehrke, M Petrişan, D Reggio, L |
| author_sort | Gehrke, M |
| collection | OXFORD |
| description | This paper contributes to the techniques of topoalgebraic recognition for languages beyond the regular setting as they relate to logic on words. In particular, we provide a general construction on recognisers corresponding to adding one layer of various kinds of quantifiers and prove a related Reutenauer-type theorem. Our main tools are codensity monads and duality theory. Our construction yields, in particular, a new characterisation of the profinite monad of the free S-semimodule monad for finite and commutative semirings S, which generalises our earlier insight that the Vietoris monad on Boolean spaces is the codensity monad of the finite powerset functor. |
| first_indexed | 2024-03-07T04:34:00Z |
| format | Conference item |
| id | oxford-uuid:cf51ae11-2d4c-493c-ab9c-d1fecf65e2bd |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T04:34:00Z |
| publishDate | 2017 |
| publisher | IEEE |
| record_format | dspace |
| spelling | oxford-uuid:cf51ae11-2d4c-493c-ab9c-d1fecf65e2bd2022-03-27T07:41:36ZQuantifiers on languages and codensity monadsConference itemhttp://purl.org/coar/resource_type/c_5794uuid:cf51ae11-2d4c-493c-ab9c-d1fecf65e2bdEnglishSymplectic ElementsIEEE2017Gehrke, MPetrişan, DReggio, LThis paper contributes to the techniques of topoalgebraic recognition for languages beyond the regular setting as they relate to logic on words. In particular, we provide a general construction on recognisers corresponding to adding one layer of various kinds of quantifiers and prove a related Reutenauer-type theorem. Our main tools are codensity monads and duality theory. Our construction yields, in particular, a new characterisation of the profinite monad of the free S-semimodule monad for finite and commutative semirings S, which generalises our earlier insight that the Vietoris monad on Boolean spaces is the codensity monad of the finite powerset functor. |
| spellingShingle | Gehrke, M Petrişan, D Reggio, L Quantifiers on languages and codensity monads |
| title | Quantifiers on languages and codensity monads |
| title_full | Quantifiers on languages and codensity monads |
| title_fullStr | Quantifiers on languages and codensity monads |
| title_full_unstemmed | Quantifiers on languages and codensity monads |
| title_short | Quantifiers on languages and codensity monads |
| title_sort | quantifiers on languages and codensity monads |
| work_keys_str_mv | AT gehrkem quantifiersonlanguagesandcodensitymonads AT petrisand quantifiersonlanguagesandcodensitymonads AT reggiol quantifiersonlanguagesandcodensitymonads |