{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T11:30:02Z","timestamp":1725795002862},"publisher-location":"Cham","reference-count":33,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319066851"},{"type":"electronic","value":"9783319066868"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-06686-8_14","type":"book-chapter","created":{"date-parts":[[2014,6,2]],"date-time":"2014-06-02T01:30:40Z","timestamp":1401672640000},"page":"176-189","source":"Crossref","is-referenced-by-count":2,"title":["Block Products and Nesting Negations in FO2"],"prefix":"10.1007","author":[{"given":"Lukas","family":"Fleischer","sequence":"first","affiliation":[]},{"given":"Manfred","family":"Kufleitner","sequence":"additional","affiliation":[]},{"given":"Alexander","family":"Lauser","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"14_CR1","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1002\/malq.19600060105","volume":"6","author":"J.R. B\u00fcchi","year":"1960","unstructured":"B\u00fcchi, J.R.: Weak second-order arithmetic and finite automata. Z. Math. Logik Grundlagen Math.\u00a06, 66\u201392 (1960)","journal-title":"Z. Math. Logik Grundlagen Math."},{"issue":"1","key":"14_CR2","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.A.: Dot-depth of star-free events. J. Comput. Syst. Sci.\u00a05(1), 1\u201316 (1971)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"14_CR3","doi-asserted-by":"publisher","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. Sci.\u00a019(3), 513\u2013548 (2008)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"14_CR4","doi-asserted-by":"crossref","unstructured":"Ebbinghaus, H.-D., Flum, J.: Finite Model Theory. In: Perspectives in Mathematical Logic. Springer (1995)","DOI":"10.1007\/978-3-662-03182-7"},{"key":"14_CR5","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1090\/S0002-9947-1961-0139530-9","volume":"98","author":"C.C. Elgot","year":"1961","unstructured":"Elgot, C.C.: Decision problems of finite automata design and related arithmetics. Trans. Amer. Math. Soc.\u00a098, 21\u201351 (1961)","journal-title":"Trans. Amer. Math. Soc."},{"issue":"2","key":"14_CR6","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1007\/s00224-007-9002-0","volume":"42","author":"C. Gla\u00dfer","year":"2008","unstructured":"Gla\u00dfer, C., Schmitz, H.: Languages of dot-depth 3\/2. Theory of Computing Systems\u00a042(2), 256\u2013286 (2008)","journal-title":"Theory of Computing Systems"},{"key":"14_CR7","unstructured":"Kamp, J.A.W.: Tense Logic and the Theory of Linear Order. PhD thesis, University of California (1968)"},{"issue":"4","key":"14_CR8","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1051\/ita\/1983170403211","volume":"17","author":"R. Knast","year":"1983","unstructured":"Knast, R.: A semigroup characterization of dot-depth one languages. RAIRO, Inf. Th\u00e9or.\u00a017(4), 321\u2013330 (1983)","journal-title":"RAIRO, Inf. Th\u00e9or."},{"key":"14_CR9","unstructured":"Krebs, A., Straubing, H.: An effective characterization of the alternation hierarchy in two-variable logic. In: FSTTCS 2012, Proceedings. LIPIcs, vol.\u00a018, pp. 86\u201398. Dagstuhl Publishing (2012)"},{"key":"14_CR10","doi-asserted-by":"crossref","unstructured":"Kufleitner, M., Lauser, A.: Languages of dot-depth one over infinite words. In: Proceedings of LICS 2011, pp. 23\u201332. IEEE Computer Society (2011)","DOI":"10.1109\/LICS.2011.24"},{"issue":"6","key":"14_CR11","doi-asserted-by":"publisher","first-page":"1323","DOI":"10.1142\/S0129054112400552","volume":"23","author":"M. Kufleitner","year":"2012","unstructured":"Kufleitner, M., Lauser, A.: Around dot-depth one. Int. J. Found. Comput. Sci.\u00a023(6), 1323\u20131339 (2012)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"14_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"603","DOI":"10.1007\/978-3-642-32589-2_53","volume-title":"Mathematical Foundations of Computer Science 2012","author":"M. Kufleitner","year":"2012","unstructured":"Kufleitner, M., Lauser, A.: The join levels of the trotter-weil hierarchy are decidable. In: Rovan, B., Sassone, V., Widmayer, P. (eds.) MFCS 2012. LNCS, vol.\u00a07464, pp. 603\u2013614. Springer, Heidelberg (2012)"},{"key":"14_CR13","unstructured":"Kufleitner, M., Lauser, A.: The join of the varieties of R-trivial and L-trivial monoids via combinatorics on words. Discrete Math. & Theor. Comput. Sci. 14(1), 141\u2013146 (2012)"},{"key":"14_CR14","unstructured":"Kufleitner, M., Lauser, A.: Quantifier alternation in two-variable first-order logic with successor is decidable. In: Proceedings of STACS 2013. LIPIcs, vol.\u00a020, pp. 305\u2013316. Dagstuhl Publishing (2013)"},{"key":"14_CR15","unstructured":"Kufleitner, M., Weil, P.: The FO2 alternation hierarchy is decidable. In: Proceedings of CSL 2012. LIPIcs, vol.\u00a016, pp. 426\u2013439. Dagstuhl Publishing (2012)"},{"key":"14_CR16","doi-asserted-by":"crossref","first-page":"1","DOI":"10.2168\/LMCS-8(3:11)2012","volume":"8","author":"M. Kufleitner","year":"2012","unstructured":"Kufleitner, M., Weil, P.: On logical hierarchies within FO2-definable languages. Log. Methods Comput. Sci.\u00a08, 1\u201330 (2012)","journal-title":"Log. Methods Comput. Sci."},{"key":"14_CR17","unstructured":"McNaughton, R., Papert, S.: Counter-Free Automata. The MIT Press (1971)"},{"key":"14_CR18","first-page":"80","volume":"39","author":"J.-\u00c9. Pin","year":"1995","unstructured":"Pin, J.-\u00c9.: A variety theorem without complementation. Russian Mathematics (Iz. VUZ)\u00a039, 80\u201390 (1995)","journal-title":"Russian Mathematics (Iz. VUZ)"},{"issue":"4","key":"14_CR19","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.\u00a030(4), 383\u2013422 (1997)","journal-title":"Theory Comput. Syst."},{"issue":"12","key":"14_CR20","doi-asserted-by":"publisher","first-page":"5677","DOI":"10.1081\/AGB-120016005","volume":"30","author":"J.-\u00c9. Pin","year":"2002","unstructured":"Pin, J.-\u00c9., Weil, P.: The wreath product principle for ordered semigroups. Commun. Algebra\u00a030(12), 5677\u20135713 (2002)","journal-title":"Commun. Algebra"},{"key":"14_CR21","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. Inf. Control\u00a08, 190\u2013194 (1965)","journal-title":"Inf. Control"},{"key":"14_CR22","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.\u00a02295, pp. 239\u2013250. Springer, Heidelberg (2002)"},{"key":"14_CR23","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)"},{"key":"14_CR24","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1016\/0304-3975(81)90036-0","volume":"13","author":"H. Straubing","year":"1981","unstructured":"Straubing, H.: A generalization of the Sch\u00fctzenberger product of finite monoids. Theor. Comput. Sci.\u00a013, 137\u2013150 (1981)","journal-title":"Theor. Comput. Sci."},{"key":"14_CR25","doi-asserted-by":"crossref","unstructured":"Straubing, H.: Finite Automata, Formal Logic, and Circuit Complexity. Birkh\u00e4user (1994)","DOI":"10.1007\/978-1-4612-0289-9"},{"key":"14_CR26","unstructured":"Straubing, H.: Algebraic characterization of the alternation hierarchy in FO2[ < ] on finite words. In: Proceedings CSL 2011. LIPIcs, vol.\u00a012, pp. 525\u2013537. Dagstuhl Publishing (2011)"},{"key":"14_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/3-540-45995-2_13","volume-title":"LATIN 2002: Theoretical Informatics","author":"H. Straubing","year":"2002","unstructured":"Straubing, H., Th\u00e9rien, D.: Weakly iterated block products of finite monoids. In: Rajsbaum, S. (ed.) LATIN 2002. LNCS, vol.\u00a02286, pp. 91\u2013104. Springer, Heidelberg (2002)"},{"key":"14_CR28","doi-asserted-by":"crossref","unstructured":"Tesson, P., Th\u00e9rien, D.: Diamonds are forever: The variety DA. In: Proceedings of Semigroups, Algorithms, Automata and Languages, pp. 475\u2013500. World Scientific (2002)","DOI":"10.1142\/9789812776884_0021"},{"issue":"2","key":"14_CR29","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/0304-3975(81)90057-8","volume":"14","author":"D. Th\u00e9rien","year":"1981","unstructured":"Th\u00e9rien, D.: Classification of finite monoids: The language approach. Theor. Comput. Sci.\u00a014(2), 195\u2013208 (1981)","journal-title":"Theor. Comput. Sci."},{"key":"14_CR30","doi-asserted-by":"crossref","unstructured":"Th\u00e9rien, D.: Th.\u00a0Wilke. Over words, two variables are as powerful as one quantifier alternation. In: Proceedings of STOC 1998, pp. 234\u2013240. ACM Press (1998)","DOI":"10.1145\/276698.276749"},{"key":"14_CR31","doi-asserted-by":"publisher","first-page":"360","DOI":"10.1016\/0022-0000(82)90016-2","volume":"25","author":"W. Thomas","year":"1982","unstructured":"Thomas, W.: Classifying regular events in symbolic logic. J. Comput. Syst. Sci.\u00a025, 360\u2013376 (1982)","journal-title":"J. Comput. Syst. Sci."},{"key":"14_CR32","first-page":"326","volume":"140","author":"B.A. Trakhtenbrot","year":"1961","unstructured":"Trakhtenbrot, B.A.: Finite automata and logic of monadic predicates (in Russian). Dokl. Akad. Nauk. SSSR\u00a0140, 326\u2013329 (1961)","journal-title":"Dokl. Akad. Nauk. SSSR"},{"key":"14_CR33","doi-asserted-by":"crossref","first-page":"1","DOI":"10.2168\/LMCS-5(3:4)2009","volume":"5","author":"P. Weis","year":"2009","unstructured":"Weis, P., Immerman, N.: Structure theorem and strict alternation hierarchy for FO2 on words. Log. Methods Comput. Sci.\u00a05, 1\u201323 (2009)","journal-title":"Log. Methods Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","Computer Science - Theory and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-06686-8_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,26]],"date-time":"2019-05-26T19:43:27Z","timestamp":1558899807000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-06686-8_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319066851","9783319066868"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-06686-8_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}