{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,15]],"date-time":"2026-04-15T06:07:47Z","timestamp":1776233267732,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783662439500","type":"print"},{"value":"9783662439517","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-43951-7_29","type":"book-chapter","created":{"date-parts":[[2014,6,11]],"date-time":"2014-06-11T08:37:49Z","timestamp":1402475869000},"page":"342-353","source":"Crossref","is-referenced-by-count":21,"title":["Going Higher in the First-Order Quantifier Alternation Hierarchy on Words"],"prefix":"10.1007","author":[{"given":"Thomas","family":"Place","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marc","family":"Zeitoun","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"#cr-split#-29_CR1.1","unstructured":"Almeida, J.: Some algorithmic problems for pseudovarieties. Publ. Math. Debrecen??54, 531???552 (1999);"},{"key":"#cr-split#-29_CR1.2","unstructured":"Proc. of Automata and Formal Languages, VIII"},{"key":"29_CR2","doi-asserted-by":"crossref","unstructured":"Almeida, J., Kl\u00edma, O.: New decidable upper bound of the 2nd level in the Straubing-Th\u00e9rien concatenation hierarchy of star-free languages. DMTCS (2010)","DOI":"10.46298\/dmtcs.490"},{"key":"29_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"198","DOI":"10.1007\/BFb0039607","volume-title":"STACS 87","author":"M. Arfi","year":"1987","unstructured":"Arfi, M.: Polynomial operations on rational languages. In: Brandenburg, F.J., Wirsing, M., Vidal-Naquet, G. (eds.) STACS 1987. LNCS, vol.\u00a0247, pp. 198\u2013206. Springer, Heidelberg (1987)"},{"key":"29_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-02737-6_1","volume-title":"Developments in Language Theory","author":"M. Boja\u0144czyk","year":"2009","unstructured":"Boja\u0144czyk, M.: Factorization forests. In: Diekert, V., Nowotka, D. (eds.) DLT 2009. LNCS, vol.\u00a05583, pp. 1\u201317. Springer, Heidelberg (2009)"},{"key":"29_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1007\/978-3-642-31585-5_13","volume-title":"Automata, Languages, and Programming","author":"M. Boja\u0144czyk","year":"2012","unstructured":"Boja\u0144czyk, M., Place, T.: Regular languages of infinite trees that are boolean combinations of open sets. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012, Part II. LNCS, vol.\u00a07392, pp. 104\u2013115. Springer, Heidelberg (2012)"},{"issue":"1","key":"29_CR6","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1016\/0022-0000(78)90049-1","volume":"16","author":"J. Brzozowski","year":"1978","unstructured":"Brzozowski, J., Knast, R.: The dot-depth hierarchy of star-free languages is infinite. J. Comp. Syst. Sci.\u00a016(1), 37\u201355 (1978)","journal-title":"J. Comp. Syst. Sci."},{"key":"29_CR7","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0022-0000(71)80003-X","volume":"5","author":"R.S. Cohen","year":"1971","unstructured":"Cohen, R.S., Brzozowski, J.: Dot-depth of star-free events. J. Comp. Syst. Sci.\u00a05, 1\u201316 (1971)","journal-title":"J. Comp. Syst. Sci."},{"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, Part II. LNCS, vol.\u00a07966, pp. 150\u2013161. Springer, Heidelberg (2013)"},{"key":"29_CR9","unstructured":"McNaughton, R., Papert, S.: Counter-Free Automata. MIT Press (1971)"},{"key":"29_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1007\/BFb0055073","volume-title":"Automata, Languages and Programming","author":"J.-\u00c9. Pin","year":"1998","unstructured":"Pin, J.-\u00c9.: Bridges for concatenation hierarchies. In: Larsen, K.G., Skyum, S., Winskel, G. (eds.) ICALP 1998. LNCS, vol.\u00a01443, pp. 431\u2013442. Springer, Heidelberg (1998)"},{"key":"29_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1007\/978-3-642-21493-6_3","volume-title":"Algebraic Informatics","author":"J.-\u00c9. Pin","year":"2011","unstructured":"Pin, J.-\u00c9.: Theme and variations on the concatenation product. In: Winkler, F. (ed.) CAI 2011. LNCS, vol.\u00a06742, pp. 44\u201364. Springer, Heidelberg (2011)"},{"key":"29_CR12","unstructured":"Pin, J.-E., Straubing, H.: Monoids of upper triangular boolean matrices. In: Semigroups. Structure and Universal Algebraic Problems. Colloquia Mathematica Societatis Janos Bolyal, vol.\u00a039, pp. 259\u2013272. North-Holland (1985)"},{"issue":"4","key":"29_CR13","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1007\/BF02679467","volume":"30","author":"J.-E. Pin","year":"1997","unstructured":"Pin, J.-E., Weil, P.: Polynomial closure and unambiguous product. Theory of Computing Systems\u00a030(4), 383\u2013422 (1997)","journal-title":"Theory of Computing Systems"},{"key":"29_CR14","doi-asserted-by":"publisher","first-page":"5677","DOI":"10.1081\/AGB-120016005","volume":"30","author":"J.-E. Pin","year":"2002","unstructured":"Pin, J.-E., Weil, P.: The wreath product principle for ordered semigroups. Communications in Algebra\u00a030, 5677\u20135713 (2002)","journal-title":"Communications in Algebra"},{"key":"29_CR15","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.\u00a08087, pp. 729\u2013740. Springer, Heidelberg (2013)"},{"key":"29_CR16","doi-asserted-by":"crossref","unstructured":"Place, T., van Rooijen, L., Zeitoun, M.: Separating regular languages by locally testable and locally threshold testable languages. In: FSTTCS 2013. LIPIcs (2013)","DOI":"10.2168\/LMCS-10(3:24)2014"},{"key":"29_CR17","unstructured":"Place, T., Zeitoun, M.: Going higher in the first-order quantifier alternation hierarchy on words. Arxiv (2014), http:\/\/arxiv.org\/abs\/1404.6832"},{"key":"29_CR18","doi-asserted-by":"crossref","unstructured":"Place, T., Zeitoun, M.: Separating regular languages with first-order logic. In: CSL-LICS 2014 (2014)","DOI":"10.1145\/2603088.2603098"},{"key":"29_CR19","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1016\/S0019-9958(65)90108-7","volume":"8","author":"M.P. Sch\u00fctzenberger","year":"1965","unstructured":"Sch\u00fctzenberger, M.P.: On finite monoids having only trivial subgroups. Information and Control\u00a08, 190\u2013194 (1965)","journal-title":"Information and Control"},{"key":"29_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"214","DOI":"10.1007\/3-540-07407-4_23","volume-title":"Automata Theory and Formal Languages","author":"I. Simon","year":"1975","unstructured":"Simon, I.: Piecewise testable events. In: Brakhage, H. (ed.) GI-Fachtagung 1975. LNCS, vol.\u00a033, pp. 214\u2013222. Springer, Heidelberg (1975)"},{"issue":"1","key":"29_CR21","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1016\/0304-3975(90)90047-L","volume":"72","author":"I. Simon","year":"1990","unstructured":"Simon, I.: Factorization forests of finite height. TCS\u00a072(1), 65\u201394 (1990)","journal-title":"TCS"},{"key":"29_CR22","doi-asserted-by":"crossref","unstructured":"Straubing, H.: A generalization of the Sch\u00fctzenberger product of finite monoids. TCS (1981)","DOI":"10.1016\/0304-3975(81)90036-0"},{"key":"29_CR23","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/0022-4049(85)90062-3","volume":"36","author":"H. Straubing","year":"1985","unstructured":"Straubing, H.: Finite semigroup varieties of the form V * D. J. Pure App. Algebra\u00a036, 53\u201394 (1985)","journal-title":"J. Pure App. Algebra"},{"key":"29_CR24","doi-asserted-by":"crossref","unstructured":"Straubing, H.: Semigroups and languages of dot-depth two. TCS (1988)","DOI":"10.1016\/0304-3975(88)90034-5"},{"key":"29_CR25","doi-asserted-by":"crossref","unstructured":"Tesson, P., Therien, D.: Diamonds are forever: The variety DA. In: Semigroups, Algorithms, Automata and Languages, pp. 475\u2013500. World Scientific (2002)","DOI":"10.1142\/9789812776884_0021"},{"key":"29_CR26","doi-asserted-by":"crossref","unstructured":"Th\u00e9rien, D.: Classification of finite monoids: the language approach. TCS (1981)","DOI":"10.1016\/0304-3975(81)90057-8"},{"key":"29_CR27","doi-asserted-by":"crossref","unstructured":"Th\u00e9rien, D., Wilke, T.: Over words, two variables are as powerful as one quantifier alternation. In: STOC 1998, pp. 234\u2013240. ACM (1998)","DOI":"10.1145\/276698.276749"},{"key":"29_CR28","doi-asserted-by":"crossref","unstructured":"Thomas, W.: Classifying regular events in symbolic logic. J. Comp. Syst. Sci. (1982)","DOI":"10.1016\/0022-0000(82)90016-2"},{"key":"29_CR29","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1007\/3-540-18170-9_183","volume-title":"Computation Theory and Logic","author":"W. Thomas","year":"1987","unstructured":"Thomas, W.: A concatenation game and the dot-depth hierarchy. In: B\u00f6rger, E. (ed.) Computation Theory and Logic. LNCS, vol.\u00a0270, pp. 415\u2013426. Springer, Heidelberg (1987)"}],"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-662-43951-7_29","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,4,7]],"date-time":"2022-04-07T17:47:13Z","timestamp":1649353633000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-43951-7_29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662439500","9783662439517"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-43951-7_29","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014]]}}}