Journal article
Quantifiers on languages and codensity monads
- Abstract:
- This paper contributes to the techniques of topo-algebraic 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 corresponding Reutenauer-type theorem. Our main tools are codensity monads and duality theory. Our construction hinges on a measure-theoretic 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.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Accepted manuscript, 790.2KB, Terms of use)
-
- Publisher copy:
- 10.1017/S0960129521000074
Authors
- Publisher:
- Cambridge University Press
- Journal:
- Mathematical Structures in Computer Science More from this journal
- Volume:
- 30
- Issue:
- 10
- Pages:
- 1054-1088
- Publication date:
- 2021-06-23
- Acceptance date:
- 2021-05-01
- DOI:
- EISSN:
-
1469-8072
- ISSN:
-
0960-1295
- Language:
-
English
- Keywords:
- Pubs id:
-
1175087
- Local pid:
-
pubs:1175087
- Deposit date:
-
2021-05-08
Terms of use
- Copyright holder:
- Gehrke et al.
- Copyright date:
- 2021
- Rights statement:
- © The Author(s), 2021. Published by Cambridge University Press
- Notes:
- This is the accepted manuscript version of the article. The final version is available online from Cambridge University Press at: https://doi.org/10.1017/S0960129521000074
If you are the owner of this record, you can report an update to it here: Report update to this record