{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:56:59Z","timestamp":1760245019688},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1993,3,1]],"date-time":"1993-03-01T00:00:00Z","timestamp":730944000000},"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":[[1993,3]]},"DOI":"10.1007\/bf01270397","type":"journal-article","created":{"date-parts":[[2005,3,24]],"date-time":"2005-03-24T04:36:14Z","timestamp":1111638974000},"page":"1-24","source":"Crossref","is-referenced-by-count":30,"title":["Lower bounds for arithmetic networks"],"prefix":"10.1007","volume":"4","author":[{"given":"J. L.","family":"Monta\ufffda","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"L. M.","family":"Pardo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"CR1","volume-title":"The Design and Analysis of Computer Algorithms","author":"A. Aho","year":"1976","unstructured":"Aho, A., Hopcroft, J., Ullman J.: The Design and Analysis of Computer Algorithms. Toronto: Addison-Wesley 1976"},{"key":"CR2","doi-asserted-by":"crossref","unstructured":"Ben-Or, M.: Lower bounds for algebraic computation trees. A.C.M. 15th Symp Theory Comput., pp. 80?86 (1983)","DOI":"10.1145\/800061.808735"},{"key":"CR3","volume-title":"Real algebraic and semialgebraic sets","author":"R. Benedetti","year":"1990","unstructured":"Benedetti, R., Risler, J. J.: Real algebraic and semialgebraic sets. Paris: Hermann 1990"},{"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. Bull. Am. Math. Soc.21(1), 1?46 (1989)","journal-title":"Bull. Am. Math. Soc."},{"key":"CR5","volume-title":"G\u00e9om\u00e9trie alg\u00e9brique r\u00e9elle. Ergebnisse der Math., 3. Folge, Bd. 12","author":"J. Bochnak","year":"1987","unstructured":"Bochnak, J., Coste, M., Roy, M.-F.: G\u00e9om\u00e9trie alg\u00e9brique r\u00e9elle. Ergebnisse der Math., 3. Folge, Bd. 12. Berlin Heidelberg New York: Springer 1987"},{"key":"CR6","unstructured":"Cucker, F.: ?P ? ?NC ??. To appear in J. of Complexity"},{"key":"CR7","unstructured":"Cucker, F., Monta\u00f1a, J. L., Pardo, L. M.: Time Bounded Computations over the Reals. To appear in Int. J. Algebra Comp."},{"key":"CR8","doi-asserted-by":"crossref","unstructured":"Cucker, F., Torrecillas, A.: Two P-complete problems in the theory of the reals. To appear in Proceedings of ICALP '91, Madrid, 1991","DOI":"10.1007\/3-540-54233-7_163"},{"key":"CR9","first-page":"29","volume-title":"J. Symb Comput. Soc.5","author":"J. H. Davenport","year":"1988","unstructured":"Davenport, J. H., Heintz, J.: Real quantifier elimination is doubly exponential. J. Symb Comput. Soc.5, 29?36, New York: Academic Press 1988"},{"key":"CR10","first-page":"86","volume":"18","author":"D. P. Dobkin","year":"1976","unstructured":"Dobkin, D. P., Lipton, R. J.: A lower bound of 1\/2n 2 on linear search programs for solving the Knapsack problem. JCSS18, 86?91 (1976)","journal-title":"JCSS"},{"key":"CR11","unstructured":"Fitchas, N., Galligo, A., Morgenstern, A.: Algorithmes rapides en s\u00e9quentiel et en parallele pour l'\u00e9limination de quantificateurs en g\u00e9om\u00e9trie \u00e9l\u00e9mentaire. Seminaire de Structures Algebriques Ordennes, Universite de Paris VII, 1987"},{"key":"CR12","doi-asserted-by":"crossref","unstructured":"Von zur Gathen, J.: Parallel arithmetic computations: a survey. Mathematical Foundations on computer Science, 13th Proc. MFCS, 1986","DOI":"10.1007\/BFb0016236"},{"key":"CR13","doi-asserted-by":"crossref","unstructured":"Von zur Gathen, J.: Algebraic Complexity Theory. Technical Report of the Department of Computer Science. University of Toronto, 1988","DOI":"10.1146\/annurev.cs.03.060188.001533"},{"key":"CR14","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1016\/S0747-7171(88)80006-3","volume":"5","author":"D. Grigor'ev","year":"1988","unstructured":"Grigor'ev, D.: Complexity of deciding Tarski algebra. J. Symb. Comp.5, 65?108 (1988)","journal-title":"J. Symb. Comp."},{"key":"CR15","doi-asserted-by":"crossref","first-page":"1388","DOI":"10.1007\/BF02104745","volume":"4","author":"D. Grigorev","year":"1985","unstructured":"Grigorev, D.: Lower bounds in algebraic computational complexity. J. Sov. Math.,4, 1388?1425 (1985)","journal-title":"J. Sov. Math."},{"key":"CR16","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?278 (1983). CORRIGENDUM in Theor. Comp. Science39, 343 (1985)","journal-title":"Theor. Comp. Sci."},{"key":"CR17","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., Solerno, P.: Sur la Complexit\u00e9 du Principe de Tarski-Seidenberg. Bull. Soc. Math. France118, 101?126 (1990)","journal-title":"Bull. Soc. Math. France"},{"key":"CR18","doi-asserted-by":"crossref","first-page":"534","DOI":"10.1145\/321958.321973","volume":"23","author":"H. T. Kung","year":"1976","unstructured":"Kung, H. T.: New algorithms and lower bounds for the parallel evaluation of certain rational expressions and recurrences. J. ACM23, 534?543 (1976)","journal-title":"J. ACM"},{"key":"CR19","first-page":"1","volume-title":"Symp. Theor. Aspects Comp. LNCS349","author":"F. Meyer auf der Heide","year":"1989","unstructured":"Meyer auf der Heide F.: On genuinely time bounded computations. Symp. Theor. Aspects Comp. LNCS349, 1?16, Berlin Heidelberg New York: Springer 1989"},{"issue":"3","key":"CR20","doi-asserted-by":"crossref","first-page":"668","DOI":"10.1145\/828.322450","volume":"31","author":"F. Meyer auf der Heide","year":"1984","unstructured":"Meyer auf der Heide, F.: A Polynomial Linear Search Algorithm for then-dimensional Knapsack Problem. J. ACM,31(3), 668?676 (1984)","journal-title":"J. ACM"},{"key":"CR21","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 algebraic varieties. Proc. AMS15, 275?280 (1964)","journal-title":"Proc. AMS"},{"key":"CR22","first-page":"347","volume":"94","author":"J. L. Monta\u00f1a","year":"1991","unstructured":"Monta\u00f1a, J. L., Pardo, L. M., Recio, T.: The non-scalar model of complexity in computational geometry. Proc. of MEGA '90, Progress in Math. 94. Basel Birkh\u00e4user, pp. 347?362 (1991)","journal-title":"Proc. of MEGA '90, Progress in Math"},{"key":"CR23","unstructured":"Monta\u00f1a, J. L.: Cotas inferiores en teor\u00eda de la complejidad algebraica. Doctoral Thesis. Universidad de Cantabria, 1992"},{"key":"CR24","unstructured":"Pardo, L. M., Recio, T.: Arboles algebraicos: un modelo de computaci\u00f3n en geometria. Contribuciones Cientificas, pp. 241?248, Universidad de Cantabria, 1988"},{"key":"CR25","doi-asserted-by":"crossref","first-page":"639","DOI":"10.1016\/S0022-0000(72)80034-5","volume":"6","author":"M. Rabin","year":"1972","unstructured":"Rabin, M.: Proving simultaneous positivity of linear forms. J. Comp. Syst. Sci.,6, 639?650 (1972)","journal-title":"J. Comp. Syst. Sci."},{"key":"CR26","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. Complexity,3, 81?89 (1987)","journal-title":"J. Complexity"},{"key":"CR27","first-page":"634","volume":"11","author":"V. Strassen","year":"1990","unstructured":"Strassen, V.: Algebraic Complexity Theory. Hand Book of Theoretical Computer Science, capitulo11, 634?671 (1990)","journal-title":"Hand Book of Theoretical Computer Science, capitulo"}],"container-title":["Applicable Algebra in Engineering, Communication and Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01270397.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01270397\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01270397","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,6]],"date-time":"2020-04-06T12:56:05Z","timestamp":1586177765000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01270397"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993,3]]},"references-count":27,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1993,3]]}},"alternative-id":["BF01270397"],"URL":"https:\/\/doi.org\/10.1007\/bf01270397","relation":{},"ISSN":["0938-1279","1432-0622"],"issn-type":[{"type":"print","value":"0938-1279"},{"type":"electronic","value":"1432-0622"}],"subject":[],"published":{"date-parts":[[1993,3]]}}}