{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T21:48:56Z","timestamp":1757627336979,"version":"3.44.0"},"publisher-location":"Cham","reference-count":36,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783032045898"},{"type":"electronic","value":"9783032045904"}],"license":[{"start":{"date-parts":[[2025,8,29]],"date-time":"2025-08-29T00:00:00Z","timestamp":1756425600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,8,29]],"date-time":"2025-08-29T00:00:00Z","timestamp":1756425600000},"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":[[2026]]},"DOI":"10.1007\/978-3-032-04590-4_16","type":"book-chapter","created":{"date-parts":[[2025,9,1]],"date-time":"2025-09-01T13:50:16Z","timestamp":1756734616000},"page":"227-243","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A Framework for\u00a0Computing Upper Bounds in\u00a0Passive Learning Settings"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0009-0000-4143-6298","authenticated-orcid":false,"given":"Benjamin","family":"Bordais","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9276-6342","authenticated-orcid":false,"given":"Daniel","family":"Neider","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,8,29]]},"reference":[{"key":"16_CR1","doi-asserted-by":"publisher","unstructured":"Angluin, D.: On the complexity of minimum inference of regular sets. Inf. Control 39(3), 337\u2013350 (1978). https:\/\/doi.org\/10.1016\/S0019-9958(78)90683-6","DOI":"10.1016\/S0019-9958(78)90683-6"},{"key":"16_CR2","doi-asserted-by":"publisher","unstructured":"Arif, M.F., Larraz, D., Echeverria, M., Reynolds, A., Chowdhury, O., Tinelli, C.: SYSLITE: syntax-guided synthesis of PLTL formulas from finite traces. In: 2020 Formal Methods in Computer Aided Design, FMCAD 2020, Haifa, Israel, 21\u201324 September 2020, pp. 93\u2013103. IEEE (2020). https:\/\/doi.org\/10.34727\/2020\/ISBN.978-3-85448-042-6_16","DOI":"10.34727\/2020\/ISBN.978-3-85448-042-6_16"},{"key":"16_CR3","doi-asserted-by":"publisher","unstructured":"Blackburn, P., de\u00a0Rijke, M., Venema, Y.: Modal Logic, Cambridge Tracts in Theoretical Computer Science, vol.\u00a053. Cambridge University Press, Cambridge (2001). https:\/\/doi.org\/10.1017\/CBO9781107050884","DOI":"10.1017\/CBO9781107050884"},{"key":"16_CR4","doi-asserted-by":"publisher","unstructured":"Bombara, G., Vasile, C.I., Penedo, F., Yasuoka, H., Belta, C.: A decision tree approach to data classification using signal temporal logic. In: Proceedings of the 19th International Conference on Hybrid Systems: Computation and Control, pp. 1\u201310. HSCC \u201916, Association for Computing Machinery, New York, NY, USA (2016). https:\/\/doi.org\/10.1145\/2883817.2883843","DOI":"10.1145\/2883817.2883843"},{"key":"16_CR5","doi-asserted-by":"publisher","unstructured":"Bordais, B., Neider, D.: A framework for computing upper bounds in passive learning settings. CoRR abs\/2504.03517 (2025). https:\/\/doi.org\/10.48550\/ARXIV.2504.03517, https:\/\/doi.org\/10.48550\/arXiv.2504.03517","DOI":"10.48550\/ARXIV.2504.03517"},{"key":"16_CR6","doi-asserted-by":"publisher","unstructured":"Bordais, B., Neider, D., Roy, R.: The complexity of learning temporal properties. CoRR abs\/2408.04486 (2024). https:\/\/doi.org\/10.48550\/ARXIV.2408.04486, https:\/\/doi.org\/10.48550\/arXiv.2408.04486","DOI":"10.48550\/ARXIV.2408.04486"},{"key":"16_CR7","doi-asserted-by":"publisher","unstructured":"Bordais, B., Neider, D., Roy, R.: Learning branching-time properties in CTL and ATL via constraint solving. In: Platzer, A., Rozier, K.Y., Pradella, M., Rossi, M. (eds.) Formal Methods. FM 2024. LNCS, vol. 14933, pp. 304\u2013323. Springer, Cham (2024). https:\/\/doi.org\/10.1007\/978-3-031-71162-6_16","DOI":"10.1007\/978-3-031-71162-6_16"},{"key":"16_CR8","doi-asserted-by":"publisher","unstructured":"Camacho, A., Icarte, R.T., Klassen, T.Q., Valenzano, R.A., McIlraith, S.A.: LTL and beyond: formal languages for reward function specification in reinforcement learning. In: Kraus, S. (ed.) Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI 2019, Macao, China, 10\u201316 August 2019, pp. 6065\u20136073. ijcai.org (2019). https:\/\/doi.org\/10.24963\/IJCAI.2019\/840, https:\/\/doi.org\/10.24963\/ijcai.2019\/840","DOI":"10.24963\/IJCAI.2019\/840"},{"key":"16_CR9","doi-asserted-by":"crossref","unstructured":"Camacho, A., McIlraith, S.A.: Learning interpretable models expressed in linear temporal logic. In: ICAPS, pp. 621\u2013630. AAAI Press (2019)","DOI":"10.1609\/icaps.v29i1.3529"},{"key":"16_CR10","doi-asserted-by":"publisher","unstructured":"Chan, W.: Temporal-logic queries. In: Emerson, E.A., Sistla, A.P. (eds.) Computer Aided Verification. CAV 2000. LNCS, vol.\u00a01855, pp. 450\u2013463. Springer, Berlin, Heidelberg (2000). https:\/\/doi.org\/10.1007\/10722167_34","DOI":"10.1007\/10722167_34"},{"key":"16_CR11","unstructured":"Ehlers, R., Gavran, I., Neider, D.: Learning properties in LTL $$\\cap $$ ACTL from positive examples only. In: 2020 Formal Methods in Computer Aided Design, FMCAD 2020, Haifa, Israel, 21\u201324 September 2020, pp. 104\u2013112. IEEE (2020)"},{"key":"16_CR12","doi-asserted-by":"publisher","unstructured":"Ellul, K., Krawetz, B., Shallit, J.O., Wang, M.: Regular expressions: new results and open problems. J. Autom. Lang. Comb. 10(4), 407\u2013437 (2005). https:\/\/doi.org\/10.25596\/JALC-2005-407, https:\/\/doi.org\/10.25596\/jalc-2005-407","DOI":"10.25596\/JALC-2005-407"},{"key":"16_CR13","unstructured":"Funk, M.: Concept-by-example in el knowledge bases. Master\u2019s thesis, University of Bremen (2019)"},{"key":"16_CR14","doi-asserted-by":"publisher","unstructured":"Gaglione, J., Neider, D., Roy, R., Topcu, U., Xu, Z.: Maxsat-based temporal logic inference from noisy data. Innov. Syst. Softw. Eng. 18(3), 427\u2013442 (2022). https:\/\/doi.org\/10.1007\/S11334-022-00444-8","DOI":"10.1007\/S11334-022-00444-8"},{"issue":"3","key":"16_CR15","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. Inf. Control 37(3), 302\u2013320 (1978)","journal-title":"Inf. Control"},{"key":"16_CR16","doi-asserted-by":"publisher","unstructured":"Goranko, V., Kuijer, L.B.: On the length and depth of temporal formulae distinguishing non-bisimilar transition systems. In: Dyreson, C.E., Hansen, M.R., Hunsberger, L. (eds.) 23rd International Symposium on Temporal Representation and Reasoning, TIME 2016, Kongens Lyngby, Denmark, 17\u201319 October 2016, pp. 177\u2013185. IEEE Computer Society (2016). https:\/\/doi.org\/10.1109\/TIME.2016.26, https:\/\/doi.org\/10.1109\/TIME.2016.26","DOI":"10.1109\/TIME.2016.26"},{"key":"16_CR17","doi-asserted-by":"publisher","unstructured":"Hansson, H., Jonsson, B.: A logic for reasoning about time and reliability. Form. Aspects Comput. 6(5), 512\u2013535 (1994). https:\/\/doi.org\/10.1007\/BF01211866, https:\/\/doi.org\/10.1007\/BF01211866","DOI":"10.1007\/BF01211866"},{"key":"16_CR18","doi-asserted-by":"publisher","unstructured":"Ielo, A., Law, M., Fionda, V., Ricca, F., Giacomo, G.D., Russo, A.: Towards ilp-based $$\\text{LTL}_{\\rm {f}}$$ passive learning. In: Bellodi, E., Lisi, F.A., Zese, R. (eds.) Inductive Logic Programming. ILP 2023. LNCS, vol. 14363, pp. 30\u201345. Springer, Cham (2023). https:\/\/doi.org\/10.1007\/978-3-031-49299-0_3","DOI":"10.1007\/978-3-031-49299-0_3"},{"key":"16_CR19","doi-asserted-by":"publisher","unstructured":"Kim, J., Muise, C., Shah, A., Agarwal, S., Shah, J.: Bayesian inference of linear temporal logic specifications for contrastive explanations. In: Kraus, S. (ed.) Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI 2019, Macao, China, 10\u201316 August 2019, pp. 5591\u20135598. ijcai.org (2019). https:\/\/doi.org\/10.24963\/IJCAI.2019\/776","DOI":"10.24963\/IJCAI.2019\/776"},{"key":"16_CR20","doi-asserted-by":"publisher","unstructured":"Luo, W., Liang, P., Du, J., Wan, H., Peng, B., Zhang, D.: Bridging ltlf inference to GNN inference for learning ltlf formulae. In: Thirty-Sixth AAAI Conference on Artificial Intelligence, AAAI 2022, Thirty-Fourth Conference on Innovative Applications of Artificial Intelligence, IAAI 2022, The Twelveth Symposium on Educational Advances in Artificial Intelligence, EAAI 2022 Virtual Event, February 22\u20131 March 2022, pp. 9849\u20139857. AAAI Press (2022). https:\/\/doi.org\/10.1609\/AAAI.V36I9.21221","DOI":"10.1609\/AAAI.V36I9.21221"},{"key":"16_CR21","unstructured":"Mascle, C., Fijalkow, N., Lagarde, G.: Learning temporal formulas from examples is hard. CoRR abs\/2312.16336 (2023). https:\/\/arxiv.org\/pdf\/2312.16336"},{"key":"16_CR22","doi-asserted-by":"publisher","unstructured":"Mohammadinejad, S., Deshmukh, J.V., Puranic, A.G., Vazquez-Chanlatte, M., Donz\u00e9, A.: Interpretable classification of time-series data using efficient enumerative techniques. In: HSCC \u201920: 23rd ACM International Conference on Hybrid Systems: Computation and Control, Sydney, New South Wales, Australia, 21\u201324 April 2020, pp. 9:1\u20139:10. ACM (2020). https:\/\/doi.org\/10.1145\/3365365.3382218","DOI":"10.1145\/3365365.3382218"},{"key":"16_CR23","doi-asserted-by":"publisher","unstructured":"Neider, D., Gavran, I.: Learning linear temporal properties. In: Bj\u00f8rner, N.S., Gurfinkel, A. (eds.) 2018 Formal Methods in Computer Aided Design, FMCAD 2018, Austin, TX, USA, October 30\u2013 2 November 2018, pp. 1\u201310. IEEE (2018). https:\/\/doi.org\/10.23919\/FMCAD.2018.8603016","DOI":"10.23919\/FMCAD.2018.8603016"},{"key":"16_CR24","doi-asserted-by":"publisher","unstructured":"Pnueli, A.: The temporal logic of programs. In: 18th Annual Symposium on Foundations of Computer Science, Providence, Rhode Island, USA, 31 October\u20131 November 1977, pp. 46\u201357. IEEE Computer Society (1977). https:\/\/doi.org\/10.1109\/SFCS.1977.32","DOI":"10.1109\/SFCS.1977.32"},{"key":"16_CR25","doi-asserted-by":"publisher","unstructured":"Pommellet, A., Stan, D., Scatton, S.: Sat-based learning of computation tree logic. In: Benzm\u00fcller, C., Heule, M.J., Schmidt, R.A. (eds.) Automated Reasoning. IJCAR 2024. LNCS, vol. 14739, pp. 366\u2013385. Springer, Cham (2024). https:\/\/doi.org\/10.1007\/978-3-031-63498-7_22","DOI":"10.1007\/978-3-031-63498-7_22"},{"key":"16_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1007\/978-3-030-99524-9_14","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems","author":"R Raha","year":"2022","unstructured":"Raha, R., Roy, R., Fijalkow, N., Neider, D.: Scalable anytime algorithms for learning fragments of linear temporal logic. In: TACAS 2022. LNCS, vol. 13243, pp. 263\u2013280. Springer, Cham (2022). https:\/\/doi.org\/10.1007\/978-3-030-99524-9_14"},{"key":"16_CR27","doi-asserted-by":"publisher","unstructured":"Raha, R., Roy, R., Fijalkow, N., Neider, D., P\u00e9rez, G.A.: Synthesizing efficiently monitorable formulas in metric temporal logic. In: Dimitrova, R., Lahav, O., Wolff, S. (eds.) Verification, Model Checking, and Abstract Interpretation. VMCAI 2024. LNCS, vol. 14500, pp. 264\u2013288. Springer, Cha (2024). https:\/\/doi.org\/10.1007\/978-3-031-50521-8_13","DOI":"10.1007\/978-3-031-50521-8_13"},{"key":"16_CR28","doi-asserted-by":"crossref","unstructured":"Riener, H.: Exact synthesis of LTL properties from traces. In: FDL, pp.\u00a01\u20136. IEEE (2019)","DOI":"10.1109\/FDL.2019.8876900"},{"key":"16_CR29","doi-asserted-by":"crossref","unstructured":"Roy, R., Fisman, D., Neider, D.: Learning interpretable models in the property specification language. In: IJCAI, pp. 2213\u20132219. ijcai.org (2020)","DOI":"10.24963\/ijcai.2020\/306"},{"key":"16_CR30","doi-asserted-by":"publisher","unstructured":"Roy, R., Gaglione, J., Baharisangari, N., Neider, D., Xu, Z., Topcu, U.: Learning interpretable temporal properties from positive examples only. In: Williams, B., Chen, Y., Neville, J. (eds.) Thirty-Seventh AAAI Conference on Artificial Intelligence, AAAI 2023, Thirty-Fifth Conference on Innovative Applications of Artificial Intelligence, IAAI 2023, Thirteenth Symposium on Educational Advances in Artificial Intelligence, EAAI 2023, Washington, DC, USA, 7\u201314 February 2023, pp. 6507\u20136515. AAAI Press (2023). https:\/\/doi.org\/10.1609\/AAAI.V37I5.25800","DOI":"10.1609\/AAAI.V37I5.25800"},{"key":"16_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"8","DOI":"10.1007\/978-3-319-48869-1_2","volume-title":"Verified Software. Theories, Tools, and Experiments","author":"KY Rozier","year":"2016","unstructured":"Rozier, K.Y.: Specification: the biggest bottleneck in formal methods and autonomy. In: Blazy, S., Chechik, M. (eds.) VSTTE 2016. LNCS, vol. 9971, pp. 8\u201326. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-48869-1_2"},{"key":"16_CR32","unstructured":"Sandor, J.: Handbook of Number Theory, II. Kluwer Academic Publishers, Dordrecht (2004)"},{"key":"16_CR33","doi-asserted-by":"publisher","unstructured":"Valizadeh, M., Berger, M.: Search-based regular expression inference on a GPU. Proc. ACM Program. Lang. 7(PLDI), 1317\u20131339 (2023). https:\/\/doi.org\/10.1145\/3591274","DOI":"10.1145\/3591274"},{"key":"16_CR34","doi-asserted-by":"publisher","unstructured":"Valizadeh, M., Fijalkow, N., Berger, M.: LTL learning on gpus. In: Gurfinkel, A., Ganesh, V. (eds.) Computer Aided Verification. CAV 2024. LNCS, vol. 14683, pp. 209\u2013231. Springer, Cham (2024). https:\/\/doi.org\/10.1007\/978-3-031-65633-0_10","DOI":"10.1007\/978-3-031-65633-0_10"},{"key":"16_CR35","doi-asserted-by":"crossref","unstructured":"Wan, H., Liang, P., Du, J., Luo, W., Ye, R., Peng, B.: End-to-end learning of ltlf formulae by faithful ltlf encoding. In: AAAI, pp. 9071\u20139079. AAAI Press (2024)","DOI":"10.1609\/aaai.v38i8.28757"},{"issue":"3\u20134","key":"16_CR36","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1007\/s10515-011-0084-1","volume":"18","author":"A Wasylkowski","year":"2011","unstructured":"Wasylkowski, A., Zeller, A.: Mining temporal specifications from object usage. Autom. Softw. Eng. 18(3\u20134), 263\u2013292 (2011)","journal-title":"Autom. Softw. Eng."}],"container-title":["Lecture Notes in Computer Science","Logics in Artificial Intelligence"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-04590-4_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,10]],"date-time":"2025-09-10T02:25:52Z","timestamp":1757471152000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-04590-4_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,8,29]]},"ISBN":["9783032045898","9783032045904"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-04590-4_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2025,8,29]]},"assertion":[{"value":"29 August 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"JELIA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"European Conference on Logics in Artificial Intelligence","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Kutaisi","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Georgia","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"1 September 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"5 September 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"jelia2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.jelia.eu\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}