{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:43:30Z","timestamp":1740109410634,"version":"3.37.3"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2017,5,16]],"date-time":"2017-05-16T00:00:00Z","timestamp":1494892800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["DI 435\/5-2","KU 2716\/1-1"],"award-info":[{"award-number":["DI 435\/5-2","KU 2716\/1-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2018,4]]},"DOI":"10.1007\/s00224-017-9763-z","type":"journal-article","created":{"date-parts":[[2017,5,15]],"date-time":"2017-05-15T21:39:18Z","timestamp":1494884358000},"page":"682-738","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["The Word Problem for Omega-Terms over the Trotter-Weil Hierarchy"],"prefix":"10.1007","volume":"62","author":[{"given":"Manfred","family":"Kufleitner","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7801-6569","authenticated-orcid":false,"given":"Jan Philipp","family":"W\u00e4chter","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,5,16]]},"reference":[{"issue":"3","key":"9763_CR1","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1016\/0022-4049(91)90019-X","volume":"69","author":"J Almeida","year":"1991","unstructured":"Almeida, J.: Implicit operations on finite J $\\mathcal {J}$ -trivial semigroups and a conjecture of I. Simon. J. Pure Applied Algebra 69(3), 205\u2013218 (1991)","journal-title":"J. Pure Applied Algebra"},{"key":"9763_CR2","doi-asserted-by":"crossref","unstructured":"Almeida, J.: Finite Semigroups and Universal Algebra. World Scientific (1994)","DOI":"10.1142\/2481"},{"key":"9763_CR3","doi-asserted-by":"crossref","unstructured":"Almeida, J.: Finite semigroups: an introduction to a unified theory of pseudovarieties. In: dos Gomes Moreira da Cunha, G.M., da Silva, P.V.A., Pin, J.\u00c9. (eds.) Semigroups, Algorithms, Automata and Languages, pp. 3\u201364. World Scientific (2002)","DOI":"10.1142\/9789812776884_0001"},{"issue":"1","key":"9763_CR4","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1016\/j.tcs.2006.10.019","volume":"370","author":"J Almeida","year":"2007","unstructured":"Almeida, J., Zeitoun, M.: An automata-theoretic approach to the word problem for \u03c9-terms over R. Theor. Comput. Sci. 370(1), 131\u2013169 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"9763_CR5","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. Sci. 19, 513\u2013548 (2008)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"9763_CR6","unstructured":"Eilenberg, S.: Automata, Languages, and Machines, vol. B. Academic press (1976)"},{"issue":"3","key":"9763_CR7","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1112\/plms\/s3-58.2.323","volume":"58","author":"J Gerhard","year":"1989","unstructured":"Gerhard, J., Petrich, M.: Varieties of bands revisited. Proc. Lond. Math. Soc. 58(3), 323\u2013350 (1989)","journal-title":"Proc. Lond. Math. Soc."},{"issue":"1","key":"9763_CR8","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1007\/s002339900032","volume":"59","author":"T Hall","year":"1999","unstructured":"Hall, T., Weil, P.: On radical congruence systems. Semigroup Forum 59(1), 56\u201373 (1999)","journal-title":"Semigroup Forum"},{"key":"9763_CR9","unstructured":"Hopcroft, J., Karp, R.: A linear algorithm for testing equivalence of finite automata. Cornell University, Tech. rep. (1971)"},{"key":"9763_CR10","first-page":"374","volume-title":"STACS 2014, Proceedings, LIPIcs, vol. 25","author":"M Huschenbett","year":"2014","unstructured":"Huschenbett, M., Kufleitner, M.: Ehrenfeucht-Fra\u00efss\u00e9 games on omega-terms. In: Mayr, E.W., Portier, N. (eds.) STACS 2014, Proceedings, LIPIcs, vol. 25, pp 374\u2013385. Dagstuhl Publishing, Dagstuhl, Germany (2014)"},{"key":"9763_CR11","first-page":"191","volume-title":"Algebraic Theory of Machines, Languages, and Semigroups, chap. 8","author":"K Krohn","year":"1968","unstructured":"Krohn, K., Rhodes, J.L., Tilson, B.: Homomorphisms and semilocal theory. In: Arbib, M.A. (ed.) Algebraic Theory of Machines, Languages, and Semigroups, chap. 8, pp 191\u2013231. Academic Press, New York and London (1968)"},{"key":"9763_CR12","doi-asserted-by":"crossref","unstructured":"Kufleitner, M., Lauser, A., Widmayer, P.: The join levels of the Trotter-Weil Hierarchy are decidable. In: Rovan, B., Sassone, V. (eds.) MFCS 2012, Proceedings, LNCS, vol. 7464, pp. 603\u2013614. Springer (2012)","DOI":"10.1007\/978-3-642-32589-2_53"},{"key":"9763_CR13","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1007\/s00233-010-9258-6","volume":"81","author":"M Kufleitner","year":"2010","unstructured":"Kufleitner, M., Weil, P.: On the lattice of sub-pseudovarieties of DA. Semigroup Forum 81, 243\u2013254 (2010)","journal-title":"Semigroup Forum"},{"key":"9763_CR14","first-page":"426","volume-title":"CSL 2012, Proceedings, LIPIcs, vol. 16","author":"M Kufleitner","year":"2012","unstructured":"Kufleitner, M., Weil, P.: The F O 2 alternation hierarchy is decidable. In: C\u00e9gielski, P., Durand, A. (eds.) CSL 2012, Proceedings, LIPIcs, vol. 16, pp. 426\u2013439. Dagstuhl Publishing, Dagstuhl, Germany (2012)"},{"issue":"3","key":"9763_CR15","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 F O 2-definable languages. Logical Methods Comput. Sci. 8(3), 1\u201330 (2012)","journal-title":"Logical Methods Comput. Sci."},{"key":"9763_CR16","doi-asserted-by":"crossref","unstructured":"Lodaya, K., Pandya, P.K., Shah, S.S.: Marking the chops: an unambiguous temporal logic. In: IFIP TCS 2008, Proceedings, IFIP, pp. 461\u2013476. Springer (2008)","DOI":"10.1007\/978-0-387-09680-3_31"},{"issue":"5","key":"9763_CR17","doi-asserted-by":"crossref","first-page":"581","DOI":"10.1142\/S0218196701000693","volume":"11","author":"JP McCammond","year":"2001","unstructured":"McCammond, J.P.: Normal forms for free aperiodic semigroups. Int. J. Algebra Comput. 11(5), 581\u2013625 (2001)","journal-title":"Int. J. Algebra Comput."},{"issue":"46","key":"9763_CR18","doi-asserted-by":"crossref","first-page":"6556","DOI":"10.1016\/j.tcs.2011.08.003","volume":"412","author":"A Moura","year":"2011","unstructured":"Moura, A.: The word problem for \u03c9-terms over DA. Theor. Comput. Sci. 412(46), 6556\u20136569 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"9763_CR19","volume-title":"Infinite words, Pure and Applied Mathematics, vol. 141","author":"D Perrin","year":"2004","unstructured":"Perrin, D., Pin, J.\u00c9.: Infinite words, Pure and Applied Mathematics, vol. 141. Elsevier, Amsterdam (2004)"},{"key":"9763_CR20","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-2215-3","volume-title":"Varieties of Formal Languages","author":"J\u00c9 Pin","year":"1986","unstructured":"Pin, J.\u00c9.: Varieties of Formal Languages. North Oxford Academic Publishers Ltd, Oxford (1986)"},{"key":"9763_CR21","doi-asserted-by":"crossref","unstructured":"Place, T.H., van Rooijen, L., Zeitoun, M.: Separating regular languages by piecewise testable and unambiguous languages MFCS 2013, Proceedings, pp. 729\u2013740. Springer (2013)","DOI":"10.1007\/978-3-642-40313-2_64"},{"key":"9763_CR22","doi-asserted-by":"crossref","first-page":"190","DOI":"10.1016\/S0019-9958(65)90108-7","volume":"8","author":"M Sch\u00fctzenberger","year":"1965","unstructured":"Sch\u00fctzenberger, M.: On finite monoids having only trivial subgroups. Inf. Control. 8, 190\u2013194 (1965)","journal-title":"Inf. Control."},{"key":"9763_CR23","doi-asserted-by":"crossref","unstructured":"Schwentick, T.H., 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, Proceedings, LNCS, vol. 2295, pp. 239\u2013250. Springer (2002)","DOI":"10.1007\/3-540-46011-X_20"},{"key":"9763_CR24","doi-asserted-by":"crossref","unstructured":"Simon, I.: Piecewise testable events. In: Automata Theory and Formal Languages, 2nd GI Conference ., LNCS, vol. 33, pp. 214\u2013222. Springer (1975)","DOI":"10.1007\/3-540-07407-4_23"},{"issue":"1","key":"9763_CR25","doi-asserted-by":"crossref","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. Theor. Comput. Sci. 72(1), 65\u201394 (1990)","journal-title":"Theor. Comput. Sci."},{"key":"9763_CR26","doi-asserted-by":"crossref","unstructured":"Tesson, P., Th\u00e9rien, D.: Diamonds are forever: The variety DA. In: dos Gomes Moreira da Cunha, G.M., da Silva, P.V.A., Pin, J.\u00c9. (eds.) Semigroups, Algorithms, Automata and Languages, pp. 475\u2013500. World Scientific (2002)","DOI":"10.1142\/9789812776884_0021"},{"key":"9763_CR27","doi-asserted-by":"crossref","unstructured":"Th\u00e9rien, D., Wilke, T.H.: Over words, two variables are as powerful as one quantifier alternation. In: Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, pp. 234\u2013240. ACM (1998)","DOI":"10.1145\/276698.276749"},{"issue":"4","key":"9763_CR28","doi-asserted-by":"crossref","first-page":"491","DOI":"10.1007\/s000120050033","volume":"37","author":"P Trotter","year":"1997","unstructured":"Trotter, P., Weil, P.: The lattice of pseudovarieties of idempotent semigroups and a non-regular analogue. Algebra Univers. 37(4), 491\u2013526 (1997)","journal-title":"Algebra Univers."},{"key":"9763_CR29","unstructured":"van Rooijen, L., Zeitoun, M.: The separation problem for regular languages by piecewise testable languages. arXiv: 1303.2143 (2013)"},{"issue":"3","key":"9763_CR30","first-page":"1","volume":"5","author":"PH Weis","year":"2009","unstructured":"Weis, Ph., Immerman, N.: Structure Theorem and Strict Alternation Hierarchy for F O 2 on Words. Logical Methods in Computer Science 5(3), 1\u201323 (2009)","journal-title":"Logical Methods in Computer Science"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-017-9763-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-017-9763-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-017-9763-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,24]],"date-time":"2019-09-24T13:49:45Z","timestamp":1569332985000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-017-9763-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,5,16]]},"references-count":30,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,4]]}},"alternative-id":["9763"],"URL":"https:\/\/doi.org\/10.1007\/s00224-017-9763-z","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2017,5,16]]}}}