{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T23:24:41Z","timestamp":1742945081310,"version":"3.40.3"},"publisher-location":"Cham","reference-count":21,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030992521"},{"type":"electronic","value":"9783030992538"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,3,29]],"date-time":"2022-03-29T00:00:00Z","timestamp":1648512000000},"content-version":"vor","delay-in-days":87,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We explore the suitability of mod 2 multiplicity automata (M2MAs) as a representation for regular languages of infinite words. M2MAs are a deterministic representation that is known to be learnable in polynomial time with membership and equivalence queries, in contrast to many other representations. Another advantage of M2MAs compared to non-deterministic automata is that their equivalence can be decided in polynomial time and complementation incurs only an additive constant size increase. Because learning time is parameterized by the size of the representation, particular attention is focused on the relative succinctness of alternate representations, in particular, LTL formulas and B\u00fcchi automata of the types: deterministic, non-deterministic and strongly unambiguous. We supplement the theoretical results of worst case upper and lower bounds with experimental results computed for randomly generated automata and specific families of LTL formulas.<\/jats:p>","DOI":"10.1007\/978-3-030-99253-8_1","type":"book-chapter","created":{"date-parts":[[2022,3,28]],"date-time":"2022-03-28T20:02:48Z","timestamp":1648497768000},"page":"1-20","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Representing Regular Languages of Infinite Words Using Mod 2 Multiplicity Automata"],"prefix":"10.1007","author":[{"given":"Dana","family":"Angluin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Timos","family":"Antonopoulos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dana","family":"Fisman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nevin","family":"George","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,3,29]]},"reference":[{"unstructured":"Angluin, D., Antonopoulos, T., Fisman, D.: Strongly unambiguous B\u00fcchi automata are polynomially predictable with membership queries. In: 28th EACSL Annual Conference on Computer Science Logic, CSL. pp. 8:1\u20138:17 (2020)","key":"1_CR1"},{"doi-asserted-by":"crossref","unstructured":"Angluin, D., Fisman, D.: Learning regular omega languages. Theor. Comput. Sci. 650, 57\u201372 (2016)","key":"1_CR2","DOI":"10.1016\/j.tcs.2016.07.031"},{"unstructured":"Baier, C., Katoen, J.: Principles of Model Checking. MIT Press (2008)","key":"1_CR3"},{"doi-asserted-by":"crossref","unstructured":"Beimel, A., Bergadano, F., Bshouty, N.H., Kushilevitz, E., Varricchio, S.: Learning functions represented as multiplicity automata. J. ACM 47(3), 506\u2013530 (May 2000)","key":"1_CR4","DOI":"10.1145\/337244.337257"},{"doi-asserted-by":"crossref","unstructured":"Bergadano, F., Varricchio, S.: Learning behaviors of automata from multiplicity and equivalence queries. SIAM J. Comput. 25(6), 1268\u20131280 (1996)","key":"1_CR5","DOI":"10.1137\/S009753979326091X"},{"doi-asserted-by":"publisher","unstructured":"Bousquet, N., L\u00f6ding, C.: Equivalence and inclusion problem for strongly unambiguous B\u00fcchi automata. In: Language and Automata Theory and Applications, 4th International Conference, LATA. Proceedings. pp. 118\u2013129 (2010). https:\/\/doi.org\/10.1007\/978-3-642-13089-2_10","key":"1_CR6","DOI":"10.1007\/978-3-642-13089-2_10"},{"doi-asserted-by":"crossref","unstructured":"Calbrix, H., Nivat, M., Podelski, A.: Ultimately periodic words of rational w-languages. In: Proceedings of the 9th International Conference on Mathematical Foundations of Programming Semantics. pp. 554\u2013566. Springer-Verlag (1994)","key":"1_CR7","DOI":"10.1007\/3-540-58027-1_27"},{"doi-asserted-by":"publisher","unstructured":"Carton, O., Michel, M.: Unambiguous B\u00fcchi automata. Theor. Comput. Sci. 297(1-3), 37\u201381 (2003). https:\/\/doi.org\/10.1016\/S0304-3975(02)00618-7","key":"1_CR8","DOI":"10.1016\/S0304-3975(02)00618-7"},{"unstructured":"Diekert, V., Gastin, P.: First-order definable languages. In: Logic and Automata: History and Perspectives [in Honor of Wolfgang Thomas]. pp. 261\u2013306 (2008)","key":"1_CR9"},{"doi-asserted-by":"crossref","unstructured":"Droste, M., Kuich, W., Vogler, H. (eds.): Handbook of Weighted Automata, chap. 4: Rational and Recognizable Series, by Jaques Sakarovitch, pp. 105\u2013174. Springer-Verlag Berlin Heidelberg (2009)","key":"1_CR10","DOI":"10.1007\/978-3-642-01492-5_4"},{"doi-asserted-by":"publisher","unstructured":"Gerth, R., Peled, D., Vardi, M., Wolper, P.: Simple on-the-fly automatic verification of linear temporal logic. In: Protocol Specification, Testing and Verification XV. PSTV 1995. Springer (1996). https:\/\/doi.org\/10.1007\/978-0-387-34892-6_1","key":"1_CR11","DOI":"10.1007\/978-0-387-34892-6_1"},{"doi-asserted-by":"crossref","unstructured":"Hromkovi\u010d, J.: Communication Complexity and Parallel Computing. Springer-Verlag Berlin Heidelberg (1997), (There is also 2013 edition.)","key":"1_CR12","DOI":"10.1007\/978-3-662-03442-2"},{"doi-asserted-by":"crossref","unstructured":"Kaznatcheev, A., Panangaden, P.: Weighted automata are compact and actively learnable. Information Processing Letters 171 (2021), (The authors were apparently unaware of prior results on learning multiplicity automata by Beimel et al. and others.)","key":"1_CR13","DOI":"10.1016\/j.ipl.2021.106133"},{"doi-asserted-by":"crossref","unstructured":"Kuperberg, D., Pinault, L., Pous, D.: Coinductive algorithms for B\u00fcchi automata. In: Developments in Language Theory - 23rd International Conference, DLT Proceedings. pp. 206\u2013220 (2019)","key":"1_CR14","DOI":"10.1007\/978-3-030-24886-4_15"},{"doi-asserted-by":"publisher","unstructured":"Manna, Z., Pnueli, A.: A hierarchy of temporal properties (invited paper, 1989). In: Proceedings of the Ninth Annual ACM Symposium on Principles of Distributed Computing. p. 377\u2013410. PODC \u201990, Association for Computing Machinery (1990). https:\/\/doi.org\/10.1145\/93385.93442","key":"1_CR15","DOI":"10.1145\/93385.93442"},{"unstructured":"Michel, M.: Complementation is much more difficult with automata on infinite words. In: Manuscript, CNET (1988)","key":"1_CR16"},{"doi-asserted-by":"crossref","unstructured":"Moser, B.K.: Linear algebra and related introductory topics. In: Linear Models, A Mean Model Approach, A volume in Probability and Mathematical Statistics. pp. 1\u201322 (1996)","key":"1_CR17","DOI":"10.1016\/B978-012508465-9\/50001-6"},{"doi-asserted-by":"crossref","unstructured":"Pnueli, A.: The temporal logic of programs. In: FOCS. pp. 46\u201357 (1977)","key":"1_CR18","DOI":"10.1109\/SFCS.1977.32"},{"doi-asserted-by":"crossref","unstructured":"Sakarovitch, J.: Elements of Automata Theory. Cambridge University Press, USA (2009)","key":"1_CR19","DOI":"10.1017\/CBO9781139195218"},{"doi-asserted-by":"publisher","unstructured":"Vardi, M.Y.: An automata-theoretic approach to linear temporal logic. In: Logics for Concurrency - Structure versus Automata (8th Banff Higher Order Workshop, Banff, Canada, August 27 - September 3, 1995, Proceedings). pp. 238\u2013266 (1995). https:\/\/doi.org\/10.1007\/3-540-60915-6_6","key":"1_CR20","DOI":"10.1007\/3-540-60915-6_6"},{"unstructured":"Wilke, T.: $$\\omega $$-automata. CoRR abs\/1609.03062 (2016), http:\/\/arxiv.org\/abs\/1609.03062","key":"1_CR21"}],"container-title":["Lecture Notes in Computer Science","Foundations of Software Science and Computation Structures"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-99253-8_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,3,28]],"date-time":"2022-03-28T20:03:50Z","timestamp":1648497830000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-99253-8_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783030992521","9783030992538"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-99253-8_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"29 March 2022","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":"Munich","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Germany","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"4 April 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"6 April 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"25","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"fossacs2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/etaps.org\/2022\/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":"77","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":"23","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":"30% - 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":"9","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)"}}]}}