{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,1]],"date-time":"2025-06-01T22:10:02Z","timestamp":1748815802022,"version":"3.41.0"},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662496299"},{"type":"electronic","value":"9783662496305"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"tdm","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":[[2016]]},"DOI":"10.1007\/978-3-662-49630-5_14","type":"book-chapter","created":{"date-parts":[[2016,3,21]],"date-time":"2016-03-21T09:04:32Z","timestamp":1458551072000},"page":"234-251","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Quantifier Alternation for Infinite Words"],"prefix":"10.1007","author":[{"given":"Th\u00e9o","family":"Pierron","sequence":"first","affiliation":[]},{"given":"Thomas","family":"Place","sequence":"additional","affiliation":[]},{"given":"Marc","family":"Zeitoun","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"14_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"198","DOI":"10.1007\/BFb0039607","volume-title":"Symposium on Theoretical Aspects of Computer Science STACS 1987","author":"M Arfi","year":"1987","unstructured":"Arfi, M.: Polynomial operations on rational languages. In: Brandenburg, F.J., Vidal-Naquet, G., Wirsing, M. (eds.) STACS\u201987. LNCS, vol. 247, pp. 198\u2013206. Springer, Heidelberg (1987)"},{"key":"14_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1007\/978-3-540-78499-9_13","volume-title":"Foundations of Software Science and Computational Structures","author":"M Boja\u0144czyk","year":"2008","unstructured":"Boja\u0144czyk, M.: The common fragment of ACTL and LTL. In: Amadio, R.M. (ed.) FOSSACS 2008. LNCS, vol. 4962, pp. 172\u2013185. Springer, Heidelberg (2008)"},{"issue":"1","key":"14_CR3","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/0022-0000(78)90049-1","volume":"16","author":"JA Brzozowski","year":"1978","unstructured":"Brzozowski, J.A., Knast, R.: The dot-depth hierarchy of star-free languages is infinite. J. Comput. Syst. Sci. 16(1), 37\u201355 (1978)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1\u20136","key":"14_CR4","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1002\/malq.19600060105","volume":"6","author":"JR B\u00fcchi","year":"1960","unstructured":"B\u00fcchi, J.R.: Weak second-order arithmetic and finite automata. Math. Logic Q. 6(1\u20136), 66\u201392 (1960)","journal-title":"Math. Logic Q."},{"key":"14_CR5","unstructured":"B\u00fcchi, J.R.: On a decision method in restricted second order arithmetic. In: Logic, Methodology and Philosophy of Science (Proc. 1960 Internat. Congr.), pp. 1\u201311. Stanford Univ. Press, Stanford (1962)"},{"key":"14_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","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. 7966, pp. 150\u2013161. Springer, Heidelberg (2013)"},{"issue":"3","key":"14_CR7","doi-asserted-by":"publisher","first-page":"486","DOI":"10.1007\/s00224-010-9266-7","volume":"48","author":"V Diekert","year":"2011","unstructured":"Diekert, V., Kufleitner, M.: Fragments of first-order logic over infinite words. Theory Comput. Syst. 48(3), 486\u2013516 (2011)","journal-title":"Theory Comput. Syst."},{"issue":"1","key":"14_CR8","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1090\/S0002-9947-1961-0139530-9","volume":"98","author":"CC Elgot","year":"1961","unstructured":"Elgot, C.C.: Decision problems of finite automata design and related arithmetics. Trans. Am. Math. Soc. 98(1), 21\u201351 (1961)","journal-title":"Trans. Am. Math. Soc."},{"key":"14_CR9","doi-asserted-by":"crossref","unstructured":"Kufleitner, M., Walter, T.: Level two of the quantifier alternation hierarchy over infinite words. CoRR, abs\/1509.06207 (2015)","DOI":"10.1007\/978-3-319-34171-2_16"},{"key":"14_CR10","volume-title":"Counter-Free Automata","author":"R McNaughton","year":"1971","unstructured":"McNaughton, R., Papert, S.A.: Counter-Free Automata. MIT Press, Cambridge (1971)"},{"key":"14_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1007\/BFb0030294","volume-title":"Mathematical Foundations of Computer Science MFCS\u201984","author":"D Perrin","year":"1984","unstructured":"Perrin, D.: Recent results on automata and infinite words. In: Chytil, M.P., Koubek, V. (eds.) MFCS 1984. LNCS, vol. 176, pp. 134\u2013148. Springer, Heidelberg (1984)"},{"key":"14_CR12","volume-title":"Infinite Words","author":"D Perrin","year":"2004","unstructured":"Perrin, D., Pin, J.\u00c9.: Infinite Words. Elsevier, Amsterdam (2004)"},{"key":"14_CR13","unstructured":"Pierron, T., Place, T., Zeitoun, M.: Quantifier alternation for infinite words. CoRR, abs\/1511.09011 (2015)"},{"key":"14_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1007\/BFb0054312","volume-title":"LATIN\u201998: Theoretical Informatics","author":"J\u00c9 Pin","year":"1998","unstructured":"Pin, J.\u00c9.: Positive varieties and infinite words. In: Lucchesi, C.L., Moura, A.V. (eds.) LATIN 1998. LNCS, vol. 1380, pp. 76\u201387. Springer, Heidelberg (1998)"},{"issue":"4","key":"14_CR15","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1007\/BF02679467","volume":"30","author":"J\u00c9 Pin","year":"1997","unstructured":"Pin, J.\u00c9., Weil, P.: Polynomial closure and unambiguous product. Theory Comput.Syst. 30(4), 383\u2013422 (1997)","journal-title":"Theory Comput.Syst."},{"key":"14_CR16","doi-asserted-by":"crossref","unstructured":"Place, T.: Separating regular languages with two quantifier alternations. In: Proceedings of the 30th Annual ACM\/IEEE Symposium on Logic in Computer Science (LICS 2015), pp. 202\u2013213. IEEE (2015)","DOI":"10.1109\/LICS.2015.28"},{"key":"14_CR17","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)"},{"key":"14_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"342","DOI":"10.1007\/978-3-662-43951-7_29","volume-title":"Automata, Languages, and Programming","author":"T Place","year":"2014","unstructured":"Place, T., Zeitoun, M.: Going higher in the first-order quantifier alternation hierarchy on words. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014, Part II. LNCS, vol. 8573, pp. 342\u2013353. Springer, Heidelberg (2014)"},{"key":"14_CR19","doi-asserted-by":"crossref","unstructured":"Place, T., Zeitoun, M.: Separating regular languages with first-order logic. In: 2014 Proceedings of the Joint Meeting of the 23rd EACSL Annual Conference on Computer Science Logic (CSL 2014), 29th Annual ACM\/IEEE Symposium on Logic in Computer Science (LICS 2014), pp. 75:1\u201375:10. ACM, New York (2011)","DOI":"10.1145\/2603088.2603098"},{"key":"14_CR20","unstructured":"Place, T., Zeitoun, M.: Separating $$\\omega $$ \u03c9 -languages without quantifier alternation (2015) (Unpublished)"},{"key":"14_CR21","unstructured":"Place, T., Zeitoun, M.: Separation and the successor relation. In preparation, long version of [22] (2015)"},{"key":"14_CR22","unstructured":"Place, T., Zeitoun, M.: Separation and the successor relation. In: Mayr, E.W., Ollinger, N. (eds.) 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), vol. 30, pp. 662\u2013675. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl (2015)"},{"issue":"2","key":"14_CR23","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1016\/S0019-9958(65)90108-7","volume":"8","author":"MP Sch\u00fctzenberger","year":"1965","unstructured":"Sch\u00fctzenberger, M.P.: On finite monoids having only trivial subgroups. Inf. Control 8(2), 190\u2013194 (1965)","journal-title":"Inf. Control"},{"key":"14_CR24","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.) Automata Theory and Formal Languages. LNCS, vol. 33, pp. 214\u2013222. Springer, Heidelberg (1975)"},{"key":"14_CR25","doi-asserted-by":"crossref","unstructured":"Stockmeyer, L.J., Meyer, A.R.: Word problems requiring exponential time (preliminary report). In: Proceedings of the Fifth Annual ACM Symposium on Theory of Computing, STOC 1973, pp. 1\u20139. ACM, New York (1973)","DOI":"10.1145\/800125.804029"},{"key":"14_CR26","series-title":"Lecture Notes in Computer Science","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. 270, pp. 415\u2013426. Springer, Heidelberg (1987)"},{"key":"14_CR27","first-page":"326","volume":"149","author":"BA Trakhtenbrot","year":"1961","unstructured":"Trakhtenbrot, B.A.: Finite automata and logic of monadic predicates. Dokl. Akad. Nauk SSSR 149, 326\u2013329 (1961). In Russian","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"14_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"588","DOI":"10.1007\/3-540-54233-7_166","volume-title":"Automata, Languages and Programming ICALP\u201991","author":"T Wilke","year":"1991","unstructured":"Wilke, T.: An Eilenberg theorem for $$\\infty $$ \u221e -languages. In: Leach Albert, J., Monien, B., Rodr\u00edguez Artalejo, M. (eds.) ICALP 1991. LNCS, vol. 510, pp. 588\u2013599. Springer, Heidelberg (1991)"}],"container-title":["Lecture Notes in Computer Science","Foundations of Software Science and Computation Structures"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-49630-5_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,1]],"date-time":"2025-06-01T21:30:02Z","timestamp":1748813402000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-49630-5_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783662496299","9783662496305"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-49630-5_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}