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.
Quantifiers on languages and codensity monads / M. Gehrke, D. Petrisan, L. Reggio - In: LICS[s.l] : Institute of Electrical and Electronics Engineers (IEEE), 2017. - ISBN 978-1-5090-3019-4. - pp. 1-12 (( Intervento presentato al 32. convegno Annual ACM/IEEE Symposium on Logic in Computer Science : June 20-23 tenutosi a Reykjavik (Iceland) nel 2017 [10.1109/LICS.2017.8005140].
Quantifiers on languages and codensity monads
L. ReggioUltimo
2017
Abstract
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.File | Dimensione | Formato | |
---|---|---|---|
08005140.pdf
accesso riservato
Dimensione
423.09 kB
Formato
Adobe PDF
|
423.09 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.