{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T06:22:35Z","timestamp":1742970155029,"version":"3.40.3"},"publisher-location":"Cham","reference-count":19,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030452308"},{"type":"electronic","value":"9783030452315"}],"license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A systematic theory of <jats:italic>structural limits<\/jats:italic> for finite models has been developed by Ne\u0161et\u0159il and Ossona de Mendez. It is based on the insight that the collection of finite structures can be embedded, via a map they call the <jats:italic>Stone pairing<\/jats:italic>, in a space of measures, where the desired limits can be computed. We show that a closely related but finer grained space of measures arises \u2014 via Stone-Priestley duality and the notion of types from model theory \u2014 by enriching the expressive power of first-order logic with certain \u201cprobabilistic operators\u201d. We provide a sound and complete calculus for this extended logic and expose the functorial nature of this construction.<\/jats:p><jats:p>The consequences are two-fold. On the one hand, we identify the logical gist of the theory of structural limits. On the other hand, our construction shows that the duality-theoretic variant of the Stone pairing captures the adding of a layer of quantifiers, thus making a strong link to recent work on semiring quantifiers in logic on words. In the process, we identify the model theoretic notion of <jats:italic>types<\/jats:italic> as the unifying concept behind this link. These results contribute to bridging the strands of logic in computer science which focus on semantics and on more algorithmic and complexity related areas, respectively.<\/jats:p>","DOI":"10.1007\/978-3-030-45231-5_16","type":"book-chapter","created":{"date-parts":[[2020,4,17]],"date-time":"2020-04-17T10:02:53Z","timestamp":1587117773000},"page":"299-318","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["A Duality Theoretic View on Limits of Finite Structures"],"prefix":"10.1007","author":[{"given":"Mai","family":"Gehrke","sequence":"first","affiliation":[]},{"given":"Tom\u00e1\u0161","family":"Jakl","sequence":"additional","affiliation":[]},{"given":"Luca","family":"Reggio","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,4,17]]},"reference":[{"key":"16_CR1","unstructured":"Abramsky, S.: Domain theory in logical form. Ann. Pure Appl. Logic 51, 1\u201377 (1991)"},{"key":"16_CR2","doi-asserted-by":"crossref","unstructured":"Abramsky, S., Dawar, A., Wang, P.: The pebbling comonad in finite model theory. In: 32nd Annual ACM\/IEEE Symposium on Logic in Computer Science, LICS. pp. 1\u201312 (2017)","DOI":"10.1109\/LICS.2017.8005129"},{"key":"16_CR3","doi-asserted-by":"crossref","unstructured":"Abramsky, S., Shah, N.: Relating Structure and Power: Comonadic semantics for computational resources. In: 27th EACSL Annual Conference on Computer Science Logic, CSL. pp. 2:1\u20132:17 (2018)","DOI":"10.1007\/978-3-030-00389-0_1"},{"key":"16_CR4","doi-asserted-by":"crossref","unstructured":"Gehrke, M., Grigorieff, S., Pin, J.-\u00c9.: Duality and equational theory of regular languages. In: Automata, languages and programming II, LNCS, vol.\u00a05126, pp. 246\u2013257. Springer, Berlin (2008)","DOI":"10.1007\/978-3-540-70583-3_21"},{"key":"16_CR5","doi-asserted-by":"crossref","unstructured":"Gehrke, M., Petri\u015fan, D., Reggio, L.: Quantifiers on languages and codensity monads. In: 32nd Annual ACM\/IEEE Symposium on Logic in Computer Science, LICS. pp. 1\u201312 (2017)","DOI":"10.1109\/LICS.2017.8005140"},{"key":"16_CR6","unstructured":"Gehrke, M., Petri\u015fan, D., Reggio, L.: Quantifiers on languages and codensity monads (2019), extended version. Submitted. Preprint available at https:\/\/arxiv.org\/abs\/1702.08841"},{"key":"16_CR7","unstructured":"Gehrke, M., Priestley, H.A.: Canonical extensions of double quasioperator algebras: an algebraic perspective on duality for certain algebras with binary operations. J. Pure Appl. Algebra 209(1), 269\u2013290 (2007)"},{"key":"16_CR8","doi-asserted-by":"crossref","unstructured":"Gehrke, M., Priestley, H.A.: Duality for double quasioperator algebras via their canonical extensions. Studia Logica 86(1), 31\u201368 (2007)","DOI":"10.1007\/s11225-007-9045-x"},{"key":"16_CR9","unstructured":"Goldblatt, R.: Varieties of complex algebras. Ann. Pure Appl. Logic 44(3), 173\u2013242 (1989)"},{"key":"16_CR10","unstructured":"van Gool, S.J., Steinberg, B.: Pro-aperiodic monoids via saturated models. In: 34th Symposium on Theoretical Aspects of Computer Science, STACS. pp. 39:1\u201339:14 (2017)"},{"key":"16_CR11","unstructured":"Johnstone, P.T.: Stone spaces, Cambridge Studies in Advanced Mathematics, vol.\u00a03. Cambridge University Press (1986), reprint of the 1982 edition"},{"key":"16_CR12","doi-asserted-by":"crossref","unstructured":"Jung, A.: Continuous domain theory in logical form. In: Coecke, B., Ong, L., Panangaden, P. (eds.) Computation, Logic, Games, and Quantum Foundations, Lecture Notes in Computer Science, vol.\u00a07860, pp. 166\u2013177. Springer Verlag (2013)","DOI":"10.1007\/978-3-642-38164-5_12"},{"key":"16_CR13","doi-asserted-by":"crossref","unstructured":"Kolaitis, P.G., Pichler, R., Sallinger, E., Savenkov, V.: Limits of schema mappings. Theory of Computing Systems 62(4), 899\u2013940 (2018)","DOI":"10.1007\/s00224-017-9812-7"},{"key":"16_CR14","unstructured":"Matz, O., Schweikardt, N.: Expressive power of monadic logics on words, trees, pictures, and graphs. In: Logic and Automata: History and Perspectives. pp. 531\u2013552 (2008)"},{"key":"16_CR15","unstructured":"Ne\u0161et\u0159il, J., Ossona\u00a0de Mendez, P.: A model theory approach to structural limits. Commentationes Mathematicae Universitatis Carolinae 53(4), 581\u2013603 (2012)"},{"key":"16_CR16","doi-asserted-by":"crossref","unstructured":"Ne\u0161et\u0159il, J., Ossona\u00a0de Mendez, P.: First-order limits, an analytical perspective. European Journal of Combinatorics 52, 368\u2013388 (2016)","DOI":"10.1016\/j.ejc.2015.07.012"},{"key":"16_CR17","doi-asserted-by":"crossref","unstructured":"Ne\u0161et\u0159il, J., Ossona\u00a0de Mendez, P.: A unified approach to structural limits and limits of graphs with bounded tree-depth (2020), to appear in Memoirs of the American Mathematical Society","DOI":"10.1090\/memo\/1272"},{"key":"16_CR18","unstructured":"Pin, J.-\u00c9.: Profinite methods in automata theory. In: 26th Symposium on Theoretical Aspects of Computer Science, STACS. pp. 31\u201350 (2009)"},{"key":"16_CR19","unstructured":"Priestley, H.A.: Representation of distributive lattices by means of ordered Stone spaces. Bull. London Math. Soc. 2, 186\u2013190 (1970)"}],"container-title":["Lecture Notes in Computer Science","Foundations of Software Science and Computation Structures"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-45231-5_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,1,7]],"date-time":"2021-01-07T13:39:59Z","timestamp":1610026799000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-45231-5_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030452308","9783030452315"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-45231-5_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2020]]},"assertion":[{"value":"17 April 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"FoSSaCS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Foundations of Software Science and Computation Structures","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Dublin","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Ireland","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2020","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"25 April 2020","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"30 April 2020","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"fossacs2020","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.etaps.org\/2020\/fossacs","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"98","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"31","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"32% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"12","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"The conference could not take place due to the COVID-19 pandemic. There was an online event on July 2, 2020.","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}