{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,29]],"date-time":"2026-01-29T11:58:08Z","timestamp":1769687888808,"version":"3.49.0"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1996,1,1]],"date-time":"1996-01-01T00:00:00Z","timestamp":820454400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["AAECC"],"published-print":{"date-parts":[[1996,1]]},"DOI":"10.1007\/bf01613615","type":"journal-article","created":{"date-parts":[[2005,4,30]],"date-time":"2005-04-30T13:15:17Z","timestamp":1114866917000},"page":"41-51","source":"Crossref","is-referenced-by-count":10,"title":["Lower bounds for arithmetic networks II: Sum of Betti numbers"],"prefix":"10.1007","volume":"7","author":[{"given":"J. L.","family":"Monta\u00f1a","sequence":"first","affiliation":[]},{"given":"J. E.","family":"Morais","sequence":"additional","affiliation":[]},{"given":"Luis M.","family":"Pardo","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","unstructured":"Ben-Or. M.: Lower bound for algebraic computation trees. A.C.M. 15 th Symposium on Theory of Computation, 80\u201386 (1983)","DOI":"10.1145\/800061.808735"},{"key":"CR2","doi-asserted-by":"crossref","unstructured":"Bj\u00f6rner, A., Lov\u00e1sz, L.: Linear decision trees, subspace arrangements and M\u00f6bis function. Preprint (1992)","DOI":"10.1145\/129712.129730"},{"key":"CR3","doi-asserted-by":"crossref","unstructured":"Bj\u00f6rner, A., Lov\u00e1sz, L., Yao, A.: Linear decision trees: volume estimates and topological bounds. In: Proc. A.C.M. 24 th Symposium on Theory of Computing, 170\u2013177 (1992)","DOI":"10.1145\/129712.129730"},{"issue":"1","key":"CR4","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1090\/S0273-0979-1989-15750-9","volume":"21","author":"L. Blum","year":"1989","unstructured":"Blum, L., Shub, M., Smale, S.: On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines. Bulletin A.M.S.21(1), 1\u201346 (1989)","journal-title":"Bulletin A.M.S."},{"key":"CR5","volume-title":"Ergebnisse der Math., 3. Folge, Band12","author":"J. Bochnack","year":"1987","unstructured":"Bochnack, J., Cost, M., Roy, M-F: G\u00e9om\u00e9trie alg\u00e9brique r\u00e9elle. Ergebnisse der Math., 3. Folge, Band12, Berlin, Heidelberg, New York: Springer (1987)"},{"key":"CR6","unstructured":"Cucker, F.:P\u211d\u2260NC\u211d. To appear in: J. of Complexity"},{"issue":"4","key":"CR7","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1142\/S0218196792000244","volume":"2","author":"F. Cucker","year":"1992","unstructured":"Cucker, F., Montana, J.L., Pardo, L.M.: Time Bounded Computations over the reals. Int. J. Alg. Comp.2(4), 395\u2013408 (1992)","journal-title":"Int. J. Alg. Comp."},{"key":"CR8","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1016\/0022-0000(79)90054-0","volume":"18","author":"O.P. Dobkin","year":"1979","unstructured":"Dobkin, O.P., Lipton, R.J.: On the complexity of computations under varying sets of primitives. J. Comp. Syst. Sci.18, 86\u201391 (1979)","journal-title":"J. Comp. Syst. Sci."},{"key":"CR9","doi-asserted-by":"crossref","unstructured":"Von, J., zur Gathen: Parallel arithmetic computations: a survey. In: Math. Found comput. Sci. 13 th Proc. (1986)","DOI":"10.1007\/BFb0016236"},{"key":"CR10","unstructured":"Fitchas, N., Galligo, A., Morgenstern, J.: Algorithmes rapides en s\u00e9quentiel et en parall\u00e8le pour l'\u00e9limination de quantificateurs en g\u00e9om\u00e9trie \u00e9l\u00e9mentair. Seminaire de Structures Algebriques Ordennes, Universit\u00e9 de Paris VII (1987)"},{"key":"CR11","unstructured":"Greenberg, M.J., Harper, J.R.: Algebraic Topology: A first course. Mathematics lecture note series 58. The Benjamin\/Cummings Publishing Company, (1981)"},{"key":"CR12","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1016\/S0747-7171(88)80006-3","volume":"5","author":"D. Grigorev","year":"1988","unstructured":"Grigorev, D.: Complexity of deciding Tarski algebra. J. Symb. Comp.5, 65\u2013108 (1988)","journal-title":"J. Symb. Comp"},{"key":"CR13","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1016\/0304-3975(83)90002-6","volume":"24","author":"J. Heintz","year":"1983","unstructured":"Heintz, J.: Definability and fast quantifier elimination over algebraically closed fields. Theor. Comp. Sci.24, 239\u2013278 (1983)","journal-title":"Theor. Comp. Sci."},{"key":"CR14","doi-asserted-by":"crossref","first-page":"101","DOI":"10.24033\/bsmf.2138","volume":"118","author":"J. Heintz","year":"1990","unstructured":"Heintz, J., Roy, M.-F., Solern\u00f3, P.: Sur la Complexit\u00e9 du Principe de Tarski-Seidenbrg. Bull. Soc. Math. France118, 101\u2013126 (1990)","journal-title":"Bull. Soc. Math. France"},{"key":"CR15","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1090\/S0002-9939-1964-0161339-9","volume":"15","author":"J. Milnor","year":"1964","unstructured":"Milnor, J.: On the Betti numbers of real varieties. Proc. Am. Math. Soc.15, 275\u2013280 (1964)","journal-title":"Proc. Am. Math. Soc."},{"key":"CR16","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF01270397","volume":"4","author":"J.L. Monta\u00f1a","year":"1993","unstructured":"Monta\u00f1a, J.L., Pardo, L.M.: Lower bounds for Arithmetic Networks. AAECC4, 1\u201324 (1993)","journal-title":"AAECC"},{"key":"CR17","unstructured":"Monta\u00f1a, J.L., Luis M. Pardo y T. Recio: The Non-Scalar Model of Complexity in Computational Semialgebraic Geometry. In: Proc MEGA'90, Progress in Mathematics vol 94, Birkh\u00e4user, 346\u2013362 (1991)"},{"key":"CR18","volume-title":"Texts and Monographs in Computer Science","author":"F.P. Preparata","year":"1985","unstructured":"Preparata, F.P., Shamos, M.I.: Computational Geometry, An Introduction. Texts and Monographs in Computer Science. Berlin, Heidelberg, New York: Springer (1985)"},{"key":"CR19","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1016\/0885-064X(87)90021-5","volume":"3","author":"S. Smale","year":"1987","unstructured":"Smale, S.: On the topology of Algorithms, I. J Complexity3, 81\u201389 (1987)","journal-title":"J Complexity"},{"key":"CR20","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0196-6774(82)90002-5","volume":"3","author":"M. Steele","year":"1982","unstructured":"Steele, M., Yao, A.: Lower bounds for Algebraic Decision Trees. J. Algorithms3, 1\u20138 (1982)","journal-title":"J. Algorithms"},{"key":"CR21","doi-asserted-by":"crossref","unstructured":"Yao, A.: Algebraic Decision trees and Euler characteristics. Proceedings of 33rd Annual IEEE on Foundations of Computer Science, 268\u2013277 (1992)","DOI":"10.1109\/SFCS.1992.267765"},{"key":"CR22","doi-asserted-by":"crossref","unstructured":"Yao, A.C.C.: Decision trees and Betti Numbers. To appear in Proc. STOCS'94 (1994)","DOI":"10.1145\/195058.195414"},{"key":"CR23","first-page":"343","volume-title":"Handbook of Theoretical Computer Science","author":"F.F. Yao","year":"1990","unstructured":"Yao, F.F.: Computational Geometry. In: Handbook of Theoretical Computer Science. J. van Leeuwen, ed., Elsevier, Amsterdam 343\u2013391 (1990)"}],"container-title":["Applicable Algebra in Engineering, Communication and Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01613615.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01613615\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01613615","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:51:25Z","timestamp":1735692685000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01613615"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,1]]},"references-count":23,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1996,1]]}},"alternative-id":["BF01613615"],"URL":"https:\/\/doi.org\/10.1007\/bf01613615","relation":{},"ISSN":["0938-1279","1432-0622"],"issn-type":[{"value":"0938-1279","type":"print"},{"value":"1432-0622","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996,1]]}}}