- 1 ABRAMOWITZ, M., AND STEGUN, I A Handbook ofMathematlcal Functzons. Nat. Bur Stand., Washmgton, DC., 1964, chap 15Google Scholar
- 2 AHO, A V, HOPCROFT, J E, AND ULLMAN, J.D The Design and Analysts of Computer Algorithms Addison- Wesley, Reading, Mass, 1974. Google Scholar
- 3 BACHMAN, G Introduction to P-Adlc Numbers and Valuation Theory Academic Press, New York, 1964Google Scholar
- 4 BORODIN, A. On the number of anthmetlcs to compute certain funcuons--Clrca May 1973. In Complemty of Sequenoal and Parallel Numerical Algorithms, J F Traub, Ed, Academic Press, New York, 1973, pp 149-180.Google Scholar
- 5 BORODIN, A, AND MUNRO, l The Computatlonal Complemty of Algebraic and Numeric Problems American Elsevier, New York, 1975Google Scholar
- 6 BURKtLL, j C The Theory of Ordmary Differential Equations Oliver and Boyd, London, 1962, Sec. 9.Google Scholar
- 7 BRENT, R P The complexity of multlple-precmlon anthmeuc. In Complexity of Computational Problem Solving, R S Anderssen & R P Brent, Eds, U of Queensland Press, Brisbane, Austraha, 1975, pp. 126-165Google Scholar
- 8 BRENT, R P Multiple-precision zero-finding methods and the complexity of elementary function evaluation In Analytic Computational Complexity, j F Traub, Ed., Academic Press, New York, 1975, pp. 151-176Google Scholar
- 9 BRENT, R P, AND KUNO, H T. O((n log n)3/2) algorithms for composmon and reversion of power series (extended abstrac0 In Analytic Computational Complemty, j F. Traub, Ed, Academic Press, New York, 1976, pp 217-225Google Scholar
- 10 BRENT, R P, AND KUNO, H.T. Fast algorithms for composiuon and reversion of multivariate power series Proc. Conf. Theoret Comptr Sct, U. of Waterloo, Waterloo, Ont., Canada, Aug 1977, pp 149-158Google Scholar
- 11 BROCKWELL, P J The transient behaviour of the queuemg system GI/M/1 J Austral Math Soc 3 (1963), 249-256Google Scholar
- 12 CHRYSTAL, G. Textbook of Algebra, Part H Chelsea, New York, 1964Google Scholar
- 13 FATEMAN, R J Polynomial multiplication, powers and asymptotic analysis Some comments SIAM J Comptng 3 (1974), 196-213Google Scholar
- 14 FERGUSON, H R P, NIELSEN, D E, AND COOK, G A partition formula for the integer coefficients of the theta funcuon home Math Comput 29 (1975), 851-855Google Scholar
- 15 FINCH, P D The single server queuemg system with non-recurrent input-process and Erlang service time J Austral Math Soc 3 (1963), 220-236Google Scholar
- 16 FINCH, P D On partial sums of Lagrange's series with application to theory of queues J Austral Math Soc 3 (1963), 488-490Google Scholar
- 17 FISCHER, M J, AND STOCKMEYER, L J Fast on-hne integer multiplication J Comptr Syst Sci 9 (1974). 317-331Google Scholar
- 18 GILBERT, E N Enumeration of labelled graphs Canadian J Math 8 (1956), 405-411Google Scholar
- 19 HEINDEL, L E Computation of powers of multivariate polynomials over the integers J Comptr Syst Scl 6 (1971), 1-8Google Scholar
- 20 HENRtCI, P Automatic computation with power series J ACM 3, 1 (Jan 1956), 10-15 Google Scholar
- 21 HENPaCi, P Apphed and Computational Complex Analysis, Vol 1 Wdey-lnterscience, New York, 1974, chap 1.Google Scholar
- 22 HOPCROFT, J E Complexity of computer computations Information Processing 74, North-Holland Pub Co, Amsterdam, 1974, pp 620--626.Google Scholar
- 23 HOROWITZ, E On the substitution of polynomial forms Proc ACM 1973 Annual Conf, CR No 28686, 1973, pp 153-158 Google Scholar
- 24 HogowlTz, E The efficient calculation of powers of polynomials J Comptr Syst Scz 7 (1973), 469-480Google Scholar
- 25 JACKSON, D M, AND REILLY, J W The enumeration of homeomorphically irreducible labelled graphs J Combinatorial Theory, Set B, 19 (1975), 272-286Google Scholar
- 26 KNUTW, D E The Art of Computer Programming, Vol 2 Semmumerlcal Algorithms Addison-Wesley, Reading, Mass, 1969, Sec 4 7 Google Scholar
- 27 KUNG, H T On computing reciprocals of power series Numer Math 22 (1974), 341-348Google Scholar
- 28 KUNG, H.T, AND TRAUB, J F Computational complexity of one-point and multipomt iteration. In Complexity of Real Computation, R M Karp, Ed, SIAM-AMS Proc 7, Amer Math Soc, Providence, R I, 1974, pp 149-160Google Scholar
- 29 KUNG, H T. AND TRAUB, J F All algebraic functions can be computed fast J ACM 25, 2 (April 1978), 245-260 Google Scholar
- 30 LEVY, H, AND LESSMAN, F Finite Dtfference Equattons Pitman and Sons, London, 1959.Google Scholar
- 31 NIvEN, 1 Formal power series Amer Math Monthly 76 (1969), 871-889.Google Scholar
- 32 NORMAN, A C Computmg with formal power series A CM Trans Math Software 1, 4 (Dec. 1975), 346-356 Google Scholar
- 33 PATERSON, M S, AND STOCKMEYER, L J On the number of nonscalar multlphcatlons necessary to evaluate polynomials SIAM J Comptng 2 (1973), 60-66Google Scholar
- 34 RAt.L, L B Computattonal Solution of Nonhnear Operator Equattons Wiley, New York, 1969Google Scholar
- 35 RIORDAN, J An Introductton to Combinatorial Analysts Wiley, New York, 1958Google Scholar
- 36 SIEVEKING, M An algorithm for division of power series Computing 10 (1972), 153-156Google Scholar
- 37 STRASSEN, V Gaussian ehmmatlon is not optimal Numer Math 13 (1969), 354-356Google Scholar
- 38 TRAUB, J F Iteratlve Methods for the Solutton of Equattons Prentice-Hall, Englewood Chffs, N J, 1964, chap 5Google Scholar
Index Terms
- Fast Algorithms for Manipulating Formal Power Series
Recommendations
Formal Power Series
We present a formalization of the topological ring of formal power series in Isabelle/HOL. We also formalize formal derivatives, division, radicals, composition and reverses. As an application, we show how formal elementary and hyper-geometric series ...
On transformations of formal power series
Formal power series are an extension of formal languages. Recognizable formal power series can be captured by the so-called weighted finite automata, generalizing finite state machines. In this paper, motivated by codings of formal languages, we ...
Rational Transformations of Formal Power Series
ICALP '01: Proceedings of the 28th International Colloquium on Automata, Languages and Programming,Formal power series are an extension of formal languages. Recognizable formal power series can be captured by the so-called weighted finite automata, generalizing finite state machines. In this paper, motivated by codings of formal languages, we ...
Comments