{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,1]],"date-time":"2025-11-01T08:40:38Z","timestamp":1761986438126,"version":"build-2065373602"},"publisher-location":"Cham","reference-count":15,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319214993"},{"type":"electronic","value":"9783319215006"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"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":[[2015]]},"DOI":"10.1007\/978-3-319-21500-6_29","type":"book-chapter","created":{"date-parts":[[2015,7,17]],"date-time":"2015-07-17T08:07:44Z","timestamp":1437120464000},"page":"364-376","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["On the Complexity of k-Piecewise Testability and the Depth of Automata"],"prefix":"10.1007","author":[{"given":"Tom\u00e1\u0161","family":"Masopust","sequence":"first","affiliation":[]},{"given":"Micha\u00ebl","family":"Thomazo","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,7,18]]},"reference":[{"issue":"9","key":"29_CR1","doi-asserted-by":"publisher","first-page":"809","DOI":"10.1016\/0898-1221(89)90179-X","volume":"18","author":"F Blanchet-Sadri","year":"1989","unstructured":"Blanchet-Sadri, F.: Games, equations and the dot-depth hierarchy. Comput. Math. Appl. 18(9), 809\u2013822 (1989)","journal-title":"Comput. Math. Appl."},{"issue":"2","key":"29_CR2","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1016\/0304-3975(92)00064-X","volume":"123","author":"F Blanchet-Sadri","year":"1994","unstructured":"Blanchet-Sadri, F.: Equations and monoid varieties of dot-depth one and two. Theoret. Comput. Sci. 123(2), 239\u2013258 (1994)","journal-title":"Theoret. Comput. Sci."},{"issue":"1","key":"29_CR3","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/0304-3975(91)90075-D","volume":"88","author":"S Cho","year":"1991","unstructured":"Cho, S., Huynh, D.T.: Finite-automaton aperiodicity is PSPACE-complete. Theor. Comput. Sci. 88(1), 99\u2013116 (1991)","journal-title":"Theor. Comput. Sci."},{"key":"29_CR4","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman (1979)"},{"key":"29_CR5","unstructured":"Hofman, P., Martens, W.: Separability by short subsequences and subwords. In: ICDT. LIPIcs, vol. 31, pp. 230\u2013246 (2015)"},{"key":"29_CR6","unstructured":"Holub, \u0160., Masopust, T., Thomazo, M.: Alternating towers and piecewise testable separators. CoRR abs\/1409.3943 (2014). 1409.3943"},{"issue":"5","key":"29_CR7","doi-asserted-by":"publisher","first-page":"935","DOI":"10.1137\/0217058","volume":"17","author":"N Immerman","year":"1988","unstructured":"Immerman, N.: Nondeterministic space is closed under complementation. SIAM J. Comput. 17(5), 935\u2013938 (1988)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"29_CR8","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. Inform. Process. Lett. 115(4), 515\u2013519 (2015)","journal-title":"Inform. Process. Lett."},{"key":"29_CR9","unstructured":"Kl\u00edma, O., Kunc, M., Pol\u00e1k, L.: Deciding $$k$$-piecewise testability (manuscript)"},{"key":"29_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1007\/978-3-642-38771-5_26","volume-title":"Developments in Language Theory","author":"O Kl\u00edma","year":"2013","unstructured":"Kl\u00edma, O., Pol\u00e1k, L.: Alternative automata characterization of piecewise testable languages. In: B\u00e9al, M.-P., Carton, O. (eds.) DLT 2013. LNCS, vol. 7907, pp. 289\u2013300. Springer, Heidelberg (2013)"},{"key":"29_CR11","unstructured":"Masopust, T., Thomazo, M.: On $$k$$-piecewise testability (preliminary report). CoRR abs\/1412.1641 (2014), 1412.1641"},{"key":"29_CR12","doi-asserted-by":"crossref","unstructured":"Sakarovitch, J., Simon, I.: Subwords. In: Lothaire, M. (ed.) Combinatorics on Words, pp. 105\u2013142. Cambridge University Press (1997)","DOI":"10.1017\/CBO9780511566097.009"},{"key":"29_CR13","unstructured":"Simon, I.: Hierarchies of Events with Dot-Depth One. Ph.D. thesis, Department of Applied Analysis and Computer Science. University of Waterloo, Canada (1972)"},{"issue":"3","key":"29_CR14","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/BF00299636","volume":"26","author":"R Szelepcs\u00e9nyi","year":"1988","unstructured":"Szelepcs\u00e9nyi, R.: The method of forced enumeration for nondeterministic automata. Acta Inf. 26(3), 279\u2013284 (1988)","journal-title":"Acta Inf."},{"key":"29_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1007\/3-540-44669-9_33","volume-title":"Fundamentals of Computation Theory","author":"AN Trahtman","year":"2001","unstructured":"Trahtman, A.N.: Piecewise and local threshold testability of DFA. In: Freivalds, R. (ed.) FCT 2001. LNCS, vol. 2138, pp. 347\u2013358. Springer, Heidelberg (2001)"}],"container-title":["Lecture Notes in Computer Science","Developments in Language Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-21500-6_29","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,8]],"date-time":"2023-02-08T14:09:08Z","timestamp":1675865348000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-21500-6_29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319214993","9783319215006"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-21500-6_29","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"18 July 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}