{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:42:00Z","timestamp":1740109320722,"version":"3.37.3"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,1,4]],"date-time":"2022-01-04T00:00:00Z","timestamp":1641254400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,1,4]],"date-time":"2022-01-04T00:00:00Z","timestamp":1641254400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"ministerio de ciencia, innovaci\u00f3n y universidades","award":["PID2019-108965GB-I00"],"award-info":[{"award-number":["PID2019-108965GB-I00"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,2]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In this paper we study regular expression matching in cases in which the identity of the symbols received is subject to uncertainty. We develop a model of symbol emission and uses a modification of the shortest path algorithm to find optimal matches on the Cartesian Graph of an expression provided that the input is a finite list. In the case of infinite streams, we show that the problem is in general undecidable but, if each symbols is received with probability 0 infinitely often, then with probability 1 the problem is decidable.<\/jats:p>","DOI":"10.1007\/s00453-021-00906-8","type":"journal-article","created":{"date-parts":[[2022,1,4]],"date-time":"2022-01-04T16:02:36Z","timestamp":1641312156000},"page":"532-564","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Matching Regular Expressions on uncertain data"],"prefix":"10.1007","volume":"84","author":[{"given":"Jos\u00e9 Arturo","family":"Gil","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1869-5301","authenticated-orcid":false,"given":"Simone","family":"Santini","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,1,4]]},"reference":[{"key":"906_CR1","doi-asserted-by":"crossref","unstructured":"Baeza-Yates, R., Navarro, G.: Faster approximate string matching. Algorithmica 23, 127\u201358 (1999)","DOI":"10.1007\/PL00009253"},{"key":"906_CR2","doi-asserted-by":"crossref","unstructured":"Bhonsle, S., Gupta, A., Santini, S., Worring, M., Jain, R.: Complex visual activity recognition using a temporally ordered database. In: Visual Information and Information Systems, pp. 722\u2013779. Springer, Heidelberg (1999)","DOI":"10.1007\/3-540-48762-X_89"},{"key":"906_CR3","unstructured":"Brookshear, J.G.: Theory of Computation: Formal Languages, Automata, and Complexity. Addison Wesley (1989)"},{"key":"906_CR4","unstructured":"Church, A.: Applications of recursive arithmetic to the problem of circuit synthesis. In: Summaries of the Summer Institute of Symbolic Logic, pp. 3\u201350 (1957)"},{"key":"906_CR5","doi-asserted-by":"crossref","unstructured":"Daldoss, M., Piotto, N., Conci, N., De\u00a0Natale, F.G.B.: Activity detection using regular expressions. In: Analysis, Retrieval and Delivery of Multimedia Content, pp. 91\u2013106. Springer (2013)","DOI":"10.1007\/978-1-4614-3831-1_6"},{"key":"906_CR6","doi-asserted-by":"crossref","unstructured":"Del Bimbo, A., Vicario, E., Zingoni, D.: Symbolic description and visual querying of image sequences using spatio-temporal logic. IEEE Trans. Knowl. Data Eng. 7(4), 66 (1994)","DOI":"10.1109\/69.404033"},{"key":"906_CR7","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-01492-5","volume-title":"Handbook of Weighted Automata","author":"M Droste","year":"2009","unstructured":"Droste, M., Kuich, W., Vogler, H.: Handbook of Weighted Automata. Springer, Heiko (2009)"},{"issue":"9","key":"906_CR8","doi-asserted-by":"publisher","first-page":"755","DOI":"10.1093\/bioinformatics\/14.9.755","volume":"14","author":"SR Eddy","year":"1998","unstructured":"Eddy, S.R.: Profile hiden Markov models. Bioinform. Rev. 14(9), 755\u201363 (1998)","journal-title":"Bioinform. Rev."},{"issue":"4","key":"906_CR9","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1109\/MMUL.2005.87","volume":"12","author":"ARJ Francois","year":"2005","unstructured":"Francois, A.R.J., Nevatia, R., Hobbs, J., Bolles, R.C., Smith, J.R.: VERL: an ontology framework for representing and annotating video events. IEEE Multimed. 12(4), 76\u201386 (2005)","journal-title":"IEEE Multimed."},{"issue":"6","key":"906_CR10","doi-asserted-by":"publisher","first-page":"989","DOI":"10.1137\/0219067","volume":"19","author":"Z Galil","year":"1990","unstructured":"Galil, Z., Park, K.: An improved algorithm for approximate string matching. SIAM J. Comput. 19(6), 989\u201399 (1990)","journal-title":"SIAM J. Comput."},{"key":"906_CR11","unstructured":"Ghanem, N., DeMenthon, D., Doermann, D, Davis, L.: Representation and recognition of events in surveillance video using petri nets. In: Conference on Computer Vision and Pattern Recognition Workshop, 2004 (CVPR\u201904), pp. 112\u201321. IEEE (2004)"},{"key":"906_CR12","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1016\/j.artint.2007.04.002","volume":"171","author":"A Hakeem","year":"2007","unstructured":"Hakeem, A., Shah, M.: Learning, detection and representation of multi-agent events in videos. Artif. Intell. 171, 66 (2007)","journal-title":"Artif. Intell."},{"key":"906_CR13","unstructured":"Hakeem, A., Sheikh, Y., Shah, M.: A hierarchical event representation for the analysis of videos. In: Proceedings of AAAI, pp. 263\u2013268 (2004)"},{"key":"906_CR14","unstructured":"Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to Automata Theory, Languages and Computation (2002)"},{"issue":"8","key":"906_CR15","doi-asserted-by":"publisher","first-page":"852","DOI":"10.1109\/34.868686","volume":"22","author":"YA Ivanov","year":"2000","unstructured":"Ivanov, Y.A., Bobick, A.F.: Recognition of visual activities and interactions by stochastic parsing. IEEE Trans. Pattern Anal. Mach. Intell. 22(8), 852\u201372 (2000)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"906_CR16","doi-asserted-by":"publisher","first-page":"1501","DOI":"10.1006\/jmbi.1994.1104","volume":"235","author":"A Krog","year":"1994","unstructured":"Krog, A., Brown, M., Mian, I.S., Sjolander, K., Haussler, D.: Hidden Markov models in computational biology: applications to protein modeling. J. Mol. Biol. 235, 1501\u201331 (1994)","journal-title":"J. Mol. Biol."},{"issue":"1","key":"906_CR17","first-page":"66","volume":"14","author":"M Merler","year":"2011","unstructured":"Merler, M., Huang, B., Xe, L., Hua, G., Natsev, A.: Semantic model vectors for complex video event recognition. IEEE Trans. Multimed. 14(1), 66 (2011)","journal-title":"IEEE Trans. Multimed."},{"key":"906_CR18","doi-asserted-by":"publisher","first-page":"444","DOI":"10.1016\/0022-2836(70)90057-4","volume":"48","author":"S Needlemann","year":"1970","unstructured":"Needlemann, S., Wunsch, C.: A general method applicable to the search for similarities in the amino acid sequences of two proteins. J. Mol. Biol. 48, 444\u201353 (1970)","journal-title":"J. Mol. Biol."},{"issue":"6","key":"906_CR19","doi-asserted-by":"publisher","first-page":"976","DOI":"10.1016\/j.imavis.2009.11.014","volume":"28","author":"R Poppe","year":"2010","unstructured":"Poppe, R.: A survey on vision-based human action recognition. Image Vis. Comput. 28(6), 976\u201390 (2010)","journal-title":"Image Vis. Comput."},{"key":"906_CR20","doi-asserted-by":"crossref","unstructured":"Prabhakar, K., Oh, S., Wang, P., Abowd, G.D., Rehg, J.M.: Temporal causality for the analysis of visual events. In: Proceedings of the International Conference on Computer Vision and Pattern Recognition (2010)","DOI":"10.1109\/CVPR.2010.5539871"},{"key":"906_CR21","first-page":"1","volume":"141","author":"MO Rabin","year":"1969","unstructured":"Rabin, M.O.: Decidability of second order theories and automata on infinite trees. Trans. Am. Math. Soc. 141, 1\u201337 (1969)","journal-title":"Trans. Am. Math. Soc."},{"key":"906_CR22","doi-asserted-by":"crossref","unstructured":"Rabin, M.O.: Automata on Infinite Objects and Church\u2019s Problem. American Mathematical Society, Providence (1972)","DOI":"10.1090\/cbms\/013"},{"key":"906_CR23","doi-asserted-by":"crossref","unstructured":"Ryoo, M.S., Aggarwal, J.K.: Recognition of composite human activities through context-free grammar based representation. In: IEEE Computer Society Conference on Computer vision and pattern recognition (CVPR), vol. 2, pp. 1709\u20131718. IEEE (2006)","DOI":"10.1109\/CVPR.2006.242"},{"key":"906_CR24","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ic.2011.10.010","volume":"211","author":"S Santini","year":"2012","unstructured":"Santini, S.: Regular languages with variables on graphs. Inf. Comput. 211, 1\u201328 (2012)","journal-title":"Inf. Comput."},{"issue":"6","key":"906_CR25","doi-asserted-by":"publisher","first-page":"801","DOI":"10.1007\/s00778-015-0402-5","volume":"24","author":"S Santini","year":"2015","unstructured":"Santini, S.: Querying streams using regular expressions: some semantics, decidability, and efficiency issues. VLDB J. 24(6), 801\u201321 (2015)","journal-title":"VLDB J."},{"key":"906_CR26","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1016\/0196-6774(80)90016-4","volume":"1","author":"P Sellers","year":"1980","unstructured":"Sellers, P.: The theory and computation of evolutionary distances: pattern recognition. J. Algorithms 1, 359\u201373 (1980)","journal-title":"J. Algorithms"},{"key":"906_CR27","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1016\/0022-2836(86)90308-6","volume":"188","author":"WR Taylor","year":"1986","unstructured":"Taylor, W.R.: Identification of protein sequence homology by consensus template alignment. J. Mol. Biol. 188, 233\u201358 (1986)","journal-title":"J. Mol. Biol."},{"key":"906_CR28","unstructured":"Thomas, W.: Logical aspects of the study of tree languages. In: Courcelle, B., (Ed.) Ninth Colloquium on Trees in Algebra and Programming, pp. 31\u201349. Cambridge University Press (1984)"},{"key":"906_CR29","doi-asserted-by":"crossref","unstructured":"Thomas, W.: Automata on infinite objects. In: van Leeuwen, J. (Ed.) Handbook of Theoretical Computer Science, pp. 134\u2013191. Elsevier (1990)","DOI":"10.1016\/B978-0-444-88074-1.50009-3"},{"issue":"6","key":"906_CR30","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1145\/363347.363387","volume":"11","author":"K Thompson","year":"1968","unstructured":"Thompson, K.: Regular expressions search algorithm. Commun. ACM 11(6), 419\u201322 (1968)","journal-title":"Commun. ACM"},{"key":"906_CR31","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1016\/0196-6774(85)90023-9","volume":"6","author":"E Ukkonen","year":"1985","unstructured":"Ukkonen, E.: Finding approximate patterns in strings. J. Algorithms 6, 132\u20137 (1985)","journal-title":"J. Algorithms"},{"issue":"1","key":"906_CR32","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1007\/BF01942606","volume":"15","author":"S Wu","year":"1996","unstructured":"Wu, S., Manber, U., Myers, G.: A subquadratic algorithm for approximate limited expression matching. Algorithmica 15(1), 50\u201367 (1996)","journal-title":"Algorithmica"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00906-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-021-00906-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00906-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,15]],"date-time":"2024-09-15T17:58:44Z","timestamp":1726423124000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-021-00906-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,4]]},"references-count":32,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,2]]}},"alternative-id":["906"],"URL":"https:\/\/doi.org\/10.1007\/s00453-021-00906-8","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2022,1,4]]},"assertion":[{"value":"11 January 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 November 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 January 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}