{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T13:39:16Z","timestamp":1774964356237,"version":"3.50.1"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2021,3,26]],"date-time":"2021-03-26T00:00:00Z","timestamp":1616716800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CNS-1446607, CBET-0939511, IIS-1723995"],"award-info":[{"award-number":["CNS-1446607, CBET-0939511, IIS-1723995"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100018146","name":"DENSO CORPORATION","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100018146","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Cyber-Phys. Syst."],"published-print":{"date-parts":[[2021,7,31]]},"abstract":"<jats:p>\n            In this article, we focus on inferring high-level descriptions of a system from its execution traces. Specifically, we consider a classification problem where system behaviors are described using formulae of\n            <jats:italic>Signal Temporal Logic<\/jats:italic>\n            (STL). Given a finite set of pairs of system traces and labels, where each label indicates whether the corresponding trace exhibits some system property, we devised a decision-tree-based framework that outputs an STL formula that can distinguish the traces. We also extend this approach to the online learning scenario. In this setting, it is assumed that new signals may arrive over time and the previously inferred formula should be updated to accommodate the new data. The proposed approach presents some advantages over traditional machine learning classifiers. In particular, the produced formulae are interpretable and can be used in other phases of the system\u2019s operation, such as monitoring and control. We present two case studies to illustrate the effectiveness of the proposed algorithms: (1) a fault detection problem in an automotive system and (2) an anomaly detection problem in a maritime environment.\n          <\/jats:p>","DOI":"10.1145\/3433994","type":"journal-article","created":{"date-parts":[[2021,3,26]],"date-time":"2021-03-26T16:27:20Z","timestamp":1616776040000},"page":"1-23","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":29,"title":["Offline and Online Learning of Signal Temporal Logic Formulae Using Decision Trees"],"prefix":"10.1145","volume":"5","author":[{"given":"Giuseppe","family":"Bombara","sequence":"first","affiliation":[{"name":"Boston University, Boston, MA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Calin","family":"Belta","sequence":"additional","affiliation":[{"name":"Boston University, Boston, MA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,3,26]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-29860-8_12"},{"key":"e_1_2_1_2_1","volume-title":"System design of stochastic models using robustness of temporal properties. Theor. Comput. Sci. 587 (July","author":"Bartocci Ezio","year":"2015","unstructured":"Ezio Bartocci , Luca Bortolussi , Laura Nenzi , and Guido Sanguinetti . 2015. System design of stochastic models using robustness of temporal properties. Theor. Comput. Sci. 587 (July 2015 ), 3--25. DOI:https:\/\/doi.org\/10.1016\/j.tcs.2015.02.046 Ezio Bartocci, Luca Bortolussi, Laura Nenzi, and Guido Sanguinetti. 2015. System design of stochastic models using robustness of temporal properties. Theor. Comput. Sci. 587 (July 2015), 3--25. DOI:https:\/\/doi.org\/10.1016\/j.tcs.2015.02.046"},{"key":"e_1_2_1_3_1","volume-title":"Formal Modeling and Analysis of Timed Systems","author":"Bartocci Ezio","unstructured":"Ezio Bartocci , Luca Bortolussi , and Guido Sanguinetti . 2014. Data-driven statistical learning of temporal logic properties . In Formal Modeling and Analysis of Timed Systems . Springer , 23--37. Ezio Bartocci, Luca Bortolussi, and Guido Sanguinetti. 2014. Data-driven statistical learning of temporal logic properties. In Formal Modeling and Analysis of Timed Systems. Springer, 23--37."},{"key":"e_1_2_1_4_1","volume-title":"Runtime Verification (Lecture Notes in Computer Science)","author":"Bombara Giuseppe","unstructured":"Giuseppe Bombara and Calin Belta . 2017. Signal clustering using temporal logics . In Runtime Verification (Lecture Notes in Computer Science) . Springer , Cham , 121--137. DOI:https:\/\/doi.org\/10.1007\/978-3-319-67531-2_8 Giuseppe Bombara and Calin Belta. 2017. Signal clustering using temporal logics. In Runtime Verification (Lecture Notes in Computer Science). Springer, Cham, 121--137. DOI:https:\/\/doi.org\/10.1007\/978-3-319-67531-2_8"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.23919\/ECC.2018.8550271"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2883817.2883843"},{"key":"e_1_2_1_7_1","volume-title":"Olshen","author":"Breiman Leo","year":"1984","unstructured":"Leo Breiman , Jerome Friedman , Charles J. Stone , and Richard A . Olshen . 1984 . Classification and Regression Trees. CRC Press . Leo Breiman, Jerome Friedman, Charles J. Stone, and Richard A. Olshen. 1984. Classification and Regression Trees. CRC Press."},{"key":"e_1_2_1_8_1","volume-title":"Leveraging Applications of Formal Methods, Verification and Validation. Number 8803 in Lecture Notes in Computer Science","author":"Bufo Sara","unstructured":"Sara Bufo , Ezio Bartocci , Guido Sanguinetti , Massimo Borelli , Umberto Lucangelo , and Luca Bortolussi . 2014. Temporal logic based monitoring of assisted ventilation in intensive care patients . In Leveraging Applications of Formal Methods, Verification and Validation. Number 8803 in Lecture Notes in Computer Science . Springer , 391--403. DOI:https:\/\/doi.org\/10.1007\/978-3-662-45231-8_30 Sara Bufo, Ezio Bartocci, Guido Sanguinetti, Massimo Borelli, Umberto Lucangelo, and Luca Bortolussi. 2014. Temporal logic based monitoring of assisted ventilation in intensive care patients. In Leveraging Applications of Formal Methods, Verification and Validation. Number 8803 in Lecture Notes in Computer Science. Springer, 391--403. DOI:https:\/\/doi.org\/10.1007\/978-3-662-45231-8_30"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the IEEE 55th Conference on Decision and Control (CDC\u201916)","author":"Chen G.","year":"2016","unstructured":"G. Chen , Z. Sabato , and Z. Kong . 2016. Active learning based requirement mining for cyber-physical systems . In Proceedings of the IEEE 55th Conference on Decision and Control (CDC\u201916) . 4586--4593. DOI:https:\/\/doi.org\/10.1109\/CDC. 2016 .7798967 G. Chen, Z. Sabato, and Z. Kong. 2016. Active learning based requirement mining for cyber-physical systems. In Proceedings of the IEEE 55th Conference on Decision and Control (CDC\u201916). 4586--4593. DOI:https:\/\/doi.org\/10.1109\/CDC.2016.7798967"},{"key":"e_1_2_1_10_1","unstructured":"E. M. Clarke Orna Grumberg and Doron Peled. 1999. Model Checking. MIT Press.  E. M. Clarke Orna Grumberg and Doron Peled. 1999. Model Checking. MIT Press."},{"key":"e_1_2_1_11_1","volume-title":"Introduction to Algorithms","author":"Cormen Thomas H.","unstructured":"Thomas H. Cormen . 2009. Introduction to Algorithms ( 3 rd ed.). MIT Press . Thomas H. Cormen. 2009. Introduction to Algorithms (3rd ed.). MIT Press.","edition":"3"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/347090.347107"},{"key":"e_1_2_1_13_1","volume-title":"Computer Aided Verification","author":"Donz\u00e9 Alexandre","unstructured":"Alexandre Donz\u00e9 , Thomas Ferrere , and Oded Maler . 2013. Efficient robust monitoring for STL . In Computer Aided Verification . Springer , 264--279. Alexandre Donz\u00e9, Thomas Ferrere, and Oded Maler. 2013. Efficient robust monitoring for STL. In Computer Aided Verification. Springer, 264--279."},{"key":"e_1_2_1_14_1","series-title":"Lecture Notes in Computer Science","volume-title":"Formal Modeling and Analysis of Timed Systems, Krishnendu Chatterjee and Thomas A","author":"Donz\u00e9 Alexandre","unstructured":"Alexandre Donz\u00e9 and Oded Maler . 2010. Robust satisfaction of temporal logic over real-valued signals . In Formal Modeling and Analysis of Timed Systems, Krishnendu Chatterjee and Thomas A . Henzinger (Eds.). Number 6246 in Lecture Notes in Computer Science . Springer , Berlin, 92--106. Alexandre Donz\u00e9 and Oded Maler. 2010. Robust satisfaction of temporal logic over real-valued signals. In Formal Modeling and Analysis of Timed Systems, Krishnendu Chatterjee and Thomas A. Henzinger (Eds.). Number 6246 in Lecture Notes in Computer Science. Springer, Berlin, 92--106."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.06.021"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1467247.1467271"},{"key":"e_1_2_1_17_1","volume-title":"The Elements of Statistical Learning: Data Mining, Inference, and Prediction","author":"Hastie Trevor","unstructured":"Trevor Hastie , Robert Tibshirani , and Jerome Friedman . 2016. The Elements of Statistical Learning: Data Mining, Inference, and Prediction ( 2 nd ed.). Springer , New York, NY . Trevor Hastie, Robert Tibshirani, and Jerome Friedman. 2016. The Elements of Statistical Learning: Data Mining, Inference, and Prediction (2nd ed.). Springer, New York, NY.","edition":"2"},{"key":"e_1_2_1_18_1","volume-title":"Proc. Appl. Verificat. Cont. Hybrid Syst.","author":"Hoxha Bardh","year":"2014","unstructured":"Bardh Hoxha , Houssam Abbas , and Georgios Fainekos . 2014 . Benchmarks for temporal logic requirements for automotive systems . Proc. Appl. Verificat. Cont. Hybrid Syst. (2014). Bardh Hoxha, Houssam Abbas, and Georgios Fainekos. 2014. Benchmarks for temporal logic requirements for automotive systems. Proc. Appl. Verificat. Cont. Hybrid Syst. (2014)."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10009-017-0447-4"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(76)90095-8"},{"key":"e_1_2_1_21_1","first-page":"33","article-title":"Adaptive simulated annealing (ASA): Lessons learned","volume":"25","author":"Ingber Lester","year":"1996","unstructured":"Lester Ingber . 1996 . Adaptive simulated annealing (ASA): Lessons learned . Control Cybernet. 25 (1996), 33 -- 54 . Lester Ingber. 1996. Adaptive simulated annealing (ASA): Lessons learned. Control Cybernet. 25 (1996), 33--54.","journal-title":"Control Cybernet."},{"key":"e_1_2_1_22_1","volume-title":"Fault-Diagnosis Systems","author":"Isermann Rolf","unstructured":"Rolf Isermann . 2006. Fault-Diagnosis Systems . Springer . Rolf Isermann. 2006. Fault-Diagnosis Systems. Springer."},{"key":"e_1_2_1_23_1","first-page":"4","article-title":"Deep learning for time series classification: A review","volume":"33","author":"Fawaz Hassan Ismail","year":"2019","unstructured":"Hassan Ismail Fawaz , Germain Forestier , Jonathan Weber , Lhassane Idoumghar , and Pierre-Alain Muller . 2019 . Deep learning for time series classification: A review . Data Min. Knowl. Discov. 33 , 4 (July 2019), 917--963. DOI:https:\/\/doi.org\/10.1007\/s10618-019-00619-1 Hassan Ismail Fawaz, Germain Forestier, Jonathan Weber, Lhassane Idoumghar, and Pierre-Alain Muller. 2019. Deep learning for time series classification: A review. Data Min. Knowl. Discov. 33, 4 (July 2019), 917--963. DOI:https:\/\/doi.org\/10.1007\/s10618-019-00619-1","journal-title":"Data Min. Knowl. Discov."},{"key":"e_1_2_1_24_1","volume-title":"Runtime Verification (Lecture Notes in Computer Science)","author":"Jha Susmit","unstructured":"Susmit Jha , Ashish Tiwari , Sanjit A. Seshia , Tuhin Sahai , and Natarajan Shankar . 2017. TeLEx: Passive STL learning using only positive examples . In Runtime Verification (Lecture Notes in Computer Science) . Springer , Cham , 208--224. DOI:https:\/\/doi.org\/10.1007\/978-3-319-67531-2_13 Susmit Jha, Ashish Tiwari, Sanjit A. Seshia, Tuhin Sahai, and Natarajan Shankar. 2017. TeLEx: Passive STL learning using only positive examples. In Runtime Verification (Lecture Notes in Computer Science). Springer, Cham, 208--224. DOI:https:\/\/doi.org\/10.1007\/978-3-319-67531-2_13"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956821"},{"key":"e_1_2_1_26_1","first-page":"1","article-title":"Mining requirements from closed-loop control models","volume":"99","author":"Jin Xiaoqing","year":"2015","unstructured":"Xiaoqing Jin , Alexandre Donz\u00e9 , Jyotirmoy Deshmukh , and Sanjit A. Seshia . 2015 . Mining requirements from closed-loop control models . IEEE Trans. Comput.-Aided Design Integr. Circ. Syst. 99 , 34 (2015), 1 -- 1 . DOI:https:\/\/doi.org\/10.1109\/TCAD.2015.2421907 Xiaoqing Jin, Alexandre Donz\u00e9, Jyotirmoy Deshmukh, and Sanjit A. Seshia. 2015. Mining requirements from closed-loop control models. IEEE Trans. Comput.-Aided Design Integr. Circ. Syst. 99, 34 (2015), 1--1. DOI:https:\/\/doi.org\/10.1109\/TCAD.2015.2421907","journal-title":"IEEE Trans. Comput.-Aided Design Integr. Circ. Syst."},{"key":"e_1_2_1_27_1","volume-title":"Kearns and Umesh Virkumar Vazirani","author":"Michael","year":"1994","unstructured":"Michael J. Kearns and Umesh Virkumar Vazirani . 1994 . An Introduction to Computational Learning Theory. MIT Press , Cambridge, MA. Michael J. Kearns and Umesh Virkumar Vazirani. 1994. An Introduction to Computational Learning Theory. MIT Press, Cambridge, MA."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2016.2585083"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the 15th International Conference on Information Fusion (FUSION\u201912)","author":"Kowalska K.","unstructured":"K. Kowalska and L. Peel . 2012. Maritime anomaly detection using Gaussian process active learning . In Proceedings of the 15th International Conference on Information Fusion (FUSION\u201912) . 1164--1171. K. Kowalska and L. Peel. 2012. Maritime anomaly detection using Gaussian process active learning. In Proceedings of the 15th International Conference on Information Fusion (FUSION\u201912). 1164--1171."},{"key":"e_1_2_1_30_1","volume-title":"Kochenderfer","author":"Liu Changliu","year":"2019","unstructured":"Changliu Liu , Tomer Arnon , Christopher Lazarus , Clark Barrett , and Mykel J . Kochenderfer . 2019 . Algorithms for verifying deep neural networks. Retrieved from https:\/\/arXiv:1903.06758 Changliu Liu, Tomer Arnon, Christopher Lazarus, Clark Barrett, and Mykel J. Kochenderfer. 2019. Algorithms for verifying deep neural networks. Retrieved from https:\/\/arXiv:1903.06758"},{"key":"e_1_2_1_31_1","volume-title":"Formal Techniques, Modelling and Analysis of Timed and Fault-Tolerant Systems, Yassine Lakhnech and Sergio Yovine (Eds.). Number 3253 in Lecture Notes in Computer Science","author":"Maler Oded","unstructured":"Oded Maler and Dejan Nickovic . 2004. Monitoring temporal properties of continuous signals . In Formal Techniques, Modelling and Analysis of Timed and Fault-Tolerant Systems, Yassine Lakhnech and Sergio Yovine (Eds.). Number 3253 in Lecture Notes in Computer Science . Springer Berlin Heidelberg , 152--166. Oded Maler and Dejan Nickovic. 2004. Monitoring temporal properties of continuous signals. In Formal Techniques, Modelling and Analysis of Timed and Fault-Tolerant Systems, Yassine Lakhnech and Sergio Yovine (Eds.). Number 3253 in Lecture Notes in Computer Science. Springer Berlin Heidelberg, 152--166."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3147660"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.23919\/FMCAD.2018.8603016"},{"key":"e_1_2_1_34_1","volume-title":"Quantitative Evaluation of Systems (Lecture Notes in Computer Science)","author":"Nenzi Laura","unstructured":"Laura Nenzi , Simone Silvetti , Ezio Bartocci , and Luca Bortolussi . 2018. A robust genetic algorithm for learning temporal specifications from data . In Quantitative Evaluation of Systems (Lecture Notes in Computer Science) , Annabelle McIver and Andras Horvath (Eds.). Springer International Publishing , 323--338. Laura Nenzi, Simone Silvetti, Ezio Bartocci, and Luca Bortolussi. 2018. A robust genetic algorithm for learning temporal specifications from data. In Quantitative Evaluation of Systems (Lecture Notes in Computer Science), Annabelle McIver and Andras Horvath (Eds.). Springer International Publishing, 323--338."},{"key":"e_1_2_1_35_1","volume-title":"Programs for Machine Learning","author":"Quinlan J. Ross","unstructured":"J. Ross Quinlan . 2014. C4.5 : Programs for Machine Learning . Elsevier . J. Ross Quinlan. 2014. C4.5: Programs for Machine Learning. Elsevier."},{"key":"e_1_2_1_36_1","volume-title":"Pattern Recognition and Neural Networks","author":"Ripley Brian D.","unstructured":"Brian D. Ripley . 1996. Pattern Recognition and Neural Networks . Cambridge University Press . Brian D. Ripley. 1996. Pattern Recognition and Neural Networks. Cambridge University Press."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNNLS.2014.2333557"},{"key":"e_1_2_1_38_1","volume-title":"Proceedings of the IEEE International Conference on Evolutionary Computation Proceedings. 69--73","author":"Shi Y.","year":"1998","unstructured":"Y. Shi and R. Eberhart . 1998. A modified particle swarm optimizer . In Proceedings of the IEEE International Conference on Evolutionary Computation Proceedings. 69--73 . DOI:https:\/\/doi.org\/10.1109\/ICEC. 1998 .699146 Y. Shi and R. Eberhart. 1998. A modified particle swarm optimizer. In Proceedings of the IEEE International Conference on Evolutionary Computation Proceedings. 69--73. DOI:https:\/\/doi.org\/10.1109\/ICEC.1998.699146"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008202821328"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1007413323501"},{"key":"e_1_2_1_41_1","volume-title":"Proceedings of the IEEE 56th Annual Conference on Decision and Control (CDC\u201917)","author":"Vaidyanathan P.","year":"2017","unstructured":"P. Vaidyanathan , R. Ivison , G. Bombara , N. A. DeLateur , R. Weiss , D. Densmore , and C. Belta . 2017. Grid-based temporal logic inference . In Proceedings of the IEEE 56th Annual Conference on Decision and Control (CDC\u201917) . 5354--5359. DOI:https:\/\/doi.org\/10.1109\/CDC. 2017 .8264452 P. Vaidyanathan, R. Ivison, G. Bombara, N. A. DeLateur, R. Weiss, D. Densmore, and C. Belta. 2017. Grid-based temporal logic inference. In Proceedings of the IEEE 56th Annual Conference on Decision and Control (CDC\u201917). 5354--5359. DOI:https:\/\/doi.org\/10.1109\/CDC.2017.8264452"},{"key":"e_1_2_1_42_1","volume-title":"Seshia","author":"Vazquez-Chanlatte Marcell","year":"2017","unstructured":"Marcell Vazquez-Chanlatte , Jyotirmoy V. Deshmukh , Xiaoqing Jin , and Sanjit A . Seshia . 2017 . Logical clustering and learning for time-series data. In Computer Aided Verification (Lecture Notes in Computer Science). Springer , Cham, 305--325. DOI:https:\/\/doi.org\/10.1007\/978-3-319-63387-9_15 Marcell Vazquez-Chanlatte, Jyotirmoy V. Deshmukh, Xiaoqing Jin, and Sanjit A. Seshia. 2017. Logical clustering and learning for time-series data. In Computer Aided Verification (Lecture Notes in Computer Science). Springer, Cham, 305--325. DOI:https:\/\/doi.org\/10.1007\/978-3-319-63387-9_15"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10703-013-0195-3"}],"container-title":["ACM Transactions on Cyber-Physical Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3433994","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3433994","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3433994","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:28:11Z","timestamp":1750195691000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3433994"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,3,26]]},"references-count":43,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,7,31]]}},"alternative-id":["10.1145\/3433994"],"URL":"https:\/\/doi.org\/10.1145\/3433994","relation":{},"ISSN":["2378-962X","2378-9638"],"issn-type":[{"value":"2378-962X","type":"print"},{"value":"2378-9638","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,3,26]]},"assertion":[{"value":"2020-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-03-26","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}