{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,13]],"date-time":"2025-05-13T21:57:15Z","timestamp":1747173435514,"version":"3.40.5"},"reference-count":31,"publisher":"Cambridge University Press (CUP)","issue":"10","license":[{"start":{"date-parts":[[2021,6,23]],"date-time":"2021-06-23T00:00:00Z","timestamp":1624406400000},"content-version":"unspecified","delay-in-days":234,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Math. Struct. Comp. Sci."],"published-print":{"date-parts":[[2020,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>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 <jats:italic>S<\/jats:italic>-semimodule monad for finite and commutative semirings <jats:italic>S<\/jats:italic>, which generalises our earlier insight that the Vietoris monad on Boolean spaces is the codensity monad of the finite powerset functor.<\/jats:p>","DOI":"10.1017\/s0960129521000074","type":"journal-article","created":{"date-parts":[[2021,6,23]],"date-time":"2021-06-23T07:55:19Z","timestamp":1624434919000},"page":"1054-1088","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":1,"title":["Quantifiers on languages and codensity monads"],"prefix":"10.1017","volume":"30","author":[{"given":"Mai","family":"Gehrke","sequence":"first","affiliation":[]},{"given":"Daniela","family":"Petri\u015fan","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7331-7381","authenticated-orcid":false,"given":"Luca","family":"Reggio","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2021,6,23]]},"reference":[{"key":"S0960129521000074_ref8","unstructured":"Engelking, R. (1989). General Topology, 2nd edn., Sigma Series in Pure Mathematics, vol. 6, Berlin, Heldermann Verlag."},{"key":"S0960129521000074_ref5","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21500-6_1"},{"key":"S0960129521000074_ref12","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2017.8005140"},{"key":"S0960129521000074_ref10","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-14162-1_13"},{"key":"S0960129521000074_ref13","doi-asserted-by":"publisher","DOI":"10.1016\/0022-4049(71)90001-6"},{"key":"S0960129521000074_ref21","doi-asserted-by":"publisher","DOI":"10.1007\/BF02679444"},{"key":"S0960129521000074_ref20","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0036488"},{"key":"S0960129521000074_ref1","unstructured":"Ad\u00e1mek, J. , Chen, L.-T. , Milius, S. and Urbat, H. (2016a). Profinite monads, profinite equations and Reiterman\u2019s theorem. Preprint available at https:\/\/arxiv.org\/abs\/1511.02147."},{"key":"S0960129521000074_ref4","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-4049(96)00083-7"},{"key":"S0960129521000074_ref7","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53132-7_8"},{"key":"S0960129521000074_ref26","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0289-9"},{"key":"S0960129521000074_ref16","first-page":"332","article-title":"Codensity and the ultrafilter monad","volume":"28","author":"Leinster","year":"2013","journal-title":"Theory and Applications of Categories"},{"key":"S0960129521000074_ref24","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139195218"},{"key":"S0960129521000074_ref9","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70583-3_21"},{"key":"S0960129521000074_ref11","unstructured":"Gehrke, M. , Petri\u015fan, D. and Reggio, L. (2016). The Sch\u00fctzenberger product for syntactic spaces. In: ICALP, LIPIcs, vol. 55, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 112:1\u2013112:14."},{"key":"S0960129521000074_ref22","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpaa.2019.05.002"},{"key":"S0960129521000074_ref27","unstructured":"Straubing, H. and Th\u00e9rien, D. (2008). Modular quantifiers. In: Logic and Automata, Texts in Logic and Games, vol. 2, Amsterdam University Press, 613\u2013628."},{"key":"S0960129521000074_ref17","volume-title":"Categories for the Working Mathematician","volume":"5","author":"Mac Lane","year":"1998"},{"key":"S0960129521000074_ref2","doi-asserted-by":"crossref","unstructured":"Ad\u00e1mek, J. , Chen, L.-T. , Milius, S. and Urbat, H. (2016b). Profinite monads, profinite equations, and Reiterman\u2019s theorem. In: FoSSaCS, Lecture Notes in Computer Science, vol. 9634, Springer, 531\u2013547.","DOI":"10.1007\/978-3-662-49630-5_31"},{"key":"S0960129521000074_ref14","first-page":"1","article-title":"Monads on symmetric monoidal closed categories","volume":"21","author":"Kock","year":"1970","journal-title":"Journal of The Australian Mathematical Society"},{"key":"S0960129521000074_ref3","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2015.46"},{"key":"S0960129521000074_ref31","doi-asserted-by":"publisher","DOI":"10.1007\/BF01696886"},{"key":"S0960129521000074_ref30","doi-asserted-by":"publisher","DOI":"10.2168\/LMCS-3(1:4)2007"},{"key":"S0960129521000074_ref15","unstructured":"Kuratowski, K. (1966). Topology, Vol. I. New edition, revised and augmented. Translated from the French by J. Jaworowski. New York-London, Academic Press; Warsaw, Pa\u0144stwowe Wydawnictwo Naukowe."},{"key":"S0960129521000074_ref18","unstructured":"McNaughton, R. and Papert, S. (1971). Counter-Free Automata. Cambridge, MA-London, MIT Press. With an appendix by William Henneman, MIT Research Monograph, No. 65."},{"key":"S0960129521000074_ref19","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1951-0042109-4"},{"key":"S0960129521000074_ref23","doi-asserted-by":"crossref","unstructured":"Reutenauer, C. (1979). Sur les vari\u00e9t\u00e9s de langages et de monodes. In: Theoretical Computer Science (Fourth GI Conference, Aachen), Lecture Notes in Computer Science, vol. 67, Berlin-New York, Springer, 260\u2013265.","DOI":"10.1007\/3-540-09118-1_27"},{"key":"S0960129521000074_ref29","doi-asserted-by":"publisher","DOI":"10.1016\/0022-4049(72)90019-9"},{"volume-title":"Handbook of Categorical Algebra 2, Categories and Structures","year":"1994","author":"Borceux","key":"S0960129521000074_ref6"},{"key":"S0960129521000074_ref25","first-page":"37","article-title":"The theory of representations for Boolean algebras","volume":"40","author":"Stone","year":"1936","journal-title":"Transactions of the American Mathematical Society"},{"key":"S0960129521000074_ref28","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1995.1067"}],"container-title":["Mathematical Structures in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0960129521000074","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,9]],"date-time":"2021-07-09T14:21:01Z","timestamp":1625840461000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0960129521000074\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11]]},"references-count":31,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2020,11]]}},"alternative-id":["S0960129521000074"],"URL":"https:\/\/doi.org\/10.1017\/s0960129521000074","relation":{},"ISSN":["0960-1295","1469-8072"],"issn-type":[{"type":"print","value":"0960-1295"},{"type":"electronic","value":"1469-8072"}],"subject":[],"published":{"date-parts":[[2020,11]]},"assertion":[{"value":"\u00a9 The Author(s), 2021. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}]}}