{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T15:29:04Z","timestamp":1743002944170,"version":"3.40.3"},"publisher-location":"Cham","reference-count":34,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030452360"},{"type":"electronic","value":"9783030452377"}],"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"},{"start":{"date-parts":[[2020,4,17]],"date-time":"2020-04-17T00:00:00Z","timestamp":1587081600000},"content-version":"vor","delay-in-days":107,"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>We study identification in the limit using polynomial time and data for models of <jats:inline-formula><jats:tex-math>$$\\omega $$<\/jats:tex-math><\/jats:inline-formula>-automata. On the negative side we show that non-deterministic <jats:inline-formula><jats:tex-math>$$\\omega $$<\/jats:tex-math><\/jats:inline-formula>-automata (of types B\u00fcchi, coB\u00fcchi, Parity or Muller) can not be polynomially learned in the limit. On the positive side we show that the <jats:inline-formula><jats:tex-math>$$\\omega $$<\/jats:tex-math><\/jats:inline-formula>-language classes <jats:inline-formula><jats:tex-math>$$\\mathbb {IB}$$<\/jats:tex-math><\/jats:inline-formula>, <jats:inline-formula><jats:tex-math>$$\\mathbb {IC}$$<\/jats:tex-math><\/jats:inline-formula>, <jats:inline-formula><jats:tex-math>$$\\mathbb {IP}$$<\/jats:tex-math><\/jats:inline-formula>, and <jats:inline-formula><jats:tex-math>$$\\mathbb {IM}$$<\/jats:tex-math><\/jats:inline-formula> that are defined by deterministic B\u00fcchi, coB\u00fcchi, parity, and Muller acceptors that are isomorphic to their right-congruence automata (that is, the right congruences of languages in these classes are fully informative) are identifiable in the limit using polynomial time and data. We further show that for these classes a characteristic sample can be constructed in polynomial time.<\/jats:p>","DOI":"10.1007\/978-3-030-45237-7_20","type":"book-chapter","created":{"date-parts":[[2020,4,17]],"date-time":"2020-04-17T10:02:53Z","timestamp":1587117773000},"page":"325-343","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Polynomial Identification of $$\\omega $$-Automata"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6907-2999","authenticated-orcid":false,"given":"Dana","family":"Angluin","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6015-4170","authenticated-orcid":false,"given":"Dana","family":"Fisman","sequence":"additional","affiliation":[]},{"given":"Yaara","family":"Shoval","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,4,17]]},"reference":[{"key":"20_CR1","doi-asserted-by":"crossref","unstructured":"Aarts, F., Vaandrager, F.: Learning I\/O automata. In: Gastin, P., Laroussinie, F. (eds.) CONCUR 2010 - Concurrency Theory: 21th International Conference, CONCUR 2010, Paris, France, August 31-September 3, 2010. Proceedings. pp. 71\u201385. Springer Berlin Heidelberg, Berlin, Heidelberg (2010)","DOI":"10.1007\/978-3-642-15375-4_6"},{"key":"20_CR2","unstructured":"Ammons, G., Bod\u00edk, R., Larus, J.R.: Mining specifications. In: Conference Record of POPL 2002: The 29th SIGPLAN-SIGACT Symposium on Principles of Programming Languages, Portland, OR, USA, January 16-18, 2002. pp. 4\u201316 (2002)"},{"key":"20_CR3","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 2020, January 13-16, 2020, Barcelona, Spain. pp. 8:1\u20138:17 (2020)"},{"key":"20_CR4","doi-asserted-by":"crossref","unstructured":"Angluin, D., Fisman, D.: Regular omega-languages with an informative right congruence. In: GandALF. EPTCS, vol.\u00a0277, pp. 265\u2013279 (2018)","DOI":"10.4204\/EPTCS.277.19"},{"issue":"2","key":"20_CR5","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/0890-5401(87)90052-6","volume":"75","author":"D Angluin","year":"1987","unstructured":"Angluin, D.: Learning regular sets from queries and counterexamples. Inf. Comput. 75(2), 87\u2013106 (1987)","journal-title":"Inf. Comput."},{"key":"20_CR6","unstructured":"Angluin, D., Boker, U., Fisman, D.: Families of DFAs as acceptors of omega-regular languages. In: 41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016, August 22-26, 2016 - Krak\u00f3w, Poland. pp. 11:1\u201311:14 (2016)"},{"key":"20_CR7","unstructured":"Angluin, D., Fisman, D.: Learning regular omega languages. In: Algorithmic Learning Theory - 25th International Conference, ALT 2014, Bled, Slovenia, October 8-10, 2014. Proceedings. pp. 125\u2013139 (2014)"},{"key":"20_CR8","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/j.tcs.2016.07.031","volume":"650","author":"D Angluin","year":"2016","unstructured":"Angluin, D., Fisman, D.: Learning regular omega languages. Theor. Comput. Sci. 650, 57\u201372 (2016)","journal-title":"Theor. Comput. Sci."},{"key":"20_CR9","unstructured":"Angluin, D., Fisman, D.: Polynomial time algorithms for inclusion and equivalence of deterministic omega acceptors. In: arXiv:2002.03191v2, cs.FL (2020)"},{"key":"20_CR10","unstructured":"Chalupar, G., Peherstorfer, S., Poll, E., de\u00a0Ruiter, J.: Automated reverse engineering using Lego\u00ae. In: 8th USENIX Workshop on Offensive Technologies (WOOT 14). USENIX Association, San Diego, CA (Aug 2014)"},{"key":"20_CR11","unstructured":"Chapman, M., Chockler, H., Kesseli, P., Kroening, D., Strichman, O., Tautschnig, M.: Learning the language of error. In: Automated Technology for Verification and Analysis - 13th International Symposium, ATVA 2015, Shanghai, China, October 12-15, 2015, Proceedings. pp. 114\u2013130 (2015)"},{"key":"20_CR12","unstructured":"Cho, C.Y., Babic, D., Shin, E.C.R., Song, D.: Inference and analysis of formal models of botnet command and control protocols. In: Proceedings of the 17th ACM Conference on Computer and Communications Security, CCS 2010, Chicago, Illinois, USA, October 4-8, 2010. pp. 426\u2013439 (2010)"},{"key":"20_CR13","doi-asserted-by":"crossref","unstructured":"Cobleigh, J.M., Giannakopoulou, D., P\u0103s\u0103reanu, C.S.: Learning assumptions for compositional verification. In: Proceedings of the 9th International Conference on Tools and Algorithms for the Construction and Analysis of Systems. pp. 331\u2013346. TACAS \u201903, Springer-Verlag, Berlin, Heidelberg (2003)","DOI":"10.1007\/3-540-36577-X_24"},{"key":"20_CR14","unstructured":"Drews, D., D\u2019Antoni, L.: Learning symbolic automata. In: Tools and Algorithms for the Construction and Analysis of Systems - 23rd International Conference, TACAS 2017, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2017, Uppsala, Sweden, April 22-29, 2017, Proceedings, Part I. pp. 173\u2013189 (2017)"},{"key":"20_CR15","doi-asserted-by":"crossref","unstructured":"Farzan, A., Chen, Y.F., Clarke, E., Tsay, Y.K., Wang, B.Y.: Extending automated compositional verification to the full class of omega-regular languages. In: TACAS. pp. 2\u201317 (2008)","DOI":"10.1007\/978-3-540-78800-3_2"},{"issue":"3","key":"20_CR16","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1016\/S0019-9958(78)90562-4","volume":"37","author":"EM Gold","year":"1978","unstructured":"Gold, E.M.: Complexity of automaton identification from given data. Information and Control 37(3), 302\u2013320 (1978)","journal-title":"Information and Control"},{"issue":"2","key":"20_CR17","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1006\/jcss.1996.0020","volume":"52","author":"SA Goldman","year":"1996","unstructured":"Goldman, S.A., Mathias, H.D.: Teaching a smarter learner. J. Comput. Syst. Sci. 52(2), 255\u2013267 (1996)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"20_CR18","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/j.entcs.2005.01.044","volume":"138","author":"P Habermehl","year":"2005","unstructured":"Habermehl, P., Vojnar, T.: Regular model checking using inference of regular languages. Electr. Notes Theor. Comput. Sci. 138(3), 21\u201336 (2005)","journal-title":"Electr. Notes Theor. Comput. Sci."},{"issue":"2","key":"20_CR19","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1023\/A:1007353007695","volume":"27","author":"C de la Higuera","year":"1997","unstructured":"de\u00a0la Higuera, C.: Characteristic sets for polynomial grammatical inference. Machine Learning 27(2), 125\u2013138 (1997)","journal-title":"Machine Learning"},{"key":"20_CR20","unstructured":"Howar, F., Steffen, B., Jonsson, B., Cassel, S.: Inferring canonical register automata. In: Verification, Model Checking, and Abstract Interpretation - 13th International Conference, VMCAI 2012, Philadelphia, PA, USA, January 22-24, 2012. Proceedings. pp. 251\u2013266 (2012)"},{"issue":"2","key":"20_CR21","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1145\/333979.333987","volume":"47","author":"O Kupferman","year":"2000","unstructured":"Kupferman, O., Vardi, M.Y., Wolper, P.: An automata-theoretic approach to branching-time model checking. J. ACM 47(2), 312\u2013360 (2000)","journal-title":"J. ACM"},{"key":"20_CR22","unstructured":"Li, Y., Chen, Y., Zhang, L., Liu, D.: A novel learning algorithm for b\u00fcchi automata based on family of dfas and classification trees. In: Tools and Algorithms for the Construction and Analysis of Systems - 23rd International Conference, TACAS 2017, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2017, Uppsala, Sweden, April 22-29, 2017, Proceedings, Part I. pp. 208\u2013226 (2017)"},{"issue":"2","key":"20_CR23","doi-asserted-by":"publisher","first-page":"316","DOI":"10.1006\/inco.1995.1070","volume":"118","author":"O Maler","year":"1995","unstructured":"Maler, O., Pnueli, A.: On the learnability of infinitary regular sets. Inf. Comput. 118(2), 316\u2013326 (1995)","journal-title":"Inf. Comput."},{"key":"20_CR24","unstructured":"Maler, O., Pnueli, A.: On the learnability of infinitary regular sets. In: Proceedings of the Fourth Annual Workshop on Computational Learning Theory, COLT 1991, Santa Cruz, California, USA, August 5-7, 1991. pp. 128\u2013136 (1991)"},{"key":"20_CR25","unstructured":"Manevich, R., Shoham, S.: Inferring program extensions from traces. In: ICGI. Proceedings of Machine Learning Research, vol.\u00a093, pp. 139\u2013154. PMLR (2018)"},{"key":"20_CR26","doi-asserted-by":"crossref","unstructured":"Margaria, T., Niese, O., Raffelt, H., Steffen, B.: Efficient test-based model generation for legacy reactive systems. In: HLDVT. pp. 95\u2013100. IEEE Computer Society (2004)","DOI":"10.1109\/HLDVT.2004.1431246"},{"key":"20_CR27","doi-asserted-by":"crossref","unstructured":"Nam, W., Alur, R.: Learning-based symbolic assume-guarantee reasoning with automatic decomposition. In: ATVA. Lecture Notes in Computer Science, vol.\u00a04218, pp. 170\u2013185. Springer (2006)","DOI":"10.1007\/11901914_15"},{"key":"20_CR28","doi-asserted-by":"crossref","unstructured":"Peled, D., Vardi, M.Y., Yannakakis, M.: Black box checking. In: FORTE. pp. 225\u2013240 (1999)","DOI":"10.1007\/978-0-387-35578-8_13"},{"key":"20_CR29","unstructured":"Schuts, M., Hooman, J., Vaandrager, F.W.: Refactoring of legacy software using model learning and equivalence checking: An industrial experience report. In: Integrated Formal Methods - 12th International Conference, IFM 2016, Reykjavik, Iceland, June 1-5, 2016, Proceedings. pp. 311\u2013325 (2016)"},{"issue":"3","key":"20_CR30","doi-asserted-by":"publisher","first-page":"434","DOI":"10.1016\/0022-0000(83)90051-X","volume":"27","author":"L Staiger","year":"1983","unstructured":"Staiger, L.: Finite-state omega-languages. J. Comput. Syst. Sci. 27(3), 434\u2013448 (1983)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"20_CR31","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1145\/2967606","volume":"60","author":"F Vaandrager","year":"2017","unstructured":"Vaandrager, F.: Model learning. Commun. ACM 60(2), 86\u201395 (2017)","journal-title":"Commun. ACM"},{"key":"20_CR32","unstructured":"Vardhan, A., Sen, K., Viswanathan, M., Agha, G.: Using language inference to verify omega-regular properties. In: Tools and Algorithms for the Construction and Analysis of Systems, 11th International Conference, TACAS 2005, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2005, Edinburgh, UK, April 4-8, 2005, Proceedings. pp. 45\u201360 (2005)"},{"key":"20_CR33","doi-asserted-by":"crossref","unstructured":"Vardi, M.Y.: An automata-theoretic approach to linear temporal logic. In: Banff Higher Order Workshop. Lecture Notes in Computer Science, vol.\u00a01043, pp. 238\u2013266. Springer (1995)","DOI":"10.1007\/3-540-60915-6_6"},{"key":"20_CR34","doi-asserted-by":"crossref","unstructured":"Wagner, K.W.: A hierarchy of regular sequence sets. In: 4th Symposium on Mathematical Foundations of Computer (MFCS). pp. 445\u2013449 (1975)","DOI":"10.1007\/3-540-07389-2_231"}],"container-title":["Lecture Notes in Computer Science","Tools and Algorithms for the Construction and Analysis of Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-45237-7_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,22]],"date-time":"2021-03-22T18:08:07Z","timestamp":1616436487000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-45237-7_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030452360","9783030452377"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-45237-7_20","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":"TACAS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Tools and Algorithms for the Construction and Analysis of Systems","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":"26","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"tacas2020","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.etaps.org\/2020\/tacas","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":"155","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":"40","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":"8","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":"26% - 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":"14","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)"}}]}}