{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,7]],"date-time":"2025-01-07T22:10:16Z","timestamp":1736287816281,"version":"3.32.0"},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540323013"},{"type":"electronic","value":"9783540322887"}],"license":[{"start":{"date-parts":[[2006,1,1]],"date-time":"2006-01-01T00:00:00Z","timestamp":1136073600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11672142_54","type":"book-chapter","created":{"date-parts":[[2006,2,28]],"date-time":"2006-02-28T08:27:54Z","timestamp":1141115274000},"page":"660-671","source":"Crossref","is-referenced-by-count":8,"title":["Evaluating Monotone Circuits on Cylinders, Planes and Tori"],"prefix":"10.1007","author":[{"given":"Nutan","family":"Limaye","sequence":"first","affiliation":[]},{"given":"Meena","family":"Mahajan","sequence":"additional","affiliation":[]},{"given":"M. N.","family":"Jayalal Sarma","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"54_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1007\/11590156_19","volume-title":"FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science","author":"E. Allender","year":"2005","unstructured":"Allender, E., Datta, S., Roy, S.: The directed planar reachability problem. In: Ramanujam, R., Sen, S. (eds.) FSTTCS 2005. LNCS, vol.\u00a03821, pp. 238\u2013249. Springer, Heidelberg (2005)"},{"key":"54_CR2","doi-asserted-by":"crossref","unstructured":"Allender, E., Datta, S., Roy, S.: Topology inside NC1. In: Proc. 20th IEEE Conference on Computational Complexity, pp. 298\u2013307 (2005)","DOI":"10.1109\/CCC.2005.31"},{"issue":"1","key":"54_CR3","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1016\/j.ic.2003.09.002","volume":"189","author":"E. Allender","year":"2004","unstructured":"Allender, E., Mahajan, M.: The complexity of planarity testing. Information and Computation\u00a0189(1), 117\u2013134 (2004)","journal-title":"Information and Computation"},{"key":"54_CR4","doi-asserted-by":"crossref","unstructured":"Mix Barrington, D.A., Lu, C.-J., Bro Miltersen, P., Skyum, S.: On monotone planar circuits. In: IEEE Conf. Computational Complexity, pp. 24\u201331 (1999)","DOI":"10.1109\/CCC.1999.766259"},{"key":"54_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, 175\u2013198 (1988)","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"54_CR6","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1137\/S0097539792226278","volume":"24","author":"A.L. Delcher","year":"1995","unstructured":"Delcher, A.L., Kosaraju, S.R.: An NC algorithm for evaluating monotone planar circuits. SIAM Journal of Computing\u00a024(2), 369\u2013375 (1995)","journal-title":"SIAM Journal of Computing"},{"issue":"3","key":"54_CR7","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/0890-5401(89)90009-6","volume":"80","author":"P.W. Dymond","year":"1989","unstructured":"Dymond, P.W., Cook, S.A.: Complexity Theory of Parallel Time and Hardware. Information and Computation\u00a080(3), 205\u2013226 (1989)","journal-title":"Information and Computation"},{"issue":"2","key":"54_CR8","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1145\/1008354.1008356","volume":"9","author":"L.M. Goldschlager","year":"1977","unstructured":"Goldschlager, L.M.: The monotone and planar circuit value problems are logspace complete for P. SIGACT News\u00a09(2), 25\u201329 (1977)","journal-title":"SIGACT News"},{"issue":"1","key":"54_CR9","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/0020-0190(80)90117-9","volume":"10","author":"L.M. Goldschlager","year":"1980","unstructured":"Goldschlager, L.M.: A space efficient algorithm for the monotone planar circuit value problem. Information Processing Letters\u00a010(1), 25\u201327 (1980)","journal-title":"Information Processing Letters"},{"key":"54_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1007\/978-3-540-24749-4_5","volume-title":"STACS 2004","author":"K. Hansen","year":"2004","unstructured":"Hansen, K.: Constant width planar computation characterizes ACC0. In: Diekert, V., Habib, M. (eds.) STACS 2004. LNCS, vol.\u00a02996, pp. 44\u201355. Springer, Heidelberg (2004)"},{"key":"54_CR11","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. Hansen","year":"2003","unstructured":"Hansen, K., Bro Miltersen, P., 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":"54_CR12","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"},{"key":"54_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1007\/3-540-53487-3_48","volume-title":"Foundations of Software Technology and Theoretical Computer Science","author":"S.R. Kosaraju","year":"1990","unstructured":"Kosaraju, S.R.: On the parallel evaluation of classes of circuits. In: Veni Madhavan, C.E., Nori, K.V. (eds.) FSTTCS 1990. LNCS, vol.\u00a0472, pp. 232\u2013237. Springer, Heidelberg (1990)"},{"key":"54_CR14","doi-asserted-by":"publisher","first-page":"687","DOI":"10.1137\/0217044","volume":"17","author":"G.L. Miller","year":"1988","unstructured":"Miller, G.L., Ramachandran, V., Kaltofen, E.: Efficient parallel evaluation of straight-line code and arithmetic circuits. SIAM Jl. Computing\u00a017, 687\u2013695 (1988)","journal-title":"SIAM Jl. Computing"},{"key":"54_CR15","doi-asserted-by":"crossref","unstructured":"Mohar, B., Thomassen, C.: Graphs on Surfaces. John Hopkins Univ. Press (2001)","DOI":"10.56021\/9780801866890"},{"key":"54_CR16","doi-asserted-by":"publisher","first-page":"517","DOI":"10.1016\/S0022-0000(05)80070-4","volume":"49","author":"V. Ramachandran","year":"1994","unstructured":"Ramachandran, V., Reif, J.: Planarity testing in parallel. Journal of Computer and System Sciences\u00a049, 517\u2013561 (1994)","journal-title":"Journal of Computer and System Sciences"},{"key":"54_CR17","doi-asserted-by":"crossref","unstructured":"Reingold, O.: Undirected st-conenctivity in logspace. In: Proc. 37th STOC, pp. 376\u2013385 (2005)","DOI":"10.1145\/1060590.1060647"},{"issue":"1","key":"54_CR18","first-page":"312","volume":"1","author":"R. Tamassia","year":"1986","unstructured":"Tamassia, R., Tollis, I.G.: A unified approach to visibility representations of planar graphs. Discrete and Computational Geometry\u00a01(1), 312\u2013341 (1986)","journal-title":"Discrete and Computational Geometry"},{"key":"54_CR19","unstructured":"Tamassia, R., Tollis, I.G.: Tessellation representations of planar graphs. In: Proc. 27th Allerton Conf. Commun., Control & Computing, UIUC, pp. 48\u201357 (1989)"},{"key":"54_CR20","doi-asserted-by":"publisher","first-page":"380","DOI":"10.1016\/0022-0000(91)90020-6","volume":"42","author":"H. Venkateswaran","year":"1991","unstructured":"Venkateswaran, H.: Properties that characterize LogCFL. Journal of Computer and System Sciences\u00a042, 380\u2013404 (1991)","journal-title":"Journal of Computer and System Sciences"},{"key":"54_CR21","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03927-4","volume-title":"Introduction to Circuit Complexity: A Uniform Approach","author":"H. Vollmer","year":"1999","unstructured":"Vollmer, H.: Introduction to Circuit Complexity: A Uniform Approach. Springer, Heidelberg (1999)"},{"key":"54_CR22","volume-title":"Graphs, Groups and Surfaces","author":"A.T. White","year":"1973","unstructured":"White, A.T.: Graphs, Groups and Surfaces. North-Holland, Amsterdam (1973)"},{"key":"54_CR23","doi-asserted-by":"crossref","unstructured":"Yang, H.: An NC algorithm for the general planar monotone circuit value problem. In: Proc. 3rd IEEE Symp. Parallel & Distributed Processing, pp. 196\u2013203 (1991)","DOI":"10.1109\/SPDP.1991.218279"}],"container-title":["Lecture Notes in Computer Science","STACS 2006"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11672142_54","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,7]],"date-time":"2025-01-07T21:55:21Z","timestamp":1736286921000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11672142_54"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540323013","9783540322887"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/11672142_54","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}