{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T18:59:35Z","timestamp":1725562775747},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540642305"},{"type":"electronic","value":"9783540697053"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1998]]},"DOI":"10.1007\/bfb0028550","type":"book-chapter","created":{"date-parts":[[2005,11,22]],"date-time":"2005-11-22T07:33:39Z","timestamp":1132644819000},"page":"73-83","source":"Crossref","is-referenced-by-count":13,"title":["Searching constant width mazes captures the AC 0 hierarchy"],"prefix":"10.1007","author":[{"given":"David A. Mix","family":"Barrington","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chi-Jen","family":"Lu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter Bro","family":"Miltersen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sven","family":"Skyum","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,20]]},"reference":[{"key":"8_CR1","doi-asserted-by":"crossref","unstructured":"D. A. M. Barrington, N. Immerman and H. Straubing. On uniformity within NC 1 Journal of Computer and System Sciences, 4(3):274\u2013306.","DOI":"10.1016\/0022-0000(90)90022-D"},{"issue":"4","key":"8_CR2","doi-asserted-by":"publisher","first-page":"941","DOI":"10.1145\/48014.63138","volume":"35","author":"D. A. M. M. Barrington","year":"1988","unstructured":"D. A. M. Mix Barrington and D. Th\u00e9rien. Finite monoids and the fine structure of NC1. Journal of the ACM, 35(4):941\u2013952, October 1988.","journal-title":"Journal of the ACM"},{"key":"8_CR3","unstructured":"P. Beame and F. Fich. On searching sorted lists: A near-optimal lower bound. Manuscript, 1997."},{"key":"8_CR4","doi-asserted-by":"crossref","unstructured":"M. Blum and D. Kozen. On the power of the compass (or why mazes are easier to search than graphs). In 19th Annual Symposium on the Foundations of Computer Science, pages 132\u2013142, October 1978.","DOI":"10.1109\/SFCS.1978.30"},{"key":"8_CR5","unstructured":"D. Eppstein. Dynamic connectivity in digital images. Technical Report 96-13, Univ. of California, Irvine, Department of Information and Computer Science, 1996."},{"key":"8_CR6","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1016\/0196-6774(92)90004-V","volume":"13","author":"D. Eppstein","year":"1992","unstructured":"D. Eppstein, G. Italiano, R. Tamassia, R. E. Tarjan, J. Westbrook, and M. Yung. Maintenance of a minimum spanning forest in a dynamic planar graph. Journal of Algorithms, 13:33\u201354, 1992.","journal-title":"Journal of Algorithms"},{"key":"8_CR7","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1145\/256303.256309","volume":"44","author":"G. S. Frandsen","year":"1997","unstructured":"G. S. Frandsen, P. B. Miltersen, and S. Skyum. Dynamic word problems. Journal of the ACM 44:257\u2013271, 1997.","journal-title":"Journal of the ACM"},{"key":"8_CR8","doi-asserted-by":"crossref","unstructured":"T. Husfeldt and T. Rauhe. Hardness results for dynamic problems by extensions of Fredman annd Saks chronogram method.. Manuscript, 1997.","DOI":"10.7146\/brics.v4i32.18958"},{"issue":"4","key":"8_CR9","doi-asserted-by":"publisher","first-page":"760","DOI":"10.1137\/0216051","volume":"16","author":"N. Immerman","year":"1987","unstructured":"N. Immerman. Languages that capture complexity classes.SIAM Journal on Computing, 16(4):760\u2013778, 1987.","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"8_CR10","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1006\/inco.1995.1007","volume":"116","author":"N. Immerman","year":"1995","unstructured":"N. Immerman and S. Landau. The complexity of iterated multiplication. Information and Computation, 116(1):103\u2013116, January 1995.","journal-title":"Information and Computation"},{"issue":"4","key":"8_CR11","doi-asserted-by":"publisher","first-page":"676","DOI":"10.1137\/0211056","volume":"11","author":"A. Itai","year":"1982","unstructured":"A. Itai, C. H. Papadimitriou, and J. L. Szwarcfiter. Hamilton paths in grid graphs. SIAM Journal on Computing, 11(4):676\u2013686, 1982.","journal-title":"SIAM Journal on Computing"},{"key":"8_CR12","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. New York: Plenum Press, 1986."},{"key":"8_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1007\/3-540-54458-5_49","volume-title":"Fundamentals of Computation Theory, 8th International Conference: FCT '91","author":"A. A. Razborov","year":"1991","unstructured":"A. A. Razborov. Lower Bounds for deterministic and nondeterministic branching programs. In L. Budach, ed., Fundamentals of Computation Theory, 8th International Conference: FCT '91. Lecture Notes in Computer Science 529, 47\u201360. Berlin, Springer Verlag, 1991."},{"key":"8_CR14","doi-asserted-by":"crossref","unstructured":"M. Sipser. Borel sets and circuit complexity. In Proceedings, 15th ACM Symposium on the Theory of Computing, 1983, 61\u201369.","DOI":"10.1145\/800061.808733"},{"issue":"2","key":"8_CR15","doi-asserted-by":"publisher","first-page":"484","DOI":"10.1145\/3149.3158","volume":"32","author":"S. Skyum","year":"1985","unstructured":"S. Skyum and L. G. Valiant. A complexity theory based on Boolean algebra. Journal of the ACM, 32(2):484\u2013502, April 1985.","journal-title":"Journal of the ACM"},{"key":"8_CR16","doi-asserted-by":"publisher","first-page":"360","DOI":"10.1016\/0022-0000(82)90016-2","volume":"25","author":"W. Thomas","year":"1982","unstructured":"W. Thomas. Classifying regular events in symbolic logic. J. Comput. System Sci. 25, 1982, 360\u2013376.","journal-title":"J. Comput. System Sci."}],"container-title":["Lecture Notes in Computer Science","STACS 98"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0028550","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,11]],"date-time":"2020-04-11T02:54:41Z","timestamp":1586573681000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0028550"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540642305","9783540697053"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/bfb0028550","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1998]]}}}