{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,10]],"date-time":"2026-11-10T21:41:08Z","timestamp":1794346868740,"version":"4.9.0"},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540434535","type":"print"},{"value":"9783540460114","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-46011-x_20","type":"book-chapter","created":{"date-parts":[[2007,6,18]],"date-time":"2007-06-18T18:54:16Z","timestamp":1182192856000},"page":"239-250","source":"Crossref","is-referenced-by-count":38,"title":["Partially-Ordered Two-Way Automata: A New Characterization of DA"],"prefix":"10.1007","author":[{"given":"Thomas","family":"Schwentick","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Denis","family":"Th\u00e9rien","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Heribert","family":"Vollmer","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2002,3,19]]},"reference":[{"key":"20_CR1","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1016\/0304-3975(91)90268-7","volume":"91","author":"M. Arfi","year":"1991","unstructured":"M. Arfi. Op\u00e9ration polynomiales et hi\u00e9rarchies de concat\u00e9nation. Theoretical Computer Science, 91:71\u201384, 1991.","journal-title":"Theoretical Computer Science"},{"key":"20_CR2","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1016\/0304-3975(89)90075-3","volume":"63","author":"J.-C. Birget","year":"1989","unstructured":"J.-C. Birget. Concatenation of inputs in a two-way automaton. Theoretical Computer Science, 63:141\u2013156, 1989.","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"20_CR3","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1016\/0022-0000(92)90045-K","volume":"45","author":"J.-C. Birget","year":"1992","unstructured":"J.-C. Birget. Positional simulation of two-way automata: Proof of a conjecture of R. Kannan and generalizations. Journal of Computer and System Sciences, 45(2):154\u2013179, 1992.","journal-title":"Journal of Computer and System Sciences"},{"key":"20_CR4","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1007\/3-540-48523-6_28","volume-title":"Two-way finite state transducers and monadic second-order logic","author":"J. Engelfriet","year":"1999","unstructured":"J. Engelfriet and H. Hoogeboom. Two-way finite state transducers and monadic second-order logic. In Proceedings 26th International Colloqium on Automata, Languages and Programming, volume 1644 of Lecture Notes in Computer Science, pages 311\u2013320, Berlin Heidelberg, 1999. Springer Verlag."},{"key":"20_CR5","volume-title":"Automata, Languages, and Machines","author":"S. Eilenberg","year":"1976","unstructured":"S. Eilenberg. Automata, Languages, and Machines, volume B. Academic Press, NewYork, 1976."},{"key":"20_CR6","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1016\/S0304-3975(96)00119-3","volume":"169","author":"N. Globerman","year":"1996","unstructured":"N. Globerman and D. Harel. Complexity results for two-way and multi-pebble automata and their logics. Theoretical Computer Science, 169:161\u2013184, 1996.","journal-title":"Theoretical Computer Science"},{"key":"20_CR7","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"433","DOI":"10.1007\/3-540-48523-6_40","volume-title":"Two-way finite automata","author":"J. Hromkovic","year":"1999","unstructured":"J. Hromkovic and G. Schnitger. On the power of Las Vegas II. Two-way finite automata. In Proceedings 26th International Colloqium on Automata, Languages and Programming, volume 1644 of Lecture Notes in Computer Science, pages 433\u2013442, Berlin Heidelberg, 1999. Springer Verlag."},{"key":"20_CR8","volume-title":"Addison-Wesley Series in Computer Science","author":"J. E. Hopcroft","year":"1979","unstructured":"J. E. Hopcroft and J. D. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley Series in Computer Science. Addison-Wesley, Reading, MA, 1979."},{"key":"20_CR9","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1016\/0020-0190(81)90012-0","volume":"12","author":"S. Micali","year":"1981","unstructured":"S. Micali. Two-way deterministic finite automata are exponentially more succinct than sweeping automata. Information Processing Letters, 12:103\u2013105, 1981.","journal-title":"Information Processing Letters"},{"key":"20_CR10","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"890","DOI":"10.1007\/3-540-45022-X_75","volume-title":"The many faces of a translation","author":"P. McKenzie","year":"2000","unstructured":"P. McKenzie, T. Schwentick, D. Th\u00e9rien, and H. Vollmer. The many faces of a translation. In Proceedings 27th International Colloqium on Automata, Languages and Programming, volume 1853 of Lecture Notes in Computer Science, pages 890\u2013901, Berlin Heidelberg, 2000. SpringerVerlag. By a mistake of the organizers while reformatting this paper, alas, all equality signs disappeared in the proceedings version. Refer to ftp:\/\/ftp-info4.informatik.uni-wuerzburg.de\/pub\/TRs\/mc-sc-th-vo00.ps.gz for a full version with equality signs."},{"key":"20_CR11","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-2215-3","volume-title":"Varieties of Formal Languages","author":"J. E. Pin","year":"1986","unstructured":"J. E. Pin. Varieties of Formal Languages. Plenum Press, NewYork, 1986."},{"key":"20_CR12","doi-asserted-by":"crossref","first-page":"679","DOI":"10.1007\/978-3-642-59136-5_10","volume-title":"Handbook of Formal Languages","author":"J. E. Pin","year":"1997","unstructured":"J. E. Pin. Syntactic semigroups. In G. Rozenberg and A. Salomaa, editors, Handbook of Formal Languages, volume I, pages 679\u2013746. SpringerVerlag, Berlin Heidelberg, 1997."},{"key":"20_CR13","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1007\/s002240000058","volume":"30","author":"J.-E. Pin","year":"1997","unstructured":"J.-E. Pin and P. Weil. Polynomial closure and unambiguous product. Theory of Computing Systems, 30:383\u2013422, 1997.","journal-title":"Theory of Computing Systems"},{"key":"20_CR14","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1007\/BF02194921","volume":"13","author":"M. Sch\u00fctzenberger","year":"1976","unstructured":"M. Sch\u00fctzenberger. Sur le produit de concatenation non ambigu. Semigroup Forum, 13:47\u201375, 1976.","journal-title":"Semigroup Forum"},{"key":"20_CR15","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0289-9","volume-title":"Finite Automata, Formal Logic, and Circuit Complexity","author":"H. Straubing","year":"1994","unstructured":"H. Straubing. Finite Automata, Formal Logic, and Circuit Complexity. Birkh\u00e4user, Boston, 1994."},{"key":"20_CR16","doi-asserted-by":"crossref","unstructured":"D. Th\u00e9rien and T. Wilke. Over words, two variables are as powerful as one quantifier alternation: FO2 = \u03a32 \u2229 \u03a02. In Proceedings 30th Symposium on Theory of Computing, pages 234\u2013240, NewYork, 1998. ACM Press.","DOI":"10.1145\/276698.276749"}],"container-title":["Lecture Notes in Computer Science","Developments in Language Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-46011-X_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,17]],"date-time":"2025-01-17T04:01:26Z","timestamp":1737086486000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-46011-X_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540434535","9783540460114"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/3-540-46011-x_20","relation":{"is-part-of":[{"id-type":"doi","id":"https:\/\/doi.org\/10.1007\/3-540-46011-x","asserted-by":"object"}]},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[2002]]}}}