{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T04:14:02Z","timestamp":1743135242634,"version":"3.40.3"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2025,2,18]],"date-time":"2025-02-18T00:00:00Z","timestamp":1739836800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,2,18]],"date-time":"2025-02-18T00:00:00Z","timestamp":1739836800000},"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":["Acta Informatica"],"published-print":{"date-parts":[[2025,3]]},"DOI":"10.1007\/s00236-025-00480-4","type":"journal-article","created":{"date-parts":[[2025,2,18]],"date-time":"2025-02-18T08:06:21Z","timestamp":1739865981000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On the piecewise complexity of words"],"prefix":"10.1007","volume":"62","author":[{"given":"Philippe","family":"Schnoebelen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Isa","family":"Vialard","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,2,18]]},"reference":[{"key":"480_CR1","doi-asserted-by":"publisher","unstructured":"Barker, L., Fleischmann, P., Harwardt, K., Manea, F., Nowotka, D.: Scattered factor-universality of words. In: Proceedings of DLT 2020. Lecture Notes in Computer Science, vol. 12086, pp. 14\u201328. Springer (2020). https:\/\/doi.org\/10.1007\/978-3-030-48516-0_2","DOI":"10.1007\/978-3-030-48516-0_2"},{"key":"480_CR2","doi-asserted-by":"publisher","DOI":"10.2168\/LMCS-8(3:26)2012","author":"M Boja\u0144czyk","year":"2012","unstructured":"Boja\u0144czyk, M., Segoufin, L., Straubing, H.: Piecewise testable tree languages. Log. Methods Comput. Sci. (2012). https:\/\/doi.org\/10.2168\/LMCS-8(3:26)2012","journal-title":"Log. Methods Comput. Sci."},{"key":"480_CR3","doi-asserted-by":"publisher","unstructured":"Carton, O., Pouzet, M.: Simon\u2019s theorem for scattered words. In: Proceedings of DLT 2018. Lecture Notes in Computer Science, vol. 11088, pp. 182\u2013193. Springer (2018). https:\/\/doi.org\/10.1007\/978-3-319-98654-8_15","DOI":"10.1007\/978-3-319-98654-8_15"},{"issue":"3","key":"480_CR4","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1142\/S0129054108005802","volume":"19","author":"V Diekert","year":"2008","unstructured":"Diekert, V., Gastin, P., Kufleitner, M.: A survey on small fragments of first-order logic over finite words. Int. J. Found. Comput. Sci. 19(3), 513\u2013548 (2008). https:\/\/doi.org\/10.1142\/S0129054108005802","journal-title":"Int. J. Found. Comput. Sci."},{"key":"480_CR5","doi-asserted-by":"publisher","unstructured":"Fleischer, L., Kufleitner, M.: Testing Simon\u2019s congruence. In: Proceedings of MFCS 2018. Leibniz International Proceedings in Informatics, vol. 117, pp. 62\u201316213. Leibniz-Zentrum f\u00fcr Informatik (2018). https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2018.62","DOI":"10.4230\/LIPIcs.MFCS.2018.62"},{"key":"480_CR6","doi-asserted-by":"publisher","unstructured":"Gawrychowski, P., Kosche, M., Ko\u00df, T., Manea, F., Siemer, S.: Efficiently testing Simon\u2019s congruence. In: Proceedings of STACS 2021. Leibniz International Proceedings in Informatics, vol. 187, pp. 34\u201313418. Leibniz-Zentrum f\u00fcr Informatik (2021). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2021.34","DOI":"10.4230\/LIPIcs.STACS.2021.34"},{"key":"480_CR7","doi-asserted-by":"publisher","unstructured":"Goubault-Larrecq, J., Schmitz, S.: Deciding piecewise testable separability for regular tree languages. In: Proceedings of ICALP 2016. Leibniz International Proceedings in Informatics, vol. 55, pp. 97\u201319715. Leibniz-Zentrum f\u00fcr Informatik (2016). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2016.97","DOI":"10.4230\/LIPIcs.ICALP.2016.97"},{"key":"480_CR8","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1016\/j.ipl.2019.01.012","volume":"145","author":"S Halfon","year":"2019","unstructured":"Halfon, S., Schnoebelen, Ph.: On shuffle products, acyclic automata and piecewise-testable languages. Inf. Process. Lett. 145, 68\u201373 (2019). https:\/\/doi.org\/10.1016\/j.ipl.2019.01.012","journal-title":"Inf. Process. Lett."},{"key":"480_CR9","doi-asserted-by":"publisher","unstructured":"Karandikar, P., Schnoebelen, Ph.: The height of piecewise-testable languages and the complexity of the logic of subwords. Log. Methods Comput. Sci. (2019) https:\/\/doi.org\/10.23638\/LMCS-15(2:6)2019","DOI":"10.23638\/LMCS-15(2:6)2019"},{"key":"480_CR10","doi-asserted-by":"publisher","unstructured":"Karandikar, P., Schnoebelen, Ph.: The height of piecewise-testable languages with applications in logical complexity. In: Proceedings of CSL 2016. Leibniz International Proceedings in Informatics, vol. 62, pp. 37\u201313722. Leibniz-Zentrum f\u00fcr Informatik (2016). https:\/\/doi.org\/10.4230\/LIPIcs.CSL.2016.37","DOI":"10.4230\/LIPIcs.CSL.2016.37"},{"issue":"4","key":"480_CR11","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, Ph.: On the index of Simon\u2019s congruence for piecewise testability. Inf. Process. Lett. 115(4), 515\u2013519 (2015). https:\/\/doi.org\/10.1016\/j.ipl.2014.11.008","journal-title":"Inf. Process. Lett."},{"issue":"20","key":"480_CR12","doi-asserted-by":"publisher","first-page":"2124","DOI":"10.1016\/j.disc.2011.06.013","volume":"311","author":"O Kl\u00edma","year":"2011","unstructured":"Kl\u00edma, O.: Piecewise testable languages via combinatorics on words. Discrete Math. 311(20), 2124\u20132127 (2011). https:\/\/doi.org\/10.1016\/j.disc.2011.06.013","journal-title":"Discrete Math."},{"issue":"3","key":"480_CR13","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1016\/j.tcs.2008.06.037","volume":"405","author":"L Kontorovich","year":"2008","unstructured":"Kontorovich, L., Cortes, C., Mohri, M.: Kernel methods for learning languages. Theoret. Comput. Sci. 405(3), 223\u2013236 (2008). https:\/\/doi.org\/10.1016\/j.tcs.2008.06.037","journal-title":"Theoret. Comput. Sci."},{"key":"480_CR14","doi-asserted-by":"publisher","unstructured":"Masopust, T., Thomazo, M.: On the complexity of $$k$$-piecewise testability and the depth of automata. In: Proceedings of DLT 2015. Lecture Notes in Computer Science, vol. 9168, pp. 364\u2013376. Springer, (2015). https:\/\/doi.org\/10.1007\/978-3-319-21500-6_29","DOI":"10.1007\/978-3-319-21500-6_29"},{"key":"480_CR15","doi-asserted-by":"publisher","unstructured":"Matz, O.: On piecewise testable, starfree, and recognizable picture languages. In: Proceedings of FOSSACS \u201998. Lecture Notes in Computer Science, vol. 1378, pp. 203\u2013210. Springer (1998). https:\/\/doi.org\/10.1007\/BFb0053551","DOI":"10.1007\/BFb0053551"},{"key":"480_CR16","unstructured":"Perrin, D., Pin, J.-\u00c9.: Infinite Words: Automata, Semigroups, Logic and Games. Pure and Applied Mathematics Series, vol. 141. Elsevier Science (2004)"},{"key":"480_CR17","doi-asserted-by":"crossref","unstructured":"Pin, J.-\u00c9.: Varieties of Formal Languages. Plenum, New-York (1986)","DOI":"10.1007\/978-1-4613-2215-3"},{"key":"480_CR18","doi-asserted-by":"publisher","unstructured":"Place, Th., Zeitoun, M.: A generic polynomial time approach to separation by first-order logic without quantifier alternation. In: Proceedings of FST &TCS 2022. Leibniz International Proceedings in Informatics, vol. 250, pp. 43\u201314322. Leibniz-Zentrum f\u00fcr Informatik (2022). https:\/\/doi.org\/10.4230\/LIPICS.FSTTCS.2022.43","DOI":"10.4230\/LIPICS.FSTTCS.2022.43"},{"key":"480_CR19","doi-asserted-by":"publisher","unstructured":"Praveen, M., Schnoebelen, Ph., Veron, J., Vialard, I.: On the piecewise complexity of words and periodic words. In: Proceedings of SOFSEM 2024. Lecture Notes in Computer Science, vol. 14519, pp. 456\u2013470. Springer (2024). https:\/\/doi.org\/10.1007\/978-3-031-52113-3_32","DOI":"10.1007\/978-3-031-52113-3_32"},{"key":"480_CR20","doi-asserted-by":"publisher","unstructured":"Rogers, J., Heinz, J., Fero, M., Hurst, J., Lambert, D., Wibel, S.: Cognitive and sub-regular complexity. In: Proceedings of FG 2012 & 2013. Lecture Notes in Computer Science, vol. 8036, pp. 90\u2013108. Springer (2013). https:\/\/doi.org\/10.1007\/978-3-642-39998-5_6","DOI":"10.1007\/978-3-642-39998-5_6"},{"key":"480_CR21","unstructured":"Sakarovitch, J., Simon, I.: Subwords. In: Lothaire, M. (ed.) Combinatorics on Words. Encyclopedia of Mathematics and Its Applications, vol. 17, Chapter 6 pp. 105\u2013142. Cambridge University Press (1983)."},{"key":"480_CR22","unstructured":"Simon, I.: Hierarchies of events with dot-depth one. Ph.D. thesis, University of Waterloo, Waterloo, ON, Canada (1972). http:\/\/maveric.uwaterloo.ca\/reports\/1972_Simon_PhD.pdf"},{"key":"480_CR23","doi-asserted-by":"publisher","unstructured":"Simon, I.: Piecewise testable events. In: Proceedings of 2nd GI Conference on Automata Theory and Formal Languages. Lecture Notes in Computer Science, vol. 33, pp. 214\u2013222. Springer (1975).https:\/\/doi.org\/10.1007\/3-540-07407-4_23","DOI":"10.1007\/3-540-07407-4_23"},{"key":"480_CR24","unstructured":"Simon, I.: Words distinguished by their subwords. In: Proceedings of WORDS 2003 (2003)"},{"issue":"3","key":"480_CR25","doi-asserted-by":"publisher","first-page":"360","DOI":"10.1016\/0022-0000(82)90016-2","volume":"25","author":"W Thomas","year":"1982","unstructured":"Thomas, W.: Classifying regular events in symbolic logic. J. Comput. Syst. Sci. 25(3), 360\u2013376 (1982). https:\/\/doi.org\/10.1016\/0022-0000(82)90016-2","journal-title":"J. Comput. Syst. Sci."},{"key":"480_CR26","doi-asserted-by":"publisher","unstructured":"Zetzsche, G.: Separability by piecewise testable languages and downward closures beyond subwords. In: Proceedings of LICS 2018, pp. 929\u2013938. ACM Press (2018). https:\/\/doi.org\/10.1145\/3209108.3209201","DOI":"10.1145\/3209108.3209201"}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-025-00480-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00236-025-00480-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-025-00480-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T01:50:27Z","timestamp":1743126627000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00236-025-00480-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2,18]]},"references-count":26,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,3]]}},"alternative-id":["480"],"URL":"https:\/\/doi.org\/10.1007\/s00236-025-00480-4","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"type":"print","value":"0001-5903"},{"type":"electronic","value":"1432-0525"}],"subject":[],"published":{"date-parts":[[2025,2,18]]},"assertion":[{"value":"13 May 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 January 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 February 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"15"}}