{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T19:29:36Z","timestamp":1725564576893},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540212362"},{"type":"electronic","value":"9783540247494"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-24749-4_5","type":"book-chapter","created":{"date-parts":[[2010,9,8]],"date-time":"2010-09-08T15:01:54Z","timestamp":1283958114000},"page":"44-55","source":"Crossref","is-referenced-by-count":5,"title":["Constant Width Planar Computation Characterizes ACC0"],"prefix":"10.1007","author":[{"given":"Kristoffer Arnsfelt","family":"Hansen","sequence":"first","affiliation":[]}],"member":"297","reference":[{"issue":"1","key":"5_CR1","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1016\/0022-0000(89)90037-8","volume":"38","author":"D.A. Barrington","year":"1989","unstructured":"Barrington, D.A.: Bounded-width polynomial-size branching programs recognize exactly those languages in NC1. J. Comput. System Sci.\u00a038(1), 150\u2013164 (1989)","journal-title":"J. Comput. System Sci."},{"key":"5_CR2","doi-asserted-by":"crossref","unstructured":"Mix Barrington, D.A., Lu, C.-J., Miltersen, P.B., Skyum, S.: Searching constant width mazes captures the AC0 hierarchy. In: Proceedings of the 15th Annual Symposium on Theoretical Aspects of Computer Science, pp. 73\u201383 (1998)","DOI":"10.1007\/BFb0028550"},{"key":"5_CR3","first-page":"24","volume-title":"14th Annual IEEE Conference on Computational Complexity","author":"D.A. Mix Barrington","year":"1999","unstructured":"Mix Barrington, D.A., Lu, C.-J., Miltersen, P.B., Skyum, S.: On monotone planar circuits. In: 14th Annual IEEE Conference on Computational Complexity, pp. 24\u201331. IEEE Computer Society Press, Los Alamitos (1999)"},{"key":"5_CR4","doi-asserted-by":"publisher","first-page":"941","DOI":"10.1145\/48014.63138","volume":"35","author":"D.A. Mix Barrington","year":"1988","unstructured":"Mix Barrington, D.A., Th\u00e9rien, D.: Finite monoids and the fine structure of NC1. Journal of the ACM (JACM)\u00a035, 941\u2013952 (1988)","journal-title":"Journal of the ACM (JACM)"},{"issue":"2-3","key":"5_CR5","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1016\/0304-3975(88)90123-5","volume":"61","author":"G. Battista Di","year":"1988","unstructured":"Di Battista, G., Tamassia, R.: Algorithms for plane representations of acyclic digraphs. Theoretical Computer Science\u00a061(2-3), 175\u2013198 (1988)","journal-title":"Theoretical Computer Science"},{"key":"5_CR6","first-page":"646","volume":"7","author":"D. Edmonds","year":"1960","unstructured":"Edmonds, D.: A combinatorial representation for polyhedral surfaces. Notices Amer. Math. Soc.\u00a07, 646 (1960)","journal-title":"Notices Amer. Math. Soc."},{"key":"5_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"220","DOI":"10.1007\/3-540-54458-5_66","volume-title":"Fundamentals of Computation Theory","author":"H.D. Gr\u00f6ger","year":"1991","unstructured":"Gr\u00f6ger, H.D.: A new partition lemma for planar graphs and its application to circuit complexity. In: Budach, L. (ed.) FCT 1991. LNCS, vol.\u00a0529, pp. 220\u2013229. Springer, Heidelberg (1991)"},{"key":"5_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/978-3-540-45077-1_17","volume-title":"Fundamentals of Computation Theory","author":"K.A. Hansen","year":"2003","unstructured":"Hansen, K.A., Miltersen, P.B., Vinay, V.: Circuits on cylinders. In: Lingas, A., Nilsson, B.J. (eds.) FCT 2003. LNCS, vol.\u00a02751, pp. 171\u2013182. Springer, Heidelberg (2003)"},{"issue":"2,3","key":"5_CR9","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/0012-365X(87)90008-2","volume":"63","author":"D. Kelly","year":"1987","unstructured":"Kelly, D.: Fundamentals of planar ordered sets. Discrete Mathematics\u00a063(2,3), 197\u2013216 (1987)","journal-title":"Discrete Mathematics"},{"issue":"3","key":"5_CR10","doi-asserted-by":"publisher","first-page":"615","DOI":"10.1137\/0209046","volume":"9","author":"R.J. Lipton","year":"1980","unstructured":"Lipton, R.J., Tarjan, R.E.: Applications of a planar separator theorem. SIAM Journal on Computing\u00a09(3), 615\u2013627 (1980)","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"5_CR11","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1007\/BF02187705","volume":"1","author":"R. Tamassia","year":"1986","unstructured":"Tamassia, R., Tollis, I.G.: A unified approach to visibility representations of planar graphs. Discrete & Computational Geometry\u00a01(1), 312\u2013341 (1986)","journal-title":"Discrete & Computational Geometry"},{"key":"5_CR12","unstructured":"Tamassia, R., Tollis, I.G.: Tessellation representations of planar graphs. In: Proceedings 27th Annual Allerton Conference on Communications, Control and Computing, September 1989, University of Illinois at Urbana-Champaign, pp. 48\u201357 (1989)"},{"key":"5_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"460","DOI":"10.1007\/3-540-51498-8_45","volume-title":"Fundamentals of Computation Theory","author":"G. Tur\u00e1n","year":"1989","unstructured":"Tur\u00e1n, G.: On restricted boolean circuits. In: Csirik, J.A., Demetrovics, J., Gecseg, F. (eds.) FCT 1989. LNCS, vol.\u00a0380, pp. 460\u2013469. Springer, Heidelberg (1989)"},{"key":"5_CR14","first-page":"108","volume-title":"11th Annual IEEE Conference on Computational Complexity","author":"V. Vinay","year":"1996","unstructured":"Vinay, V.: Hierarchies of circuit classes that are closed under complement. In: 11th Annual IEEE Conference on Computational Complexity, pp. 108\u2013117. IEEE Computer Society, Los Alamitos (1996)"},{"key":"5_CR15","volume-title":"Graphs, Groups and Surfaces","author":"A.T. White","year":"1984","unstructured":"White, A.T.: Graphs, Groups and Surfaces. Elsevier Science Publishers B.V., Amsterdam (1984)"},{"key":"5_CR16","doi-asserted-by":"publisher","first-page":"619","DOI":"10.1109\/FSCS.1990.89583","volume-title":"Proceedings 31st Annual Symposium on Foundations of Computer Science","author":"C.-C. Yao","year":"1990","unstructured":"Yao, C.-C.: On ACC0 and threshold circuits. In: Proceedings 31st Annual Symposium on Foundations of Computer Science, pp. 619\u2013627. IEEE Computer Society Press, Los Alamitos (1990)"}],"container-title":["Lecture Notes in Computer Science","STACS 2004"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-24749-4_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,4]],"date-time":"2019-06-04T01:32:39Z","timestamp":1559611959000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-24749-4_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540212362","9783540247494"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-24749-4_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}