{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:58:15Z","timestamp":1750309095024,"version":"3.41.0"},"reference-count":5,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[1977,8,1]],"date-time":"1977-08-01T00:00:00Z","timestamp":239241600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGSAM Bull."],"published-print":{"date-parts":[[1977,8]]},"abstract":"<jats:p>It is a well-known empirical result that differentiation, especially higher order differentiation, of simple expressions can lead to long and complex expressions. In this paper we give some theoretical results that help to explain this phenomenon. In particular we show that in certain representations there exist expressions whose representations require \u03c3(n) space but whose (k+1)-th order derivatives require \u03c3(n(n+k-1\/k)) space and hence require at least \u03c3(n(n+k-1\/k)) time to compute.<\/jats:p>","DOI":"10.1145\/1088248.1088249","type":"journal-article","created":{"date-parts":[[2007,1,17]],"date-time":"2007-01-17T18:32:02Z","timestamp":1169058722000},"page":"4-6","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["A note on the complexity of algebraic differentiation"],"prefix":"10.1145","volume":"11","author":[{"given":"B. F.","family":"Caviness","sequence":"first","affiliation":[{"name":"Rensselaer Polytechnic Institute, Troy, N.Y."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"H. I.","family":"Epstein","sequence":"additional","affiliation":[{"name":"Boston College, Chestnut Hill, Massachusetts"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[1977,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/355656.355660"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/800205.806335"},{"volume-title":"Inc.","year":"1969","author":"Boyce W. E.","key":"e_1_2_1_3_1"},{"key":"e_1_2_1_4_1","unstructured":"{EPC77} H. I. Epstein and B. F. Caviness A structure theorem for the elementary functions and its application to the identity problem International J. Computer and Info. Sciences (to appear).  {EPC77} H. I. Epstein and B. F. Caviness A structure theorem for the elementary functions and its application to the identity problem International J. Computer and Info. Sciences (to appear)."},{"key":"e_1_2_1_5_1","unstructured":"(KAP57) I. Kaplansky An Introduction to Differential Algebra Hermann Paris 1957.  (KAP57) I. Kaplansky An Introduction to Differential Algebra Hermann Paris 1957."}],"container-title":["ACM SIGSAM Bulletin"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1088248.1088249","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1088248.1088249","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T22:43:44Z","timestamp":1750286624000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1088248.1088249"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1977,8]]},"references-count":5,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1977,8]]}},"alternative-id":["10.1145\/1088248.1088249"],"URL":"https:\/\/doi.org\/10.1145\/1088248.1088249","relation":{},"ISSN":["0163-5824"],"issn-type":[{"type":"print","value":"0163-5824"}],"subject":[],"published":{"date-parts":[[1977,8]]},"assertion":[{"value":"1977-08-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}