{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T15:20:02Z","timestamp":1772119202381,"version":"3.50.1"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2025,9,1]],"date-time":"2025-09-01T00:00:00Z","timestamp":1756684800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,9,10]],"date-time":"2025-09-10T00:00:00Z","timestamp":1757462400000},"content-version":"vor","delay-in-days":9,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Umea University"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[2025,9]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>Given a deterministic finite automaton (DFA) A, we present a simple algorithm for constructing deterministic finite automata that accept the shortest forbidden factors, the shortest forbidden prefixes, the shortest forbidden suffixes, the shortest forbidden words, the shortest allowed suffixes, and the shortest allowed words of the automaton A. We refer to these sets as the shortest characteristic factors of the automaton A. If the given automaton is local, and therefore the language it accepts is strictly locally testable, the sets of its shortest characteristic factors are finite, and these automata are acyclic. Otherwise, they accept infinite languages. This approach simplifies existing methods for the extraction of forbidden factors, allows the extraction of more types of characteristic factors, and also generalizes the extraction for all classes of DFAs. Furthermore, we demonstrate that this type of extraction can be used for a sublinear run of an automaton for certain inputs. We define a positive position run of a deterministic finite automaton, representing all positions in an input string where the automaton reaches a final state. Finally, we present an algorithm for computing the positive position run of the automaton, which utilizes pattern set matching of its shortest forbidden factors and its shortest forbidden or allowed suffixes, provided that the sets are finite. We showcase the computation of the positive position run of a local automaton using backward pattern set matching, which can achieve sublinear time.<\/jats:p>","DOI":"10.1007\/s00236-025-00484-0","type":"journal-article","created":{"date-parts":[[2025,9,10]],"date-time":"2025-09-10T09:07:24Z","timestamp":1757495244000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Shortest characteristic factors of a deterministic finite automaton and computing its positive position run by pattern set matching"],"prefix":"10.1007","volume":"62","author":[{"given":"Jan","family":"Janou\u0161ek","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"\u0160t\u011bp\u00e1n","family":"Plach\u00fd","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,9,10]]},"reference":[{"key":"484_CR1","doi-asserted-by":"publisher","unstructured":"Crochemore, M., Hancart, C.: Pattern matching in strings. In: Algorithms and Theory of Computation Handbook. Chapman & Hall\/CRC Applied Algorithms and Data Structures series. CRC Press, Boca Raton (1999). https:\/\/doi.org\/10.1201\/9781420049503-c12","DOI":"10.1201\/9781420049503-c12"},{"key":"484_CR2","volume-title":"Introduction to the Theory of Computation","author":"M Sipser","year":"2013","unstructured":"Sipser, M.: Introduction to the Theory of Computation, 3rd edn. Course Technology, Melbourne (2013)","edition":"3"},{"key":"484_CR3","doi-asserted-by":"publisher","unstructured":"Baeza-Yates, R.A.: A unified view to string matching algorithms. In: SOFSEM 1996. Lecture Notes in Computer Science, vol. 1175, pp. 1\u201315. Springer, Cham (1996). https:\/\/doi.org\/10.1007\/BFb0037393","DOI":"10.1007\/BFb0037393"},{"key":"484_CR4","doi-asserted-by":"publisher","unstructured":"Melichar, B.: String matching with k differences by finite automata. In: ICPR 1996, Vienna, Austria, pp. 256\u2013260. IEEE Computer Society, Piscataway (1996). https:\/\/doi.org\/10.1109\/ICPR.1996.546828","DOI":"10.1109\/ICPR.1996.546828"},{"key":"484_CR5","unstructured":"Melichar, B., Holub, J.: 6d classification of pattern matching problems. In: Proceedings of the Prague Stringology Club Workshop 1997, pp. 24\u201332 (1997)"},{"key":"484_CR6","first-page":"163","volume-title":"Counter-Free Automata","author":"R McNaughton","year":"1971","unstructured":"McNaughton, R., Papert, S.: Counter-Free Automata, vol. 65, p. 163. MIT Press, Cambridge (1971)"},{"issue":"1","key":"484_CR7","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1016\/S0304-3975(98)80011-X","volume":"205","author":"M-P B\u00e9al","year":"1998","unstructured":"B\u00e9al, M.-P., Senellart, J.: On the bound of the synchronization delay of a local automaton. Theor. Comput. Sci. 205(1), 297\u2013306 (1998). https:\/\/doi.org\/10.1016\/S0304-3975(98)80011-X","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"484_CR8","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1016\/S0304-3975(98)00332-6","volume":"242","author":"P Caron","year":"2000","unstructured":"Caron, P.: Families of locally testable languages. Theor. Comput. Sci. 242(1), 361\u2013376 (2000). https:\/\/doi.org\/10.1016\/S0304-3975(98)00332-6","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"484_CR9","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1016\/S0022-0000(72)80020-5","volume":"6","author":"Y Zalcstein","year":"1972","unstructured":"Zalcstein, Y.: Locally testable languages. J. Comput. Syst. Sci. 6(2), 151\u2013167 (1972). https:\/\/doi.org\/10.1016\/S0022-0000(72)80020-5","journal-title":"J. Comput. Syst. Sci."},{"issue":"1\u20132","key":"484_CR10","first-page":"121","volume":"56","author":"M B\u00e9al","year":"2003","unstructured":"B\u00e9al, M., Crochemore, M., Mignosi, F., Restivo, A., Sciortino, M.: Computing forbidden words of regular languages. Fundam. Informatica 56(1\u20132), 121\u2013135 (2003)","journal-title":"Fundam. Informatica"},{"key":"484_CR11","doi-asserted-by":"publisher","unstructured":"Rogers, J., Lambert, D.: Extracting forbidden factors from regular stringsets. In: Proceedings of the 15th Meeting on the Mathematics of Language, pp. 36\u201346. Association for Computational Linguistics, London (2017). https:\/\/doi.org\/10.18653\/v1\/W17-3404","DOI":"10.18653\/v1\/W17-3404"},{"issue":"2","key":"484_CR12","doi-asserted-by":"publisher","first-page":"143","DOI":"10.15398\/jlm.v7i2.209","volume":"7","author":"J Rogers","year":"2019","unstructured":"Rogers, J., Lambert, D.: Extracting subregular constraints from regular stringsets. J. Lang. Model. 7(2), 143 (2019). https:\/\/doi.org\/10.15398\/jlm.v7i2.209","journal-title":"J. Lang. Model."},{"key":"484_CR13","doi-asserted-by":"crossref","unstructured":"Apostolico, A., Galil, Z. (eds.): Pattern Matching Algorithms. Oxford University Press, New York (1997). https:\/\/global.oup.com\/academic\/product\/pattern-matching-algorithms-9780195113679","DOI":"10.1093\/oso\/9780195113679.001.0001"},{"key":"484_CR14","unstructured":"Crochemore, M., Rytter, W.: Text Algorithms. Oxford University Press, New York (1994). http:\/\/www-igm.univ-mlv.fr\/%7Emac\/REC\/B1.html"},{"issue":"11","key":"484_CR15","doi-asserted-by":"publisher","first-page":"1095","DOI":"10.1016\/j.scico.2010.04.012","volume":"75","author":"LG Cleophas","year":"2010","unstructured":"Cleophas, L.G., Watson, B.W., Zwaan, G.: A new taxonomy of sublinear right-to-left scanning keyword pattern matching algorithms. Sci. Comput. Program. 75(11), 1095\u20131112 (2010). https:\/\/doi.org\/10.1016\/j.scico.2010.04.012","journal-title":"Sci. Comput. Program."},{"key":"484_CR16","doi-asserted-by":"publisher","unstructured":"Commentz-Walter, B.: A string matching algorithm fast on the average. In: Automata, Languages and Programming, pp. 118\u2013132. Springer, Berlin, Heidelberg (1979). https:\/\/doi.org\/10.1007\/3-540-09510-1_10","DOI":"10.1007\/3-540-09510-1_10"},{"issue":"2","key":"484_CR17","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/0167-6423(96)00008-1","volume":"27","author":"BW Watson","year":"1996","unstructured":"Watson, B.W., Zwaan, G.: A taxonomy of sublinear multiple keyword pattern matching algorithms. Sci. Comput. Program. 27(2), 85\u2013118 (1996). https:\/\/doi.org\/10.1016\/0167-6423(96)00008-1","journal-title":"Sci. Comput. Program."},{"key":"484_CR18","doi-asserted-by":"publisher","unstructured":"Watson, B.W.: Taxonomies and toolkits of regular language algorithms. PhD thesis, Mathematics and Computer Science, Eindhoven (1995). https:\/\/doi.org\/10.6100\/IR444299","DOI":"10.6100\/IR444299"},{"key":"484_CR19","doi-asserted-by":"publisher","unstructured":"Crochemore, M., Hancart, C.: Automata for matching patterns. In: Handbook of Formal Languages, Volume 2. Linear Modeling: Background and Application, pp. 399\u2013462. Springer, Berlin Heidelberg (1997). https:\/\/doi.org\/10.1007\/978-3-662-07675-0_9","DOI":"10.1007\/978-3-662-07675-0_9"},{"key":"484_CR20","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1007\/978-3-031-52113-3_23","volume-title":"SOFSEM 2024: Theory and Practice of Computer Science","author":"J Janou\u0161ek","year":"2024","unstructured":"Janou\u0161ek, J., Plach\u00fd, \u0160: Shortest characteristic factors of a deterministic finite automaton and computing its positive position run by pattern set matching. In: Fernau, H., Gaspers, S., Klasing, R. (eds.) SOFSEM 2024: Theory and Practice of Computer Science, pp. 326\u2013339. Springer, Cham (2024)"},{"key":"484_CR21","doi-asserted-by":"publisher","unstructured":"Bla\u017eej, V., Janou\u0161ek, J., Plach\u00fd, \u0160.: On the smallest synchronizing terms of finite tree automata. In: CIAA 2023, pp. 79\u201390. Springer, Cham (2023). https:\/\/doi.org\/10.1007\/978-3-031-40247-0_5","DOI":"10.1007\/978-3-031-40247-0_5"},{"key":"484_CR22","doi-asserted-by":"publisher","unstructured":"Plach\u00fd, \u0160., Janou\u0161ek, J.: On synchronizing tree automata and their work\u2014optimal parallel run, usable for parallel tree pattern matching. In: SOFSEM 2020, pp. 576\u2013586. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-38919-2_47","DOI":"10.1007\/978-3-030-38919-2_47"}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-025-00484-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00236-025-00484-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-025-00484-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,22]],"date-time":"2025-09-22T18:02:38Z","timestamp":1758564158000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00236-025-00484-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,9]]},"references-count":22,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,9]]}},"alternative-id":["484"],"URL":"https:\/\/doi.org\/10.1007\/s00236-025-00484-0","relation":{"has-preprint":[{"id-type":"doi","id":"10.21203\/rs.3.rs-4358862\/v1","asserted-by":"object"}]},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"value":"0001-5903","type":"print"},{"value":"1432-0525","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,9]]},"assertion":[{"value":"2 May 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 March 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 September 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"36"}}