{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:50:30Z","timestamp":1725490230057},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540424963"},{"type":"electronic","value":"9783540446835"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-44683-4_52","type":"book-chapter","created":{"date-parts":[[2007,8,28]],"date-time":"2007-08-28T21:32:38Z","timestamp":1188336758000},"page":"598-610","source":"Crossref","is-referenced-by-count":2,"title":["From Bidirectionality to Alternation"],"prefix":"10.1007","author":[{"given":"Nir","family":"Piterman","sequence":"first","affiliation":[]},{"given":"Moshe Y.","family":"Vardi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2001,9,5]]},"reference":[{"issue":"3","key":"52_CR1","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1007\/BF01371727","volume":"26","author":"J. C. Birget","year":"1993","unstructured":"J. C. Birget. State-complexity of finite-state devices, state compressibility and incompressibility. Mathematical Systems Theory, 26(3):237\u2013269, 1993.","journal-title":"Mathematical Systems Theory"},{"key":"52_CR2","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/0304-3975(80)90069-9","volume":"10","author":"J. A. Brzozowski","year":"1980","unstructured":"J. A. Brzozowski and E. Leiss. Finite automata and sequential networks. Theoretical Computer Science, 10:19\u201335, 1980.","journal-title":"Theoretical Computer Science"},{"key":"52_CR3","unstructured":"J. R. B\u00fcchi. On a decision method in restricted second order arithmetic. In Proc. Internat. Congr. Logic, Method. and Philos. Sci. 1960, pages 1\u201312, Stanford, 1962. Stanford University Press."},{"key":"52_CR4","doi-asserted-by":"crossref","unstructured":"D. Calvanese, G. de Giacomo, M. Lenzerini, and M. Y. Vardi. View-based query processing for regular path queries with inverse. In 19th PODS, 58\u201366, ACM, 2000.","DOI":"10.1145\/335168.335207"},{"key":"52_CR5","doi-asserted-by":"crossref","unstructured":"A. K. Chandra, D. C. Kozen, and L. J. Stockmeyer. Alternation. Journal of the Association for Computing Machinery, 28(1):114\u2013133, January 1981.","DOI":"10.1145\/322234.322243"},{"key":"52_CR6","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1016\/S0304-3975(96)00119-3","volume":"143","author":"N. Globerman","year":"1996","unstructured":"N. Globerman and D. Harel. Complexity results for two-way and multi-pebble automata and their logics. TCS, 143:161\u2013184, 1996.","journal-title":"TCS"},{"issue":"12","key":"52_CR7","doi-asserted-by":"publisher","first-page":"805","DOI":"10.1145\/364175.364185","volume":"11","author":"W. L. Johnson","year":"1968","unstructured":"W. L. Johnson, J. H. Porter, S. I. Ackley, and D. T. Ross. Automatic generation of efficient lexical processors using finite state techniques. Communications of the ACM, 11(12):805\u2013813, 1968.","journal-title":"Communications of the ACM"},{"key":"52_CR8","volume-title":"Switching and Finite Automata Theory","author":"Z. Kohavi","year":"1970","unstructured":"Z. Kohavi. Switching and Finite Automata Theory. McGraw-Hill, New York, 1970."},{"key":"52_CR9","doi-asserted-by":"crossref","unstructured":"R. P. Kurshan. Computer Aided Verification of Coordinating Processes. Princeton Univ. Press, 1994.","DOI":"10.1515\/9781400864041"},{"key":"52_CR10","doi-asserted-by":"crossref","unstructured":"O. Kupferman and M. Y. Vardi. Synthesis with incomplete informatio. In Advances in Temporal Logic, pages 109\u2013127. Kluwer Academic Publishers, January 2000.","DOI":"10.1007\/978-94-015-9586-5_6"},{"issue":"1","key":"52_CR11","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1137\/0213010","volume":"13","author":"R. E. Ladner","year":"1984","unstructured":"Richard E. Ladner, Richard J. Lipton, and Larry J. Stockmeyer. Al-ternating pushdown and stack automata. SIAM Journal on Computing, 13(1):135\u2013155, 1984.","journal-title":"SIAM Journal on Computing"},{"key":"52_CR12","doi-asserted-by":"publisher","first-page":"521","DOI":"10.1016\/S0019-9958(66)80013-X","volume":"9","author":"R. McNaughton","year":"1966","unstructured":"R. McNaughton. Testing and generating infinite sequences by a finite automaton. Information and Control, 9:521\u2013530, 1966.","journal-title":"Information and Control"},{"key":"52_CR13","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1016\/0304-3975(84)90049-5","volume":"32","author":"S. Miyano","year":"1984","unstructured":"S. Miyano and T. Hayashi. Alternating finite automata on \u03c9-words. Theoretical Computer Science, 32:321\u2013330, 1984.","journal-title":"Theoretical Computer Science"},{"key":"52_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.2307\/1995086","volume":"141","author":"M. O. Rabin","year":"1969","unstructured":"M. O. Rabin. Decidability of second order theories and automata on infinite trees. Transaction of the AMS, 141:1\u201335, 1969.","journal-title":"Transaction of the AMS"},{"key":"52_CR15","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1147\/rd.32.0114","volume":"3","author":"M. O. Rabin","year":"1959","unstructured":"M. O. Rabin and D. Scott. Finite automata and their decision problems. IBM Journal of Research and Development, 3:115\u2013125, 1959.","journal-title":"IBM Journal of Research and Development"},{"key":"52_CR16","first-page":"218","volume":"21","author":"W. Ruzzo","year":"1980","unstructured":"W. Ruzzo. Tree-size bounded alternation. JCSS, 21:218\u2013235, 1980.","journal-title":"JCSS"},{"key":"52_CR17","doi-asserted-by":"publisher","first-page":"198","DOI":"10.1147\/rd.32.0198","volume":"3","author":"J. C. Shepherdson","year":"1959","unstructured":"J. C. Shepherdson. The reduction of two-way automata to one-way automata. IBM Journal of Research and Development, 3:198\u2013200, 1959.","journal-title":"IBM Journal of Research and Development"},{"key":"52_CR18","doi-asserted-by":"crossref","unstructured":"W. J. Sakoda and M. Sipser. Nondeterminism and the size of two way finite automata. In 10th STOC, 275\u2013286, 1978. ACM.","DOI":"10.1145\/800133.804357"},{"key":"52_CR19","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/S0019-9958(82)91258-X","volume":"54","author":"R. S. Streett","year":"1982","unstructured":"R. S. Streett. Propositional dynamic logic of looping and converse. Information and Control, 54:121\u2013141, 1982.","journal-title":"Information and Control"},{"key":"52_CR20","doi-asserted-by":"crossref","unstructured":"M. Y. Vardi. A temporal fixpoint calculus. In Proc. 15th ACM Symp. on Principles of Programming Languages, 250\u2013259, 1988.","DOI":"10.1145\/73560.73582"},{"issue":"5","key":"52_CR21","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1016\/0020-0190(89)90205-6","volume":"30","author":"M. Y. Vardi","year":"1989","unstructured":"M. Y. Vardi. A note on the reduction of two-way automata to one-way automata. Information Processing Letters, 30(5):261\u2013264, March 1989.","journal-title":"Information Processing Letters"},{"issue":"3","key":"52_CR22","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1016\/0020-0190(90)90063-4","volume":"35","author":"M. Y. Vardi","year":"1990","unstructured":"M. Y. Vardi. Endmarkers can make a difference. Information Processing Letters, 35(3):145\u2013148, July 1990.","journal-title":"Information Processing Letters"},{"key":"52_CR23","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"628","DOI":"10.1007\/BFb0055090","volume-title":"25th ICALP","author":"M. Y. Vardi","year":"1998","unstructured":"M. Y. Vardi. Reasoning about the past with two-way automata. In 25th ICALP, LNCS 1443, 628\u2013641. Springer-Verlag, July 1998."},{"issue":"2","key":"52_CR24","first-page":"380","volume":"43","author":"H. Venkateswaran","year":"1991","unstructured":"H. Venkateswaran. Properties that characterize logCFL. JCSS, 43(2):380\u2013404, 1991.","journal-title":"JCSS"},{"key":"52_CR25","unstructured":"M. Y. Vardi and P. Wolper. An automata-theoretic approach to automatic program verification. In 1st LICS, 332\u2013344, 1986."}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2001"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44683-4_52","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,2]],"date-time":"2019-05-02T13:27:58Z","timestamp":1556803678000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44683-4_52"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540424963","9783540446835"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/3-540-44683-4_52","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}