Quantifiers on languages and codensity monads

MaRDI QIDQ5144687zbMATH OpenFDO

Authors Mai Gehrke, Daniela Petrişan, Luca Reggio

Publication date 19 January 2021

Full work available at URL https://arxiv.org/abs/1702.08841, http://dl.acm.org/citation.cfm?id=3330075

Mathematics Subject Classification ID

Logic with extra quantifiers and operators (03C80) Stone spaces (Boolean spaces) and related structures (06E15) Monads (= standard construction, triple or triad), algebras for monads, homology and derived functors for monads (18C15) Algebraic theory of languages and automata (68Q70)

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.

Recommendations

• Quantifiers on languages and codensity monads
• Computational Semantics for Monadic Quantifiers
• Hierarchies of monadic generalized quantifiers
• Codensity and the ultrafilter monad
• scientific article; zbMATH DE number 1424044
• Syntax and semantics of quantitative type theory
• Recognisable languages over monads
• Languages for monoidal categories
• scientific article; zbMATH DE number 139984
• On the relations between monadic semantics

Cited in

(12)

• A duality theoretic view on limits of finite structures
• Whither semantics?
• Codensity, profiniteness and algebras of semiring-valued measures
• Recognisable languages over monads
• Computational Semantics for Monadic Quantifiers
• scientific article; zbMATH DE number 1036407 (Why is no real title available?)
• The Schützenberger product for syntactic spaces
• Quantifiers on languages and codensity monads
• Languages for monoidal categories
• Calculational design of a regular model checker by abstract interpretation
• A Cook's tour of duality in logic: from quantifiers, through Vietoris, to measures
• Monadic monadic second order logic

This page was built for publication: Quantifiers on languages and codensity monads

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5144687)