{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:25:29Z","timestamp":1740108329951,"version":"3.37.3"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2019,11,7]],"date-time":"2019-11-07T00:00:00Z","timestamp":1573084800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,11,7]],"date-time":"2019-11-07T00:00:00Z","timestamp":1573084800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100004663","name":"Ministry of Science and Technology, Taiwan","doi-asserted-by":"publisher","award":["107-2221-E-002- 026-MY2"],"award-info":[{"award-number":["107-2221-E-002- 026-MY2"]}],"id":[{"id":"10.13039\/501100004663","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[2021,4]]},"DOI":"10.1007\/s00236-019-00347-5","type":"journal-article","created":{"date-parts":[[2019,11,7]],"date-time":"2019-11-07T00:13:27Z","timestamp":1573085607000},"page":"35-56","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Subsequence versus substring constraints in sequence pattern languages"],"prefix":"10.1007","volume":"58","author":[{"given":"Steven","family":"Engels","sequence":"first","affiliation":[]},{"given":"Tony","family":"Tan","sequence":"additional","affiliation":[]},{"given":"Jan","family":"Van den Bussche","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,11,7]]},"reference":[{"key":"347_CR1","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1002\/malq.19600060105","volume":"6","author":"JR B\u00fcchi","year":"1960","unstructured":"B\u00fcchi, J.R.: Weak second-order arithmetic and finite automata. Zeitschrift f\u00fcr Mathematische Logic und Grundlagen der Mathematik 6, 66\u201392 (1960)","journal-title":"Zeitschrift f\u00fcr Mathematische Logic und Grundlagen der Mathematik"},{"key":"347_CR2","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/0022-0000(78)90049-1","volume":"16","author":"JA Brzozowski","year":"1978","unstructured":"Brzozowski, J.A., Knast, R.: The dot-depth hierarchy of star-free languages is infinite. J. Comput. Syst. Sci. 16, 37\u201355 (1978)","journal-title":"J. Comput. Syst. Sci."},{"key":"347_CR3","volume-title":"Modern Information Retrieval","author":"R Baeza-Yates","year":"1999","unstructured":"Baeza-Yates, R., Ribeiro-Neto, B.: Modern Information Retrieval. Addison-Wesley, Boston (1999)"},{"issue":"1","key":"347_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0022-0000(71)80003-X","volume":"5","author":"RS Cohen","year":"1971","unstructured":"Cohen, R.S., Brzozowski, J.A.: Dot-depth of star-free events. J. Comput. Syst. Sci. 5(1), 1\u201316 (1971)","journal-title":"J. Comput. Syst. Sci."},{"key":"347_CR5","volume-title":"Sequence Data Mining","author":"G Dong","year":"2007","unstructured":"Dong, G., Pei, J.: Sequence Data Mining. Springer, Berlin (2007)"},{"key":"347_CR6","doi-asserted-by":"crossref","unstructured":"Faloutsos, Ch., Ranganathan, M., Manolopoulos, Y.: Fast subsequence matching in time-series databases. In: Proceedings ACM SIGMOD International Conference on Management of Data, pp. 419\u2013429 (1994)","DOI":"10.1145\/191843.191925"},{"key":"347_CR7","doi-asserted-by":"crossref","unstructured":"Genkin, D., Kaminski, M., Peterfreund, L.: Closure Under Reversal of Languages over Infinite Alphabets. In: Fomin, E., Podolskii, V. (eds.),Computer Science Symposium in Russia, Proceedings (CSR), volume 10846 of Lecture Notes in Computer Science, Springer, pp. 145\u2013156 (2018)","DOI":"10.1007\/978-3-319-90530-3_13"},{"key":"347_CR8","doi-asserted-by":"crossref","unstructured":"Jagadish, H.V., et\u00a0al.: Making database systems usable. In: Proceedings of the ACM SIGMOD International Conference on Management of Data, pp. 13\u201324 (2007)","DOI":"10.1145\/1247480.1247483"},{"key":"347_CR9","first-page":"301","volume":"69","author":"M Kaminski","year":"2006","unstructured":"Kaminski, M., Tan, T.: Regular expressions for languages over infinite alphabets. Fundam. Inf. 69, 301\u2013318 (2006)","journal-title":"Fundam. Inf."},{"issue":"1","key":"347_CR10","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1145\/181550.181565","volume":"23","author":"A Loeffen","year":"1994","unstructured":"Loeffen, A.: Text databases: a survey of text models and systems. SIGMOD Record 23(1), 97\u2013106 (1994)","journal-title":"SIGMOD Record"},{"key":"347_CR11","volume-title":"Counter-Free Automata","author":"R McNaughton","year":"1971","unstructured":"McNaughton, R., Papert, S.: Counter-Free Automata. MIT Press, Cambridge (1971)"},{"issue":"3","key":"347_CR12","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1145\/1013560.1013562","volume":"5","author":"F Neven","year":"2004","unstructured":"Neven, F., Schwentick, T., Vianu, V.: Finite state machines for strings over infinite alphabets. ACM Trans. Comput. Logic 5(3), 403\u2013435 (2004)","journal-title":"ACM Trans. Comput. Logic"},{"key":"347_CR13","unstructured":"Patel, J.M.: Special issue on querying biological sequences. IEEE Data Eng. Bull. 27(3), (2004)"},{"key":"347_CR14","unstructured":"Peterfreund, L.: Closure under reversal of languages over infinite alphabets: a case study. Master thesis, Department of Computer Science, Technion\u2014Israel Institute of Technology (2015)"},{"key":"347_CR15","doi-asserted-by":"crossref","unstructured":"Pin, J.E.: Syntactic semigroups. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, vol. 1, chapter\u00a010. Springer (1997)","DOI":"10.1007\/978-3-642-59136-5_10"},{"key":"347_CR16","doi-asserted-by":"crossref","unstructured":"Pin, J.E.: The dot-depth hierarchy, 45 years later. The role of theory in computer science, pp. 177\u2013202 (2017)","DOI":"10.1142\/9789813148208_0008"},{"key":"347_CR17","doi-asserted-by":"crossref","unstructured":"Place, T., van Rooijen, L., Zeitoun, M.: Separating regular languages by locally testable and locally threshold testable languages. Logical Methods Comput. Sci. 10(3) (2014)","DOI":"10.2168\/LMCS-10(3:24)2014"},{"key":"347_CR18","doi-asserted-by":"crossref","unstructured":"Segoufin, L.: Automata and logics for words and trees over an infinite alphabet. In: \u00c9sik, Z. (ed.) Computer Science Logic, Proceedings (CSL), volume 4207 of Lecture Notes in Computer Science, Springer, pp. 41\u201357 (2006)","DOI":"10.1007\/11874683_3"},{"key":"347_CR19","doi-asserted-by":"crossref","unstructured":"Simon, I.: Piecewise testable events. In: Barkhage, H. (ed.) Automata Theory and Formal Languages, Proceedings, volume 33 of Lecture Notes in Computer Science, Springer, pp. 214\u2013222 (1975)","DOI":"10.1007\/3-540-07407-4_23"},{"issue":"8","key":"347_CR20","doi-asserted-by":"publisher","first-page":"778","DOI":"10.1016\/j.jcss.2010.03.004","volume":"76","author":"T Tan","year":"2010","unstructured":"Tan, T.: On pebble automata for data languages with decidable emptiness problem. J. Comput. Syst. Sci. 76(8), 778\u2013791 (2010)","journal-title":"J. Comput. Syst. Sci."},{"key":"347_CR21","doi-asserted-by":"crossref","unstructured":"Tan, T.: Graph reachability and pebble automata over infinite alphabets. ACM Trans. Comput. Logic 14(3), 19 (2013)","DOI":"10.1145\/2499937.2499940"},{"key":"347_CR22","doi-asserted-by":"crossref","unstructured":"Thomas, W.: A concatenation game and the dot-depth hierarchy. In: Computation Theory and Logic, volume 270 of Lecture Notes in Computer Science, Springer-Verlag, pp. 415\u2013426 (1987)","DOI":"10.1007\/3-540-18170-9_183"},{"key":"347_CR23","doi-asserted-by":"crossref","unstructured":"Thomas, W.: Languages, automata, and logic. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, vol. 3, chapter\u00a07. Springer (1997)","DOI":"10.1007\/978-3-642-59126-6_7"},{"volume-title":"Pattern Discovery in Biomolecular Data","year":"1999","key":"347_CR24","unstructured":"Wang, J.T.L., Shapiro, B.A., Shasha, D. (eds.): Pattern Discovery in Biomolecular Data. Oxford University Press, Oxford (1999)"}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-019-00347-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00236-019-00347-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-019-00347-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,27]],"date-time":"2021-03-27T04:39:30Z","timestamp":1616819970000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00236-019-00347-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,11,7]]},"references-count":24,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2021,4]]}},"alternative-id":["347"],"URL":"https:\/\/doi.org\/10.1007\/s00236-019-00347-5","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"type":"print","value":"0001-5903"},{"type":"electronic","value":"1432-0525"}],"subject":[],"published":{"date-parts":[[2019,11,7]]},"assertion":[{"value":"5 October 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 October 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 November 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}