{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T08:06:51Z","timestamp":1758269211884},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642392115"},{"type":"electronic","value":"9783642392122"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-39212-2_16","type":"book-chapter","created":{"date-parts":[[2013,7,2]],"date-time":"2013-07-02T13:09:19Z","timestamp":1372770559000},"page":"150-161","source":"Crossref","is-referenced-by-count":19,"title":["Efficient Separability of Regular Languages by Subsequences and Suffixes"],"prefix":"10.1007","author":[{"given":"Wojciech","family":"Czerwi\u0144ski","sequence":"first","affiliation":[]},{"given":"Wim","family":"Martens","sequence":"additional","affiliation":[]},{"given":"Tom\u00e1\u0161","family":"Masopust","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"16_CR1","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/0022-4049(91)90019-X","volume":"69","author":"J. Almeida","year":"1990","unstructured":"Almeida, J.: Implicit operations on finite J-trivial semigroups and a conjecture of I. Simon. Journal of Pure and Applied Algebra\u00a069, 205\u2013218 (1990)","journal-title":"Journal of Pure and Applied Algebra"},{"key":"16_CR2","first-page":"531","volume":"54","author":"J. Almeida","year":"1999","unstructured":"Almeida, J.: Some algorithmic problems for pseudovarieties. Publicationes Mathematicae Debrecen\u00a054, 531\u2013552 (1999)","journal-title":"Publicationes Mathematicae Debrecen"},{"issue":"3","key":"16_CR3","doi-asserted-by":"publisher","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. Journal of Pure and Applied Algebra\u00a0212(3), 486\u2013499 (2008)","journal-title":"Journal of Pure and Applied Algebra"},{"issue":"5","key":"16_CR4","doi-asserted-by":"crossref","first-page":"457","DOI":"10.1051\/ita\/1997310504571","volume":"31","author":"J. Almeida","year":"1997","unstructured":"Almeida, J., Zeitoun, M.: The pseudovariety J is hyperdecidable. RAIRO Informatique Th\u00e9orique et Applications\u00a031(5), 457\u2013482 (1997)","journal-title":"RAIRO Informatique Th\u00e9orique et Applications"},{"key":"16_CR5","doi-asserted-by":"crossref","unstructured":"Arenas, M., Conca, S., P\u00e9rez, J.: Counting beyond a yottabyte, or how SPARQL 1.1 property paths will prevent the adoption of the standard. In: World Wide Web Conference, pp. 629\u2013638 (2012)","DOI":"10.1145\/2187836.2187922"},{"key":"16_CR6","unstructured":"Bray, T., Paoli, J., Sperberg-McQueen, C.M., Maler, E., Yergeau, F.: Extensible Markup Language XML 1.0, 5th edn. Tech. report, W3C Recommendation (November 2008), \n                    \n                      http:\/\/www.w3.org\/TR\/2008\/REC-xml-20081126\/"},{"issue":"3","key":"16_CR7","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1016\/0304-3975(82)90124-4","volume":"27","author":"A. Ehrenfeucht","year":"1983","unstructured":"Ehrenfeucht, A., Haussler, D., Rozenberg, G.: On regularity of context-free languages. Theoretical Computer Science\u00a027(3), 311\u2013332 (1983)","journal-title":"Theoretical Computer Science"},{"key":"16_CR8","unstructured":"Gao, S., Sperberg-McQueen, C.M., Thompson, H.S., Mendelsohn, N., Beech, D., Maloney, M.: W3C XML Schema Definition Language (XSD) 1.1 part 1. Tech. report, W3C (2009), \n                    \n                      http:\/\/www.w3.org\/TR\/2009\/CR-xmlschema11-1-20090430\/"},{"issue":"3","key":"16_CR9","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1016\/j.jcss.2010.04.008","volume":"77","author":"W. Gelade","year":"2011","unstructured":"Gelade, W., Neven, F.: Succinctness of pattern-based schema languages for XML. Journal of Computer and System Sciences\u00a077(3), 505\u2013519 (2011)","journal-title":"Journal of Computer and System Sciences"},{"key":"16_CR10","unstructured":"Harris, S., Seaborne, A.: SPARQL 1.1 query language. Tech. report, W3C (2010)"},{"issue":"2","key":"16_CR11","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1142\/S0218196710005662","volume":"20","author":"K. Henckell","year":"2010","unstructured":"Henckell, K., Rhodes, J., Steinberg, B.: Aperiodic pointlikes and beyond. International Journal of Algebra and Computation\u00a020(2), 287\u2013305 (2010)","journal-title":"International Journal of Algebra and Computation"},{"issue":"1","key":"16_CR12","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1112\/plms\/s3-2.1.326","volume":"s3-2","author":"G. Higman","year":"1952","unstructured":"Higman, G.: Ordering by divisibility in abstract algebras. Proceedings of the London Mathematical Society\u00a0s3-2(1), 326\u2013336 (1952)","journal-title":"Proceedings of the London Mathematical Society"},{"key":"16_CR13","doi-asserted-by":"crossref","unstructured":"Kasneci, G., Schwentick, T.: The complexity of reasoning about pattern-based XML schemas. In: Principles of Database Systems, pp. 155\u2013164 (2007)","DOI":"10.1145\/1265530.1265552"},{"key":"16_CR14","doi-asserted-by":"crossref","unstructured":"Losemann, K., Martens, W.: The complexity of evaluating path expressions in SPARQL. In: Principles of Database Systems, pp. 101\u2013112 (2012)","DOI":"10.1145\/2213556.2213573"},{"issue":"2","key":"16_CR15","doi-asserted-by":"publisher","first-page":"322","DOI":"10.1145\/322063.322075","volume":"25","author":"D. Maier","year":"1978","unstructured":"Maier, D.: The complexity of some problems on subsequences and supersequences. Journal of the ACM\u00a025(2), 322\u2013336 (1978)","journal-title":"Journal of the ACM"},{"issue":"12","key":"16_CR16","doi-asserted-by":"crossref","first-page":"1994","DOI":"10.14778\/2367502.2367556","volume":"5","author":"W. Martens","year":"2012","unstructured":"Martens, W., Neven, F., Niewerth, M., Schwentick, T.: Developing and analyzing XSDs through BonXai. Proc. of the VLDB Endowment\u00a05(12), 1994\u20131997 (2012)","journal-title":"Proc. of the VLDB Endowment"},{"key":"16_CR17","unstructured":"Martens, W., Neven, F., Niewerth, M., Schwentick, T.: BonXai: Combining the simplicity of DTD with the expressiveness of XML Schema (manuscript 2013)"},{"issue":"3","key":"16_CR18","doi-asserted-by":"publisher","first-page":"770","DOI":"10.1145\/1166074.1166076","volume":"31","author":"W. Martens","year":"2006","unstructured":"Martens, W., Neven, F., Schwentick, T., Bex, G.J.: Expressiveness and complexity of XML Schema. ACM Trans. on Database Systems\u00a031(3), 770\u2013813 (2006)","journal-title":"ACM Trans. on Database Systems"},{"issue":"4","key":"16_CR19","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1016\/j.websem.2010.01.002","volume":"8","author":"J. P\u00e9rez","year":"2010","unstructured":"P\u00e9rez, J., Arenas, M., Gutierrez, C.: nSPARQL: A navigational language for RDF. Journal of Web Semantics\u00a08(4), 255\u2013270 (2010)","journal-title":"Journal of Web Semantics"},{"key":"16_CR20","unstructured":"Simon, I.: Hierarchies of Events with Dot-Depth One. PhD thesis, Dep. of Applied Analysis and Computer Science, University of Waterloo, Canada (1972)"},{"key":"16_CR21","series-title":"LNCS","first-page":"214","volume-title":"GI Conference on Automata Theory and Formal Languages","author":"I. Simon","year":"1975","unstructured":"Simon, I.: Piecewise testable events. In: Brakhage, H. (ed.) GI Conference on Automata Theory and Formal Languages. LNCS, vol.\u00a033, pp. 214\u2013222. Springer, Heidelberg (1975)"},{"key":"16_CR22","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1007\/s002330010051","volume":"63","author":"B. Steinberg","year":"2001","unstructured":"Steinberg, B.: A delay theorem for pointlikes. Semigroup Forum\u00a063, 281\u2013304 (2001)","journal-title":"Semigroup Forum"},{"issue":"1985","key":"16_CR23","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/0304-3975(85)90003-9","volume":"35","author":"J. Stern","year":"1985","unstructured":"Stern, J.: Characterizations of some classes of regular events. Theoretical Computer Science\u00a035(1985), 17\u201342 (1985)","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"16_CR24","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/S0019-9958(85)80058-9","volume":"66","author":"J. Stern","year":"1985","unstructured":"Stern, J.: Complexity of some problems from the theory of automata. Information and Control\u00a066(3), 163\u2013176 (1985)","journal-title":"Information and Control"},{"key":"16_CR25","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":"A.N. Trahtman","year":"2001","unstructured":"Trahtman, A.N.: Piecewise and local threshold testability of DFA. In: Freivalds, R. (ed.) FCT 2001. LNCS, vol.\u00a02138, pp. 347\u2013358. Springer, Heidelberg (2001)"},{"key":"16_CR26","unstructured":"van Rooijen, L., Zeitoun, M.: The separation problem for regular languages by piecewise testable languages (March 8, 2013), \n                    \n                      http:\/\/arxiv.org\/abs\/1303.2143"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-39212-2_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,15]],"date-time":"2019-05-15T10:01:09Z","timestamp":1557914469000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-39212-2_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642392115","9783642392122"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-39212-2_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}