{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:17:32Z","timestamp":1760203052067},"publisher-location":"Cham","reference-count":33,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319731162"},{"type":"electronic","value":"9783319731179"}],"license":[{"start":{"date-parts":[[2017,12,22]],"date-time":"2017-12-22T00:00:00Z","timestamp":1513900800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-73117-9_29","type":"book-chapter","created":{"date-parts":[[2017,12,21]],"date-time":"2017-12-21T16:45:34Z","timestamp":1513874734000},"page":"413-427","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Deciding Universality of ptNFAs is PSpace-Complete"],"prefix":"10.1007","author":[{"given":"Tom\u00e1\u0161","family":"Masopust","sequence":"first","affiliation":[]},{"given":"Markus","family":"Kr\u00f6tzsch","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,12,22]]},"reference":[{"key":"29_CR1","volume-title":"The Design and Analysis of Computer Algorithms","author":"AV Aho","year":"1974","unstructured":"Aho, A.V., Hopcroft, J.E., Ullman, J.D.: The Design and Analysis of Computer Algorithms. Addison-Wesley, Boston (1974)"},{"issue":"3","key":"29_CR2","doi-asserted-by":"crossref","first-page":"486","DOI":"10.1016\/j.jpaa.2007.06.007","volume":"212","author":"J Almeida","year":"2008","unstructured":"Almeida, J., Costa, J.C., Zeitoun, M.: Pointlike sets with respect to R and J. J. Pure Appl. Algebra 212(3), 486\u2013499 (2008)","journal-title":"J. Pure Appl. Algebra"},{"issue":"1","key":"29_CR3","doi-asserted-by":"crossref","first-page":"8:1","DOI":"10.1145\/2559905","volume":"61","author":"P Barcel\u00f3","year":"2014","unstructured":"Barcel\u00f3, P., Libkin, L., Reutter, J.L.: Querying regular graph patterns. J. ACM 61(1), 8:1\u20138:54 (2014)","journal-title":"J. ACM"},{"key":"29_CR4","doi-asserted-by":"crossref","unstructured":"Bojanczyk, M., Segoufin, L., Straubing, H.: Piecewise testable tree languages. Logical Methods Comput. Sci. 8(3) (2012)","DOI":"10.2168\/LMCS-8(3:26)2012"},{"issue":"2","key":"29_CR5","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1016\/j.ic.2005.11.007","volume":"205","author":"A Bouajjani","year":"2007","unstructured":"Bouajjani, A., Muscholl, A., Touili, T.: Permutation rewriting and algorithmic verification. Inf. Comput. 205(2), 199\u2013224 (2007)","journal-title":"Inf. Comput."},{"issue":"1","key":"29_CR6","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1016\/0022-0000(80)90003-3","volume":"20","author":"JA Brzozowski","year":"1980","unstructured":"Brzozowski, J.A., Fich, F.E.: Languages of $${R}$$ R -trivial monoids. J. Comput. Syst. Sci. 20(1), 32\u201349 (1980)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"29_CR7","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1145\/959060.959076","volume":"32","author":"D Calvanese","year":"2003","unstructured":"Calvanese, D., De Giacomo, G., Lenzerini, M., Vardi, M.Y.: Reasoning on regular path queries. ACM SIGMOD Rec. 32(4), 83\u201392 (2003)","journal-title":"ACM SIGMOD Rec."},{"key":"29_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1007\/978-3-642-39212-2_16","volume-title":"Automata, Languages, and Programming","author":"W Czerwi\u0144ski","year":"2013","unstructured":"Czerwi\u0144ski, W., Martens, W., Masopust, T.: Efficient separability of regular languages by subsequences and suffixes. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013. LNCS, vol. 7966, pp. 150\u2013161. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-39212-2_16"},{"issue":"3","key":"29_CR9","doi-asserted-by":"crossref","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. Science 19(3), 513\u2013548 (2008)","journal-title":"Int. J. Found. Comput. Science"},{"key":"29_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"252","DOI":"10.1007\/978-3-642-20877-5_26","volume-title":"Theory and Applications of Models of Computation","author":"J Fu","year":"2011","unstructured":"Fu, J., Heinz, J., Tanner, H.G.: An algebraic characterization of strictly piecewise languages. In: Ogihara, M., Tarui, J. (eds.) TAMC 2011. LNCS, vol. 6648, pp. 252\u2013263. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-20877-5_26"},{"key":"29_CR11","first-page":"125","volume":"7","author":"P Garc\u00eda","year":"2004","unstructured":"Garc\u00eda, P., Ruiz, J.: Learning $$k$$ k -testable and $$k$$ k -piecewise testable languages from positive data. Grammars 7, 125\u2013140 (2004)","journal-title":"Grammars"},{"issue":"9","key":"29_CR12","doi-asserted-by":"crossref","first-page":"920","DOI":"10.1109\/34.57687","volume":"12","author":"P Garc\u00eda","year":"1990","unstructured":"Garc\u00eda, P., Vidal, E.: Inference of k-testable languages in the strict sense and application to syntactic pattern recognition. IEEE Trans. Pattern Anal. Mach. Intell. 12(9), 920\u2013925 (1990)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"29_CR13","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, New York (1979)"},{"key":"29_CR14","doi-asserted-by":"publisher","unstructured":"Hofman, P., Martens, W.: Separability by short subsequences and subwords. In: Arenas, M., Ugarte, M. (eds.) ICDT 2015. LIPIcs, vol. 31, pp. 230\u2013246. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2015). https:\/\/doi.org\/10.4230\/LIPIcs.ICDT.2015.230","DOI":"10.4230\/LIPIcs.ICDT.2015.230"},{"key":"29_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1007\/978-3-662-44522-8_27","volume-title":"Mathematical Foundations of Computer Science 2014","author":"\u0160 Holub","year":"2014","unstructured":"Holub, \u0160., Jir\u00e1skov\u00e1, G., Masopust, T.: On upper and lower bounds on the length of alternating towers. In: Csuhaj-Varj\u00fa, E., Dietzfelbinger, M., \u00c9sik, Z. (eds.) MFCS 2014. LNCS, vol. 8634, pp. 315\u2013326. Springer, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-662-44522-8_27"},{"issue":"1","key":"29_CR16","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1016\/S0022-0000(75)80050-X","volume":"11","author":"ND Jones","year":"1975","unstructured":"Jones, N.D.: Space-bounded reducibility among combinatorial problems. J. Comput. Syst. Sci. 11(1), 68\u201385 (1975)","journal-title":"J. Comput. Syst. Sci."},{"key":"29_CR17","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). https:\/\/doi.org\/10.1007\/978-3-642-38771-5_26"},{"issue":"3","key":"29_CR18","doi-asserted-by":"crossref","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. Theor. Comput. Sci. 405(3), 223\u2013236 (2008)","journal-title":"Theor. Comput. Sci."},{"key":"29_CR19","doi-asserted-by":"publisher","unstructured":"Kr\u00f6tzsch, M., Masopust, T., Thomazo, M.: Complexity of universality and related problems for partially ordered NFAs. Inf. Comput. Part 1 255, 177\u2013192 (2017). https:\/\/doi.org\/10.1016\/j.ic.2017.06.004","DOI":"10.1016\/j.ic.2017.06.004"},{"key":"29_CR20","doi-asserted-by":"publisher","unstructured":"Martens, W., Neven, F., Niewerth, M., Schwentick, T.: BonXai: combining the simplicity of DTD with the expressiveness of XML schema. In: Milo, T., Calvanese, D. (eds.) PODS 2015, pp. 145\u2013156. ACM (2015). https:\/\/doi.org\/10.1145\/2745754.2745774","DOI":"10.1145\/2745754.2745774"},{"key":"29_CR21","doi-asserted-by":"publisher","unstructured":"Masopust, T.: Piecewise testable languages and nondeterministic automata. In: Faliszewski, P., Muscholl, A., Niedermeier, R. (eds.) MFCS 2016. LIPIcs, vol. 58, pp. 67:1\u201367:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2016). https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2016.67","DOI":"10.4230\/LIPIcs.MFCS.2016.67"},{"key":"29_CR22","unstructured":"Masopust, T., Kr\u00f6tzsch, M.: Universality of confluent, self-loop deterministic partially ordered NFAs is hard (2017). http:\/\/arxiv.org\/abs\/1704.07860"},{"key":"29_CR23","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1016\/j.tcs.2017.01.017","volume":"682","author":"T Masopust","year":"2017","unstructured":"Masopust, T., Thomazo, M.: On Boolean combinations forming piecewise testable languages. Theor. Comput. Sci. 682, 165\u2013179 (2017)","journal-title":"Theor. Comput. Sci."},{"key":"29_CR24","doi-asserted-by":"publisher","unstructured":"Meyer, A.R., Stockmeyer, L.J.: The equivalence problem for regular expressions with squaring requires exponential space. In: Symposium on Switching and Automata Theory, pp. 125\u2013129. IEEE Computer Society (1972). https:\/\/doi.org\/10.1109\/SWAT.1972.29","DOI":"10.1109\/SWAT.1972.29"},{"key":"29_CR25","volume-title":"Infinite Words: Automata, Semigroups, Logic and Games, Pure and Applied Mathematics","author":"D Perrin","year":"2004","unstructured":"Perrin, D., Pin, J.E.: Infinite Words: Automata, Semigroups, Logic and Games, Pure and Applied Mathematics, vol. 141. Academic Press, Cambridge (2004)"},{"key":"29_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"729","DOI":"10.1007\/978-3-642-40313-2_64","volume-title":"Mathematical Foundations of Computer Science 2013","author":"T Place","year":"2013","unstructured":"Place, T., van Rooijen, L., Zeitoun, M.: Separating regular languages by piecewise testable and unambiguous languages. In: Chatterjee, K., Sgall, J. (eds.) MFCS 2013. LNCS, vol. 8087, pp. 729\u2013740. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-40313-2_64"},{"issue":"1\u20134","key":"29_CR27","doi-asserted-by":"crossref","first-page":"223","DOI":"10.3233\/FI-2012-680","volume":"116","author":"N Rampersad","year":"2012","unstructured":"Rampersad, N., Shallit, J., Xu, Z.: The computational complexity of universality problems for prefixes, suffixes, factors, and subwords of regular languages. Fundamenta Informatica 116(1\u20134), 223\u2013236 (2012)","journal-title":"Fundamenta Informatica"},{"key":"29_CR28","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1007\/978-3-642-14322-9_19","volume-title":"The Mathematics of Language","author":"J Rogers","year":"2010","unstructured":"Rogers, J., Heinz, J., Bailey, G., Edlefsen, M., Visscher, M., Wellcome, D., Wibel, S.: On languages piecewise testable in the strict sense. In: Ebert, C., J\u00e4ger, G., Michaelis, J. (eds.) MOL 2007\/2009. LNCS (LNAI), vol. 6149, pp. 255\u2013265. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-14322-9_19"},{"key":"29_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1007\/978-3-642-39998-5_6","volume-title":"Formal Grammar","author":"J Rogers","year":"2013","unstructured":"Rogers, J., Heinz, J., Fero, M., Hurst, J., Lambert, D., Wibel, S.: Cognitive and sub-regular complexity. In: Morrill, G., Nederhof, M.-J. (eds.) FG 2012-2013. LNCS, vol. 8036, pp. 90\u2013108. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-39998-5_6"},{"key":"29_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1007\/3-540-46011-X_20","volume-title":"Developments in Language Theory","author":"T Schwentick","year":"2002","unstructured":"Schwentick, T., Th\u00e9rien, D., Vollmer, H.: Partially-ordered two-way automata: a new characterization of DA. In: Kuich, W., Rozenberg, G., Salomaa, A. (eds.) DLT 2001. LNCS, vol. 2295, pp. 239\u2013250. Springer, Heidelberg (2002). https:\/\/doi.org\/10.1007\/3-540-46011-X_20"},{"key":"29_CR31","unstructured":"Simon, I.: Hierarchies of events with dot-depth one. Ph.D. thesis, University of Waterloo, Canada (1972)"},{"key":"29_CR32","doi-asserted-by":"crossref","first-page":"645","DOI":"10.1613\/jair.4457","volume":"51","author":"G Stefanoni","year":"2014","unstructured":"Stefanoni, G., Motik, B., Kr\u00f6tzsch, M., Rudolph, S.: The complexity of answering conjunctive and navigational queries over OWL 2 EL knowledge bases. J. Artif. Intell. Res. 51, 645\u2013705 (2014)","journal-title":"J. Artif. Intell. Res."},{"key":"29_CR33","doi-asserted-by":"publisher","unstructured":"Stockmeyer, L.J., Meyer, A.R.: Word problems requiring exponential time: preliminary report. In: Aho, A.V., Borodin, A., Constable, R.L., Floyd, R.W., Harrison, M.A., Karp, R.M., Strong, R. (eds.) ACM Symposium on the Theory of Computing, pp. 1\u20139. ACM (1973). https:\/\/doi.org\/10.1145\/800125.804029","DOI":"10.1145\/800125.804029"}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2018: Theory and Practice of Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-73117-9_29","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,24]],"date-time":"2020-10-24T17:47:16Z","timestamp":1603561636000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-73117-9_29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,12,22]]},"ISBN":["9783319731162","9783319731179"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-73117-9_29","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017,12,22]]}}}