{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,11]],"date-time":"2026-08-11T19:28:05Z","timestamp":1786476485925,"version":"build-2736575974"},"publisher-location":"Cham","reference-count":30,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032311764","type":"print"},{"value":"9783032359674","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"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-31176-4_8","type":"book-chapter","created":{"date-parts":[[2026,8,11]],"date-time":"2026-08-11T18:44:28Z","timestamp":1786473868000},"page":"108-123","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Pattern Matching Under $$\\mathcal {R}$$-Congruence"],"prefix":"10.1007","author":[{"given":"Sungmin","family":"Kim","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hyundong","family":"Jin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yo-Sub","family":"Han","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,8,5]]},"reference":[{"key":"8_CR1","doi-asserted-by":"crossref","unstructured":"Barker, L., Fleischmann, P., Harwardt, K., Manea, F., Nowotka, D.: Scattered factor-universality of words. In: Proceedings of the 24th International Conference on Developments in Language Theory, DLT, pp. 14\u201328 (2020)","DOI":"10.1007\/978-3-030-48516-0_2"},{"issue":"1","key":"8_CR2","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1016\/0022-0000(80)90003-3","volume":"20","author":"J Brzozowski","year":"1980","unstructured":"Brzozowski, J., Fich, F.E.: Languages of $$\\cal{R} $$-trivial monoids. J. Comput. Syst. Sci. 20(1), 32\u201349 (1980)","journal-title":"J. Comput. Syst. Sci."},{"issue":"07","key":"8_CR3","doi-asserted-by":"publisher","first-page":"807","DOI":"10.1142\/S0129054114400097","volume":"25","author":"J Brzozowski","year":"2014","unstructured":"Brzozowski, J., Li, B.: Syntactic complexity of $$\\cal{R} $$- and $$\\cal{J} $$-trivial languages. Int. J. Found. Comput. Sci. 25(07), 807\u2013821 (2014)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"8_CR4","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2025.103681","volume":"154","author":"JD Day","year":"2025","unstructured":"Day, J.D., Fleischmann, P., Kosche, M., Ko\u00df, T., Manea, F., Siemer, S.: The edit distance to $$k$$-subsequence universality. J. Comput. Syst. Sci. 154, 103681 (2025)","journal-title":"J. Comput. Syst. Sci."},{"key":"8_CR5","unstructured":"Fleischer, L., Kufleitner, M.: Testing Simon\u2019s congruence. In: Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS, pp. 62:1\u201362:13 (2018)"},{"key":"8_CR6","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2023.114113","volume":"974","author":"P Fleischmann","year":"2023","unstructured":"Fleischmann, P., Haschke, L., H\u00f6fer, J., Huch, A., Mayrock, A., Nowotka, D.: Nearly k-universal words - investigating a part of Simon\u2019s congruence. Theoret. Comput. Sci. 974, 114113 (2023)","journal-title":"Theoret. Comput. Sci."},{"key":"8_CR7","doi-asserted-by":"crossref","unstructured":"Fleischmann, P., H\u00f6fer, J., Huch, A., Nowotka, D.: $$\\alpha $$-$$\\beta $$-factorization and the binary case of Simon\u2019s congruence. In: Proceedings of the 24th International Symposium on Fundamentals of Computation Theory, FCT, pp. 190\u2013204 (2023)","DOI":"10.1007\/978-3-031-43587-4_14"},{"key":"8_CR8","doi-asserted-by":"crossref","unstructured":"Fleischmann, P., et al.: Matching patterns with variables under Simon\u2019s congruence. In: Proceedings of the 17th International Conference on Reachability Problems, RP, pp. 155\u2013170 (2023)","DOI":"10.1007\/978-3-031-45286-4_12"},{"key":"8_CR9","unstructured":"Gawrychowski, P., Kosche, M., Ko\u00df, T., Manea, F., Siemer, S.: Efficiently testing Simon\u2019s congruence. In: Proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science, STACS, pp. 34:1\u201334:18 (2021)"},{"issue":"1","key":"8_CR10","doi-asserted-by":"publisher","first-page":"163","DOI":"10.2307\/1969317","volume":"54","author":"JA Green","year":"1951","unstructured":"Green, J.A.: On the structure of semigroups. Ann. Math. 54(1), 163\u2013172 (1951)","journal-title":"Ann. Math."},{"issue":"1","key":"8_CR11","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/0304-3975(91)90170-7","volume":"82","author":"J H\u00e9brard","year":"1991","unstructured":"H\u00e9brard, J.: An algorithm for distinguishing efficiently bit-strings by their subsequences. Theoret. Comput. Sci. 82(1), 35\u201349 (1991)","journal-title":"Theoret. Comput. Sci."},{"key":"8_CR12","doi-asserted-by":"crossref","unstructured":"Jir\u00e1skov\u00e1, G., Masopust, T.: On the state complexity of the reverse of $$\\cal{R}$$- and $$\\cal{J}$$-trivial regular languages. In: Proceedings of the International Workshop on Descriptional Complexity of Formal Systems, pp. 136\u2013147 (2013)","DOI":"10.1007\/978-3-642-39310-5_14"},{"issue":"4","key":"8_CR13","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1016\/j.ipl.2014.11.008","volume":"115","author":"P Karandikar","year":"2015","unstructured":"Karandikar, P., Kufleitner, M., Schnoebelen, P.: On the index of Simon\u2019s congruence for piecewise testability. Inf. Process. Lett. 115(4), 515\u2013519 (2015)","journal-title":"Inf. Process. Lett."},{"key":"8_CR14","doi-asserted-by":"crossref","unstructured":"Kim, S., Han, Y.S.: Pattern mining under Simon\u2019s congruence. In: Proceedings of the 29th International Conference on Developments in Language Theory, DLT, pp. 182\u2013196 (2025)","DOI":"10.1007\/978-3-032-01475-7_13"},{"key":"8_CR15","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2023.114078","volume":"972","author":"S Kim","year":"2023","unstructured":"Kim, S., Han, Y.S., Ko, S.K., Salomaa, K.: On Simon\u2019s congruence closure of a string. Theoret. Comput. Sci. 972, 114078 (2023)","journal-title":"Theoret. Comput. Sci."},{"key":"8_CR16","doi-asserted-by":"crossref","unstructured":"Kim, S., Han, Y.S., Ko, S.K., Salomaa, K.: On the Simon\u2019s congruence neighborhood of languages. In: Proceedings of the 27th International Conference on Developments in Language Theory, DLT, pp. 168\u2013181 (2023)","DOI":"10.1007\/978-3-031-33264-7_14"},{"key":"8_CR17","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2024.114478","volume":"994","author":"S Kim","year":"2024","unstructured":"Kim, S., Ko, S.K., Han, Y.S.: Simon\u2019s congruence pattern matching. Theoret. Comput. Sci. 994, 114478 (2024)","journal-title":"Theoret. Comput. Sci."},{"issue":"2","key":"8_CR18","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1137\/0206024","volume":"6","author":"DE Knuth","year":"1977","unstructured":"Knuth, D.E., Morris, J.H., Jr., Pratt, V.R.: Fast pattern matching in strings. SIAM J. Comput. 6(2), 323\u2013350 (1977)","journal-title":"SIAM J. Comput."},{"key":"8_CR19","doi-asserted-by":"crossref","unstructured":"Li, J., Cotterell, R.: Characterizing the expressivity of fixed-precision transformer language models. In: Proceedings of the 39th Annual Conference on Neural Information Processing Systems, NeurIPS (2025)","DOI":"10.52202\/085713-5329"},{"key":"8_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1007\/978-3-319-73117-9_29","volume-title":"SOFSEM 2018: Theory and Practice of Computer Science","author":"T Masopust","year":"2018","unstructured":"Masopust, T., Kr\u00f6tzsch, M.: Deciding universality of ptNFAs is PSpace-complete. In: Tjoa, A.M., Bellatreche, L., Biffl, S., van Leeuwen, J., Wiedermann, J. (eds.) SOFSEM 2018. LNCS, vol. 10706, pp. 413\u2013427. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-73117-9_29"},{"key":"8_CR21","doi-asserted-by":"crossref","unstructured":"Masopust, T., Kr\u00f6tzsch, M.: Partially ordered automata and piecewise testability. Logical Methods Comput. Sci. 17(2) (2021)","DOI":"10.23638\/LMCS-17(2:14)2021"},{"key":"8_CR22","doi-asserted-by":"crossref","unstructured":"Masopust, T., Thomazo, M.: On the complexity of $$k$$-piecewise testability and the depth of automata. In: Proceedings of the 19th International Conference on Developments in Language Theory, DLT, pp. 364\u2013376 (2015)","DOI":"10.1007\/978-3-319-21500-6_29"},{"key":"8_CR23","doi-asserted-by":"crossref","unstructured":"Pach, P.P.: Normal forms under Simon\u2019s congruence. In: Semigroup Forum, vol. 97, pp. 251\u2013267 (2018)","DOI":"10.1007\/s00233-017-9910-5"},{"key":"8_CR24","unstructured":"Pin, J.E.: Varieties of Formal Languages. North Oxford Academic (1989), translated by A. Howie"},{"key":"8_CR25","doi-asserted-by":"crossref","unstructured":"Schnoebelen, P., Veron, J.: On arch factorization and subword universality for words and compressed words. In: Proceedings of the 14th International Conference on Combinatorics on Words, WORDS, pp. 274\u2013287 (2023)","DOI":"10.1007\/978-3-031-33180-0_21"},{"key":"8_CR26","doi-asserted-by":"crossref","unstructured":"Schwentick, T., Th\u00e9rien, D., Vollmer, H.: Partially-ordered two-way automata: A new characterization of DA. In: Proceedings of the 5th International Conference on Developments in Language Theory, DLT, pp. 239\u2013250 (2001)","DOI":"10.1007\/3-540-46011-X_20"},{"key":"8_CR27","doi-asserted-by":"publisher","unstructured":"Simon, I.: Piecewise testable events. In: Brakhage, H. (ed.) GI-Fachtagung 1975. LNCS, vol. 33, pp. 214\u2013222. Springer, Heidelberg (1975). https:\/\/doi.org\/10.1007\/3-540-07407-4_23","DOI":"10.1007\/3-540-07407-4_23"},{"issue":"2","key":"8_CR28","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1016\/0021-8693(88)90067-1","volume":"119","author":"H Straubing","year":"1988","unstructured":"Straubing, H., Th\u00e9rien, D.: Partially ordered finite monoids and a theorem of I. Simon. J. Algebra 119(2), 393\u2013399 (1988)","journal-title":"Simon. J. Algebra"},{"key":"8_CR29","unstructured":"Vaswani, A., et al.: Attention is all you need. In: Proceedings of the 30th Annual Conference on Neural Information Processing Systems, pp. 5998\u20136008. NeurIPS (2017)"},{"key":"8_CR30","doi-asserted-by":"crossref","unstructured":"Weis, P., Immerman, N.: Structure theorem and strict alternation hierarchy for FO$$^2$$ on words. Logical Methods in Computer Science 5 (2009)","DOI":"10.2168\/LMCS-5(3:4)2009"}],"container-title":["Lecture Notes in Computer Science","Implementation and Application of Automata"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-31176-4_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,11]],"date-time":"2026-08-11T18:44:32Z","timestamp":1786473872000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-31176-4_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9783032311764","9783032359674"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-31176-4_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026]]},"assertion":[{"value":"5 August 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CIAA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Implementation and Application of Automata","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Kingston","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Canada","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2026","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"5 May 2026","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"8 May 2026","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"30","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wia2026","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/research.cs.queensu.ca\/ciaa2026\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}