{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,2]],"date-time":"2022-04-02T06:29:04Z","timestamp":1648880944448},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2015,12,26]],"date-time":"2015-12-26T00:00:00Z","timestamp":1451088000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2017,8]]},"DOI":"10.1007\/s00224-015-9666-9","type":"journal-article","created":{"date-parts":[[2015,12,26]],"date-time":"2015-12-26T02:30:54Z","timestamp":1451097054000},"page":"322-351","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Processing Succinct Matrices and Vectors"],"prefix":"10.1007","volume":"61","author":[{"given":"Markus","family":"Lohrey","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Manfred","family":"Schmidt-Schau\u00df","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,12,26]]},"reference":[{"key":"9666_CR1","doi-asserted-by":"crossref","unstructured":"Allender, E., Balaji, N., Datta, S.: Low-depth uniform threshold circuits and the bit-complexity of straight line programs. In: Proceedings of MFCS 2014, LNCS 8635, pp 13\u201324. Springer, Berlin Heidelberg New York (2014)","DOI":"10.1007\/978-3-662-44465-8_2"},{"key":"9666_CR2","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/0304-3975(93)90252-O","volume":"107","author":"C \u00c0lvarez","year":"1993","unstructured":"\u00c0lvarez, C., Jenner, B.: A very hard log-space counting class. Theor. Comput. Sci. 107, 3\u201330 (1993)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"9666_CR3","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1007\/s00037-007-0222-0","volume":"16","author":"M Beaudry","year":"2007","unstructured":"Beaudry, M., Holzer, M.: The complexity of tensor circuit evaluation. Comput. Complex. 16(1), 60\u2013111 (2007)","journal-title":"Comput. Complex."},{"key":"9666_CR4","doi-asserted-by":"crossref","first-page":"332","DOI":"10.1006\/jcss.2002.1852","volume":"65","author":"P Berman","year":"2002","unstructured":"Berman, P., Karpinski, M., Larmore, L.L., Plandowski, W., Rytter, W.: On the complexity of pattern matching for highly compressed two-dimensional texts. J. Comput. Syst. Sci. 65, 332\u2013350 (2002)","journal-title":"J. Comput. Syst. Sci."},{"key":"9666_CR5","doi-asserted-by":"crossref","unstructured":"Bertoni, A., Choffrut, C., Radicioni, R.: Literal shuffle of compressed words. In: Proceedings of IFIP TCS 2008, volume 273 of IFIP, pp 87\u2013100. Springer, Berlin Heidelberg New York (2008)","DOI":"10.1007\/978-0-387-09680-3_6"},{"key":"9666_CR6","doi-asserted-by":"crossref","first-page":"641","DOI":"10.1007\/s00224-004-1133-y","volume":"37","author":"A Blumensath","year":"2004","unstructured":"Blumensath, A., Gr\u00e4del, E.: Finite presentations of infinite structures: automata and interpretations. Theor. Comput. Syst. 37, 641\u2013674 (2004)","journal-title":"Theor. Comput. Syst."},{"issue":"8","key":"9666_CR7","doi-asserted-by":"crossref","first-page":"677","DOI":"10.1109\/TC.1986.1676819","volume":"35","author":"RE Bryant","year":"1986","unstructured":"Bryant, R.E.: Graph-based algorithms for boolean function manipulation. IEEE Trans. Comput. 35(8), 677\u2013691 (1986)","journal-title":"IEEE Trans. Comput."},{"issue":"2","key":"9666_CR8","doi-asserted-by":"crossref","first-page":"200","DOI":"10.1006\/jcss.1998.1588","volume":"57","author":"H Caussinus","year":"1998","unstructured":"Caussinus, H., McKenzie, P., Th\u00e9rien, D., Vollmer, H.: Nondeterministic NC1 computation. J. Comput. Syst. Sci. 57(2), 200\u2013212 (1998)","journal-title":"J. Comput. Syst. Sci."},{"key":"9666_CR9","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1016\/S0019-9958(85)80041-3","volume":"64","author":"SA Cook","year":"1985","unstructured":"Cook, S.A.: A taxonomy of problems with fast parallel algorithms. Inf. Control. 64, 2\u201322 (1985)","journal-title":"Inf. Control."},{"issue":"1\u20132","key":"9666_CR10","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1007\/s00037-000-0170-4","volume":"11","author":"C Damm","year":"2002","unstructured":"Damm, C., Holzer, M., McKenzie, P.: The complexity of tensor calculus. Comput. Complex. 11(1\u20132), 54\u201389 (2002)","journal-title":"Comput. Complex."},{"key":"9666_CR11","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1142\/S0218195908002568","volume":"18","author":"D Eppstein","year":"2008","unstructured":"Eppstein, D., Goodrich, M.T., Sun, J.Z.: Skip quadtrees: dynamic data structures for multidimensional point sets. Int. J. Comput. Geom. Appl. 18, 131\u2013160 (2008)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"9666_CR12","doi-asserted-by":"crossref","unstructured":"Feigenbaum, J., Kannan, S., Vardi, M.Y., Viswanathan, M.: The complexity of problems on graphs represented as obdds Chicago Journal of Theoretical Computer Science (1999)","DOI":"10.4086\/cjtcs.1999.005"},{"key":"9666_CR13","doi-asserted-by":"crossref","unstructured":"Fujii, H., Ootomo, G., Hori, C.: Interleaving based variable ordering methods for ordered binary decision diagrams. IEEE Computer Society, pp 38\u201341 (1993)","DOI":"10.1109\/ICCAD.1993.580028"},{"issue":"2\/3","key":"9666_CR14","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1023\/A:1008647823331","volume":"10","author":"M Fujita","year":"1997","unstructured":"Fujita, M., McGeer, P.C., Yang, J.C.-Y.: Multi-terminal binary decision diagrams: an efficient data structure for matrix representation. Form. Method Syst. Des. 10(2\/3), 149\u2013169 (1997)","journal-title":"Form. Method Syst. Des."},{"issue":"1","key":"9666_CR15","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1016\/j.ic.2005.02.002","volume":"198","author":"M Galota","year":"2005","unstructured":"Galota, M., Vollmer, H.: Functions computable in polynomial space. Inf. Comput. 198(1), 56\u201370 (2005)","journal-title":"Inf. Comput."},{"key":"9666_CR16","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1016\/S0019-9958(83)80004-7","volume":"56","author":"H Galperin","year":"1983","unstructured":"Galperin, H., Wigderson, A.: Succinct representations of graphs. Inf. Control. 56, 183\u2013198 (1983)","journal-title":"Inf. Control."},{"issue":"4","key":"9666_CR17","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1016\/j.ic.2010.01.002","volume":"208","author":"V Geffert","year":"2010","unstructured":"Geffert, V., Mereghetti, C., Palano, B.: More concise representation of regular languages by automata and regular expressions. Inf. Comput. 208(4), 385\u2013394 (2010)","journal-title":"Inf. Comput."},{"issue":"2","key":"9666_CR18","doi-asserted-by":"crossref","first-page":"142","DOI":"10.1016\/j.jco.2012.10.001","volume":"29","author":"B Grenet","year":"2013","unstructured":"Grenet, B., Koiran, P., Portier, N.: On the complexity of the multivariate resultant. J. Complex. 29(2), 142\u2013157 (2013)","journal-title":"J. Complex."},{"issue":"1","key":"9666_CR19","doi-asserted-by":"crossref","first-page":"23","DOI":"10.3233\/ICA-2012-0389","volume":"19","author":"M Hayashida","year":"2012","unstructured":"Hayashida, M., Ruan, P., Akutsu, T.: A quadsection algorithm for grammar-based image compression. Integr. Comput. Aided Eng. 19(1), 23\u201338 (2012)","journal-title":"Integr. Comput. Aided Eng."},{"issue":"1","key":"9666_CR20","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1145\/322358.322373","volume":"30","author":"OH Ibarra","year":"1983","unstructured":"Ibarra, O.H., Moran, S.: Probabilistic algorithms for deciding equivalence of straight-line programs. J. Assoc. Comput. Mach. 30(1), 217\u2013228 (1983)","journal-title":"J. Assoc. Comput. Mach."},{"key":"9666_CR21","unstructured":"K\u00f6nig, D., Lohrey, M.: Evaluating matrix circuits. Technical report. arXiv: 1502.03540 , to appear in Proceedings of COCOON 2015 (2015)"},{"key":"9666_CR22","doi-asserted-by":"crossref","first-page":"1087","DOI":"10.1137\/0218073","volume":"18","author":"RE Ladner","year":"1989","unstructured":"Ladner, R.E.: Polynomial space counting problems. SIAM J. Comput. 18, 1087\u20131097 (1989)","journal-title":"SIAM J. Comput."},{"key":"9666_CR23","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1016\/0022-0000(92)90004-3","volume":"44","author":"T Lengauer","year":"1992","unstructured":"Lengauer, T., Wagner, K.W.: The correlation between the complexities of the nonhierarchical and hierarchical versions of graph problems. J. Comput. Syst. Sci. 44, 63\u201393 (1992)","journal-title":"J. Comput. Syst. Sci."},{"key":"9666_CR24","doi-asserted-by":"crossref","first-page":"538","DOI":"10.1287\/moor.8.4.538","volume":"8","author":"H Lenstra","year":"1983","unstructured":"Lenstra, H.: Integer programming with a fixed number of variables. Math. Oper. Res. 8, 538\u2013548 (1983)","journal-title":"Math. Oper. Res."},{"key":"9666_CR25","doi-asserted-by":"crossref","first-page":"951","DOI":"10.1016\/j.ic.2011.01.009","volume":"209","author":"M Lohrey","year":"2011","unstructured":"Lohrey, M.: Leaf languages and string compression. Inf. Comput. 209, 951\u2013965 (2011)","journal-title":"Inf. Comput."},{"key":"9666_CR26","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1515\/gcc-2012-0016","volume":"4","author":"M Lohrey","year":"2012","unstructured":"Lohrey, M.: Algorithmics on SLP-compressed strings: a survey. Groups, Complexity, Cryptology 4, 241\u2013299 (2012)","journal-title":"Groups, Complexity, Cryptology"},{"issue":"2","key":"9666_CR27","doi-asserted-by":"crossref","first-page":"196","DOI":"10.1016\/j.tcs.2006.07.024","volume":"363","author":"M Lohrey","year":"2006","unstructured":"Lohrey, M., Maneth, S.: The complexity of tree automata and XPath on grammar-compressed trees. Theor. Comput. Sci. 363(2), 196\u2013210 (2006)","journal-title":"Theor. Comput. Sci."},{"key":"9666_CR28","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1016\/j.ic.2013.01.002","volume":"224","author":"M Lohrey","year":"2013","unstructured":"Lohrey, M., Mathissen, C.: Isomorphism of regular trees and words. Inf. Comput. 224, 71\u2013105 (2013)","journal-title":"Inf. Comput."},{"key":"9666_CR29","doi-asserted-by":"crossref","unstructured":"Malod, G.: Succinct algebraic branching programs characterizing non-uniform complexity classes. In: Proceedings of FCT 2011, LNCS 6914, pp 205\u2013216. Springer, Berlin Heidelberg New York (2011)","DOI":"10.1007\/978-3-642-22953-4_18"},{"key":"9666_CR30","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-58940-9","volume-title":"Algorithms and Data Structures in VLSI Design: OBDD - Foundations and Applications","author":"C Meinel","year":"1998","unstructured":"Meinel, C., Theobald, T.: Algorithms and Data Structures in VLSI Design: OBDD - Foundations and Applications. Springer, Berlin Heidelberg New York (1998)"},{"issue":"1","key":"9666_CR31","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1051\/ita:2000105","volume":"34","author":"C Mereghetti","year":"2000","unstructured":"Mereghetti, C., Palano, B.: Threshold circuits for iterated matrix product and powering. Informatique Th\u00e9orique et Applications 34(1), 39\u201346 (2000)","journal-title":"Informatique Th\u00e9orique et Applications"},{"key":"9666_CR32","doi-asserted-by":"crossref","unstructured":"Plandowski, W.: Testing equivalence of morphisms in context-free languages. In: Proceedings of ESA 1994, LNCS 855, pp 460\u2013470. Springer, Berlin Heidelberg New York (1994)","DOI":"10.1007\/BFb0049431"},{"key":"9666_CR33","volume-title":"The Design and Analysis of Spatial Data Structures","author":"H Samet","year":"1990","unstructured":"Samet, H.: The Design and Analysis of Spatial Data Structures. Addison-Wesley, Reading, MA (1990)"},{"key":"9666_CR34","doi-asserted-by":"crossref","unstructured":"Storjohann, A., Mulders, T.: Fast algorithms for linear algebra modulo N. In: Proceedings of ESA 1998, LNCS 1461, pp 139\u2013150. Springer, Berlin Heidelberg New York (1998)","DOI":"10.1007\/3-540-68530-8_12"},{"issue":"1","key":"9666_CR35","first-page":"201","volume":"9","author":"MA Tai\u0306clin","year":"1968","unstructured":"Tai\u0306clin, M.A.: Algorithmic problems for commutative semigroups. Dokl. Akad. Nauk SSSR 9(1), 201\u2013204 (1968)","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"9666_CR36","unstructured":"Toda, S.: Counting problems computationally equivalent to computing the determinant. Technical Report CSIM 91-07, Tokyo University of Electro-Communications (1991)"},{"key":"9666_CR37","doi-asserted-by":"crossref","first-page":"865","DOI":"10.1137\/0220053","volume":"20","author":"S Toda","year":"1991","unstructured":"Toda, S.: PP is as hard as the polynomial-time hierarchy. SIAM J. Comput. 20, 865\u2013877 (1991)","journal-title":"SIAM J. Comput."},{"key":"9666_CR38","unstructured":"Torfah, H., Zimmermann, M.: The complexity of counting models of linear-time temporal logic. In: Proceedings of FSTTCS 2014, volume 29 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, pp 241\u2013252 (2014)"},{"key":"9666_CR39","doi-asserted-by":"crossref","unstructured":"Valiant, L.G.: Completeness classes in algebra. In: Proceedings of STOC 1979, ACM, pp 249\u2013261 (1979)","DOI":"10.1145\/800135.804419"},{"key":"9666_CR40","doi-asserted-by":"crossref","unstructured":"Veith, H.: How to encode a logical structure by an OBDD. In: Proceedings of 13th Annual IEEE Conference on Computational Complexity, IEEE Computer Society, pp 122\u2013131 (1998)","DOI":"10.1109\/CCC.1998.694598"},{"issue":"11","key":"9666_CR41","doi-asserted-by":"crossref","first-page":"1262","DOI":"10.1109\/12.324559","volume":"43","author":"I Wegener","year":"1994","unstructured":"Wegener, I.: The size of reduced OBDD\u2019s and optimal read-once branching programs for almost all boolean functions. IEEE Trans. Comput. 43(11), 1262\u20131269 (1994)","journal-title":"IEEE Trans. Comput."},{"key":"9666_CR42","doi-asserted-by":"crossref","unstructured":"Weibel, C.: The K-book: an Introduction to Algebraic K-theory. Graduate Studies in Mathematics, vol. 145. AMS (2013)","DOI":"10.1090\/gsm\/145"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-015-9666-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-015-9666-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-015-9666-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-015-9666-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,2]],"date-time":"2019-09-02T23:41:55Z","timestamp":1567467715000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-015-9666-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,12,26]]},"references-count":42,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,8]]}},"alternative-id":["9666"],"URL":"https:\/\/doi.org\/10.1007\/s00224-015-9666-9","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,12,26]]}}}