{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T07:39:12Z","timestamp":1743147552632,"version":"3.40.3"},"publisher-location":"Cham","reference-count":20,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319587400"},{"type":"electronic","value":"9783319587417"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"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":[[2017]]},"DOI":"10.1007\/978-3-319-58741-7_13","type":"book-chapter","created":{"date-parts":[[2017,5,11]],"date-time":"2017-05-11T12:59:28Z","timestamp":1494507568000},"page":"119-128","source":"Crossref","is-referenced-by-count":0,"title":["A Deterministic Algorithm for Testing the Equivalence of Read-Once Branching Programs with Small Discrepancy"],"prefix":"10.1007","author":[{"given":"Stefan","family":"Arnold","sequence":"first","affiliation":[]},{"given":"Jacobo","family":"Tor\u00e1n","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,5,12]]},"reference":[{"key":"13_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"489","DOI":"10.1007\/978-3-540-70918-3_42","volume-title":"STACS 2007","author":"M Agrawal","year":"2007","unstructured":"Agrawal, M., Hoang, T.M., Thierauf, T.: The polynomially bounded perfect matching problem is in NC 2. In: Thomas, W., Weil, P. (eds.) STACS 2007. LNCS, vol. 4393, pp. 489\u2013499. Springer, Heidelberg (2007). doi: 10.1007\/978-3-540-70918-3_42"},{"key":"13_CR2","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1016\/S0020-0190(80)90078-2","volume":"10","author":"M Blum","year":"1980","unstructured":"Blum, M., Chandra, A.K., Wegman, M.N.: Equivalence of free boolean graphs can be decided probabilistically in polynomial time. Inf. Process. Lett. 10, 80\u201382 (1980)","journal-title":"Inf. Process. Lett."},{"key":"13_CR3","first-page":"677","volume":"35","author":"E Randal","year":"1986","unstructured":"Randal, E.: Bryant: graph based algorithms for Boolean function manipulation. IEEE Trans. Comput. 35, 677\u2013691 (1986)","journal-title":"IEEE Trans. Comput."},{"key":"13_CR4","doi-asserted-by":"crossref","first-page":"1036","DOI":"10.1137\/S0097539793250330","volume":"24","author":"S Chari","year":"1995","unstructured":"Chari, S., Rohatgi, P., Srinivasan, A.: Randomness-optimal unique element isolation with applications to perfect matching and related problems. SIAM J. Comput. 24, 1036\u20131050 (1995)","journal-title":"SIAM J. Comput."},{"key":"13_CR5","unstructured":"Darwiche, A.: Compiling knowledge into decomposable negation normal form. In: Proceedings of the 16th International Joint Conference on Artifical Intelligence (IJCAI 1999), pp. 284\u2013289 (1999)"},{"key":"13_CR6","doi-asserted-by":"crossref","first-page":"608","DOI":"10.1145\/502090.502091","volume":"48","author":"A Darwiche","year":"2001","unstructured":"Darwiche, A.: Decomposable negation normal form. J. ACM 48, 608\u2013647 (2001)","journal-title":"J. ACM"},{"key":"13_CR7","doi-asserted-by":"crossref","first-page":"11","DOI":"10.3166\/jancl.11.11-34","volume":"11","author":"A Darwiche","year":"2001","unstructured":"Darwiche, A.: On the tractable counting of theory models and its application to truth maintenance and belief revision. J. Appl. Non-Class. Logics 11, 11\u201334 (2001)","journal-title":"J. Appl. Non-Class. Logics"},{"key":"13_CR8","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1613\/jair.989","volume":"17","author":"A Darwiche","year":"2002","unstructured":"Darwiche, A., Marquis, P.: A knowledge compilation map. J. Artifi. Intell. Res. 17, 229\u2013264 (2002)","journal-title":"J. Artifi. Intell. Res."},{"key":"13_CR9","unstructured":"Darwiche, A., Huang, J.: Testing equivalence probabilistically. Technical report D-123 Computer Science Department, UCLA (2002)"},{"key":"13_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1007\/3-540-08860-1_17","volume-title":"Automata, Languages and Programming","author":"S Fortune","year":"1978","unstructured":"Fortune, S., Hopcroft, J., Schmidt, E.M.: The complexity of equivalence and containment for free single variable program schemes. In: Ausiello, G., B\u00f6hm, C. (eds.) ICALP 1978. LNCS, vol. 62, pp. 227\u2013240. Springer, Heidelberg (1978). doi: 10.1007\/3-540-08860-1_17"},{"key":"13_CR11","doi-asserted-by":"crossref","unstructured":"Grigoriev, D., Karpinski, M.: The matching problem for bipartite graphs with polynomially bounded permanents is in NC. In: 28th Annual Symposium on Foundations of Computer Science (FOCS), pp. 166\u2013172 (1987)","DOI":"10.1109\/SFCS.1987.56"},{"key":"13_CR12","doi-asserted-by":"crossref","first-page":"985","DOI":"10.1002\/j.1538-7305.1959.tb01585.x","volume":"38","author":"CY Lee","year":"1959","unstructured":"Lee, C.Y.: Representation of switching circuits by binary-decision programs. Bell Syst. Tech. J. 38, 985\u2013999 (1959)","journal-title":"Bell Syst. Tech. J."},{"key":"13_CR13","unstructured":"Masek, W.J.: A fast algorithm for the string editing problem and decision graph complexity. M.Sc. thesis, MIT, Cambridge MA (1976)"},{"key":"13_CR14","volume-title":"Modified Branching Programs and Their Computational Power","author":"C Meinel","year":"1989","unstructured":"Meinel, C.: Modified Branching Programs and Their Computational Power. LNCS, vol. 370. Springer, Heidelberg (1989)"},{"key":"13_CR15","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/BF02579206","volume":"7","author":"K Mulmuley","year":"1987","unstructured":"Mulmuley, K., Vazirani, U.V., Vazirani, V.V.: Matching is as easy as matrix inversion. Combinatorica 7, 105\u2013113 (1987)","journal-title":"Combinatorica"},{"key":"13_CR16","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-60322-8","volume-title":"Gems of Theoretical Computer Science","author":"U Sch\u00f6ning","year":"1998","unstructured":"Sch\u00f6ning, U., Pruim, R.: Gems of Theoretical Computer Science. Springer, Heidelberg (1998)"},{"key":"13_CR17","doi-asserted-by":"crossref","first-page":"701","DOI":"10.1145\/322217.322225","volume":"27","author":"T Jacob","year":"1980","unstructured":"Jacob, T.: Schwartz: fast probabilistic algorithms for verification of polynomial identities. J. ACM 27, 701\u2013717 (1980)","journal-title":"J. ACM"},{"key":"13_CR18","volume-title":"Introduction to the Theory of Computation","author":"M Sipser","year":"1997","unstructured":"Sipser, M.: Introduction to the Theory of Computation. PWS Publishing Company, Boston (1997)"},{"key":"13_CR19","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898719789","volume-title":"Branching Programs and Binary Decision Diagrams","author":"I Wegener","year":"2000","unstructured":"Wegener, I.: Branching Programs and Binary Decision Diagrams. SIAM, Philadelphia (2000)"},{"key":"13_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1007\/3-540-09519-5_73","volume-title":"Symbolic and Algebraic Computation","author":"R Zippel","year":"1979","unstructured":"Zippel, R.: Probabilistic algorithms for sparse polynomials. In: Ng, E.W. (ed.) Symbolic and Algebraic Computation. LNCS, vol. 72, pp. 216\u2013226. Springer, Heidelberg (1979). doi: 10.1007\/3-540-09519-5_73"}],"container-title":["Lecture Notes in Computer Science","Unveiling Dynamics and Complexity"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-58741-7_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,24]],"date-time":"2019-09-24T08:47:05Z","timestamp":1569314825000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-58741-7_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319587400","9783319587417"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-58741-7_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]}}}