{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T15:47:05Z","timestamp":1743090425838,"version":"3.40.3"},"publisher-location":"Cham","reference-count":23,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031787089"},{"type":"electronic","value":"9783031787096"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025]]},"DOI":"10.1007\/978-3-031-78709-6_13","type":"book-chapter","created":{"date-parts":[[2025,1,31]],"date-time":"2025-01-31T22:10:35Z","timestamp":1738361435000},"page":"257-278","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Query Learning Bounds for\u00a0Advice and\u00a0Nominal Automata"],"prefix":"10.1007","author":[{"given":"Kevin","family":"Zhou","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,2,1]]},"reference":[{"key":"13_CR1","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, 87\u2013106 (1987)","journal-title":"Inf. Comput."},{"key":"13_CR2","doi-asserted-by":"publisher","unstructured":"Angluin, D., Fisman, D.: Learning regular omega languages. Theoret. Comput. Sci. 650, 57\u201372 (2016). https:\/\/doi.org\/10.1016\/j.tcs.2016.07.031, https:\/\/www.sciencedirect.com\/science\/article\/pii\/S0304397516303760, algorithmic Learning Theory","DOI":"10.1016\/j.tcs.2016.07.031"},{"key":"13_CR3","doi-asserted-by":"publisher","unstructured":"Balc\u00e1zar, J.L., Castro, J., Guijarro, D., Simon, H.U.: The consistency dimension and distribution-dependent learning from queries. Theoretical Computer Science 288(2), 197\u2013215 (2002). https:\/\/doi.org\/10.1016\/S0304-3975(01)00400-5, https:\/\/www.sciencedirect.com\/science\/article\/pii\/S0304397501004005, algorithmic Learning Theory","DOI":"10.1016\/S0304-3975(01)00400-5"},{"key":"13_CR4","doi-asserted-by":"publisher","unstructured":"B\u00e1r\u00e1ny, V.: A hierarchy of automatic $$\\omega $$-words having a decidable MSO theory. RAIRO - Theoret. Inform. Appl. - Informatique Th\u00e9orique et Applications 42(3), 417\u2013450 (2008). https:\/\/doi.org\/10.1051\/ita:2008008, http:\/\/www.numdam.org\/articles\/10.1051\/ita:2008008\/","DOI":"10.1051\/ita:2008008"},{"key":"13_CR5","doi-asserted-by":"publisher","unstructured":"Boja\u0144czyk, M., Klin, B., Lasota, S.: Automata theory in nominal sets. Log. Meth. Comput. Sci. 10(3) (2014). https:\/\/doi.org\/10.2168\/LMCS-10(3:4)2014, https:\/\/lmcs.episciences.org\/1157","DOI":"10.2168\/LMCS-10(3:4)2014"},{"key":"13_CR6","unstructured":"Bollig, B., Habermehl, P., Kern, C., Leucker, M.: Angluin-style learning of NFA. In: IJCAI, pp. 1004\u20131009 (2009)"},{"key":"13_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1007\/3-540-44612-5_23","volume-title":"Mathematical Foundations of Computer Science 2000","author":"O Carton","year":"2000","unstructured":"Carton, O., Thomas, W.: The monadic theory of morphic infinite words and generalizations. In: Nielsen, M., Rovan, B. (eds.) MFCS 2000. LNCS, vol. 1893, pp. 275\u2013284. Springer, Heidelberg (2000). https:\/\/doi.org\/10.1007\/3-540-44612-5_23"},{"key":"13_CR8","unstructured":"Chase, H., Freitag, J.: Bounds in query learning. In: Abernethy, J., Agarwal, S. (eds.) Proceedings of Thirty Third Conference on Learning Theory. Proceedings of Machine Learning Research, vol.\u00a0125, pp. 1142\u20131160. PMLR (2020). http:\/\/proceedings.mlr.press\/v125\/chase20a.html"},{"key":"13_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1007\/978-3-662-54577-5_10","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems","author":"S Drews","year":"2017","unstructured":"Drews, S., D\u2019Antoni, L.: Learning symbolic automata. In: Legay, A., Margaria, T. (eds.) TACAS 2017. LNCS, vol. 10205, pp. 173\u2013189. Springer, Heidelberg (2017). https:\/\/doi.org\/10.1007\/978-3-662-54577-5_10"},{"key":"13_CR10","doi-asserted-by":"publisher","first-page":"169","DOI":"10.2307\/2269808","volume":"31","author":"CC Elgot","year":"1966","unstructured":"Elgot, C.C., Rabin, M.: Decidability and undecidability of extensions of second (first) order theory of (generalized) successor. J. Symb. Log. 31, 169\u2013181 (1966)","journal-title":"J. Symb. Log."},{"key":"13_CR11","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1007\/978-3-031-19992-9_17","volume-title":"Automated Technology for Verification and Analysis","author":"D Fisman","year":"2022","unstructured":"Fisman, D., Saadon, S.: Learning and characterizing fully-ordered lattice automata. In: Bouajjani, A., Hol\u00edk, L., Wu, Z. (eds.) Automated Technology for Verification and Analysis. LNCS, vol. 13505, pp. 266\u2013282. Springer, Cham (2022). https:\/\/doi.org\/10.1007\/978-3-031-19992-9_17"},{"issue":"3","key":"13_CR12","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1007\/s001650200016","volume":"13","author":"MJ Gabbay","year":"2002","unstructured":"Gabbay, M.J., Pitts, A.M.: A new approach to abstract syntax with variable binding. Formal Aspects Comput. 13(3), 341\u2013363 (2002). https:\/\/doi.org\/10.1007\/s001650200016","journal-title":"Formal Aspects Comput."},{"key":"13_CR13","unstructured":"Hanneke, S., Livni, R., Moran, S.: Online learning with simple predictors and a combinatorial characterization of minimax in 0\/1 games. In: COLT (2021)"},{"issue":"5","key":"13_CR14","doi-asserted-by":"publisher","first-page":"840","DOI":"10.1145\/234752.234755","volume":"43","author":"L Hellerstein","year":"1996","unstructured":"Hellerstein, L., Pillaipakkamnatt, K., Raghavan, V., Wilkins, D.: How many queries are needed to learn? J. ACM 43(5), 840\u2013862 (1996). https:\/\/doi.org\/10.1145\/234752.234755","journal-title":"J. ACM"},{"key":"13_CR15","doi-asserted-by":"publisher","unstructured":"Kruckman, A., Rubin, S., Sheridan, J., Zax, B.: A myhill-nerode theorem for automata with advice. Electron. Proc. Theoret. Comput. Sci. 96 (2012). https:\/\/doi.org\/10.4204\/EPTCS.96.18","DOI":"10.4204\/EPTCS.96.18"},{"key":"13_CR16","doi-asserted-by":"publisher","unstructured":"Moerman, J., Sammartino, M., Silva, A., Klin, B., Szynwelski, M.: Learning nominal automata. In: Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages, New York, NY, USA, pp. 613\u2013625. POPL 2017, Association for Computing Machinery (2017). https:\/\/doi.org\/10.1145\/3009837.3009879","DOI":"10.1145\/3009837.3009879"},{"key":"13_CR17","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1016\/S1571-0661(05)80696-6","volume":"10","author":"U Montanari","year":"1997","unstructured":"Montanari, U., Pistore, M.: An introduction to history dependent automata. Electr. Notes Theor. Comput. Sci. 10, 170\u2013188 (1997). https:\/\/doi.org\/10.1016\/S1571-0661(05)80696-6","journal-title":"Electr. Notes Theor. Comput. Sci."},{"key":"13_CR18","doi-asserted-by":"crossref","unstructured":"Nies, A.: Describing groups. Bull. Symbol. Logic 13(3), 305\u2013339 (2007). http:\/\/www.jstor.org\/stable\/4493323","DOI":"10.2178\/bsl\/1186666149"},{"key":"13_CR19","doi-asserted-by":"publisher","unstructured":"Pitts, A.M.: Nominal Sets: Names and Symmetry in Computer Science. Cambridge Tracts in Theoretical Computer Science, Cambridge University Press (2013). https:\/\/doi.org\/10.1017\/CBO9781139084673","DOI":"10.1017\/CBO9781139084673"},{"key":"13_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"562","DOI":"10.1007\/11874683_37","volume-title":"Computer Science Logic","author":"A Rabinovich","year":"2006","unstructured":"Rabinovich, A., Thomas, W.: Decidable theories of the ordering of natural numbers with unary predicates. In: \u00c9sik, Z. (ed.) CSL 2006. LNCS, vol. 4207, pp. 562\u2013574. Springer, Heidelberg (2006). https:\/\/doi.org\/10.1007\/11874683_37"},{"key":"13_CR21","unstructured":"Sakakibara, Y.: Learning context-free grammars from structural data in polynomial time. In: Proceedings of the First Annual Workshop on Computational Learning Theory. COLT \u201988, San Francisco, CA, USA, pp. 330\u2013344. Morgan Kaufmann Publishers Inc. (1988)"},{"key":"13_CR22","doi-asserted-by":"publisher","unstructured":"Salomaa, A.: On finite automata with a time-variant structure. Inf. Control 13(2), 85\u201398 (1968). https:\/\/doi.org\/10.1016\/S0019-9958(68)90706-7, https:\/\/www.sciencedirect.com\/science\/article\/pii\/S0019995868907067","DOI":"10.1016\/S0019-9958(68)90706-7"},{"key":"13_CR23","doi-asserted-by":"crossref","unstructured":"Tsankov, T.: The additive group of the rationals does not have an automatic presentation. J. Symbol. Logic 76(4), 1341\u20131351 (2011). http:\/\/www.jstor.org\/stable\/23208221","DOI":"10.2178\/jsl\/1318338853"}],"container-title":["Lecture Notes in Computer Science","Automated Technology for Verification and Analysis"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-78709-6_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,31]],"date-time":"2025-01-31T22:10:41Z","timestamp":1738361441000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-78709-6_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9783031787089","9783031787096"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-78709-6_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"1 February 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"ATVA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on Automated Technology for Verification and Analysis","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Kyoto","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Japan","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21 October 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"25 October 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"atva2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}