{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:54:59Z","timestamp":1725663299347},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540127277"},{"type":"electronic","value":"9783540387145"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1983]]},"DOI":"10.1007\/3-540-12727-5_25","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T17:54:54Z","timestamp":1330192494000},"page":"392-404","source":"Crossref","is-referenced-by-count":3,"title":["Alternating tree automata"],"prefix":"10.1007","author":[{"given":"Giora","family":"Slutzki","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,29]]},"reference":[{"key":"25_CR1","doi-asserted-by":"crossref","unstructured":"Berman, L. Precise Bounds for Presburger Arithmetic and the Reals with Addition. 18th Symposium FOCS, 1977, pp. 95\u201399.","DOI":"10.1109\/SFCS.1977.23"},{"key":"25_CR2","doi-asserted-by":"crossref","unstructured":"Chandra, A. K. and Stockmeyer, L. J. Alternation. 17th Symposium FOCS, 1976, pp. 98\u2013108.","DOI":"10.1109\/SFCS.1976.4"},{"key":"25_CR3","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1145\/322234.322243","volume":"28","author":"A. K. Chandra","year":"1981","unstructured":"Chandra, A. K., Kozen, D. C. and Stockmeyer, L. J. Alternation. JACM 28 (1981), pp. 114\u2013133.","journal-title":"JACM"},{"key":"25_CR4","first-page":"406","volume":"4","author":"J. Doner","year":"1970","unstructured":"Doner, J. Tree Acceptors and Some of Their Applications. JCSS 4 (1970), pp. 406\u2013451.","journal-title":"JCSS"},{"key":"25_CR5","series-title":"Lecture Notes DAIMI","volume-title":"Tree Automata and Tree Grammars","author":"J. Engelfriet","year":"1975","unstructured":"Engelfriet, J. Tree Automata and Tree Grammars. Lecture Notes DAIMI FN-10, University of Aarhus, Denmark, 1975."},{"key":"25_CR6","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/BF01704020","volume":"9","author":"J. Engelfriet","year":"1975","unstructured":"Engelfriet, J. Bottom-up and Top-down Tree Transformations\u2014A Comparison. Math. Systems Theory 9 (1975), pp. 193\u2013231.","journal-title":"Math. Systems Theory"},{"key":"25_CR7","first-page":"150","volume":"20","author":"J. Engelfriet","year":"1980","unstructured":"Engelfriet, J. Rozenberg, G. and Slutzki, G. Tree Transducers, L-Systems, and Two-way Machines. JCSS 20 (1980), pp. 150\u2013202.","journal-title":"JCSS"},{"key":"25_CR8","doi-asserted-by":"crossref","unstructured":"Fischer, M. J. and Ladner, R. E. Propositional Modal Logic of Programs. 9th ACM STOC, 1977, pp. 286\u2013294.","DOI":"10.1145\/800105.803418"},{"key":"25_CR9","doi-asserted-by":"crossref","unstructured":"Kozen, D. C. On Parallelism in Turing Machines. 17th Symposium FOCS, 1976, pp. 89\u201397.","DOI":"10.1109\/SFCS.1976.20"},{"key":"25_CR10","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1016\/0304-3975(80)90048-1","volume":"70","author":"D. C. Kozen","year":"1980","unstructured":"Kozen, D. C. Complexity of Boolean Algebras. Theoretical Computer Science 70 (1980), pp. 221\u2013247.","journal-title":"Theoretical Computer Science"},{"key":"25_CR11","unstructured":"Kamimura, T. Tree Automata and Attribute Grammars. TR-82-1, Dept. of Comp. Sci., Univ. of Kansas, Lawrence, Kansas, 66045, USA."},{"key":"25_CR12","doi-asserted-by":"publisher","first-page":"574","DOI":"10.1137\/0208046","volume":"8","author":"T. Kasai","year":"1979","unstructured":"Kasai, T., Adachi, A. and Iwata, S. Classes of Pebble Games and Complete Problems. SIAM Journal of Computing 8 (1979), pp. 574\u2013586.","journal-title":"SIAM Journal of Computing"},{"key":"25_CR13","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1016\/S0019-9958(81)90438-1","volume":"49","author":"T. Kamimura","year":"1981","unstructured":"Kamimura, T. and Slutzki, G. Parallel and Two-way Automata on Directed Ordered Acyclic. Graphs. Information and Control 49 (1981), pp. 10\u201351.","journal-title":"Information and Control"},{"key":"25_CR14","doi-asserted-by":"crossref","unstructured":"Ladner, R. E., Lipton, R. J. and Stockmeyer, L. J. Alternating Pushdown Automata. 19th Symposium FOCS, 1978, pp. 92\u2013106.","DOI":"10.1109\/SFCS.1978.6"},{"key":"25_CR15","unstructured":"Magidor, M. and Moran, G. Finite Automata over Finite Trees. TR-69-30, Dept. of Math., Hebrew Univ., Jerusalem, Israel."},{"key":"25_CR16","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1090\/psapm\/019\/0239886","volume":"19","author":"M. O. Rabin","year":"1968","unstructured":"Rabin, M. O. Matheamtical Theory of Automata. Proc. Symp. Appl. Math., Vol. 19, AMS, Providence, R. I., 1968, pp. 153\u2013175.","journal-title":"Proc. Symp. Appl. Math."},{"key":"25_CR17","unstructured":"Slutzki, G. Alternating, Nondeterministic and Universal Pushdown Automata. TR-82-2, Dept. of Comp. Sci., Univ. of Kansas, Lawrence, Kansas, 66045, USA."},{"key":"25_CR18","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1137\/0208013","volume":"8","author":"L. J. Stockmeyer","year":"1979","unstructured":"Stockmeyer, L. J. and Chandra, A. K. Provably Difficult Combinatorial Games. SIAM Journal of Computing 8 (1979), pp. 151\u2013174.","journal-title":"SIAM Journal of Computing"},{"key":"25_CR19","unstructured":"Thatcher, J. W. Tree Automata: informal survey. In \"Currents in the Theory of Computing\" (A. V. Aho, Ed.), Prentice-Hall, Englewood Cliffs, N. J., pp. 143\u2013172."},{"key":"25_CR20","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1007\/BF01691346","volume":"2","author":"J. W. Thatcher","year":"1968","unstructured":"Thatcher, J. W. and Wright, J. B. Generalized Finite Automate Theory with an Application to a Decision Problem of Second Order Logic. Math. Systems Theory 2 (1968), pp. 57\u201381.","journal-title":"Math. Systems Theory"}],"container-title":["Lecture Notes in Computer Science","CAAP'83"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-12727-5_25.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T20:06:14Z","timestamp":1605643574000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-12727-5_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1983]]},"ISBN":["9783540127277","9783540387145"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/3-540-12727-5_25","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1983]]}}}