Loading...
Please wait, while we are loading the content...
Similar Documents
Flashing Lcmmas on Time Complexities with Applications to Formula Manipulation at !* L+
| Content Provider | Semantic Scholar |
|---|---|
| Author | Goro, Et Rclrr Fntroduction, I. |
| Abstract | Johnson[]-l and Horowitzt2l applied sorting to improve time compJ.exity of multiplication of uni-variate polynomials. Their results may be regarded as applications of the following LEMMA: Sorting LEI'IMA. xhe Xine complexitg of sorting of N items js O(N7og2N) and that of binarg search of sorted N items is O(7og2N). In this paper, time complexit,Les of operation on "sets" and "ordered n-tuples" based on a hashing table search technique are presented as .'Etashing LEll 4tIAs" and are applied to formula manipulation. Unique normal forms for multivariatre slnrbolic formulas resulting in O(7) time eomplexity for ictentity checks are presented. llhe logarithmic factor j.ogzV, characteristic to sorting algorithns, is shown ts all disappear from time complexitl"es of polynonial manipula-uions. Actual implementation of the hashing technique is outlined and actual timing data are presented in the appendix. II-Hashing LEMMAS on Sets and n-Tuptes. (2.0) Denotations and Conventions: In case x represents a set or an n-tuple. lxl means the n'.unber of elements. Sets are denoted by underscored capitaL letter(s). Specially , INT is the set of (a11) integers; rNfo = INT-{Oi, i.e., integers except o; INT+ is the set of positive integers. A BNf' metaobject is denoted by embracketing a set j.n the underscoring notation between *<,. and .)'., with o.otional conrnentary r:n-underscored letters. ?his convention enables us to use both BNF and set notations. 8.9., BIT = {O,f} and (Binary diglT> ::= 011 o are equivaleiE-definitions, wfure ,,o" mEans the end of a BNF definition. In order to present algorithrns precisely and concisely, Lisp with three additional data types (ordered n-TUPle>, and .s are assumed Eo be o(L) for the sake of simpllEity. / ;;Dl. fcogssal@gy of the 1975 ACI+I Symposium oa Svnholic aad Algebraic Compuraion While 's'are denoted as :.: (.)o, 's .iE-'s are d.enoted li-accordance with ordinary mathematical notations : r:= ((,p),ooolor ::= {,ooo}o, t{here "rooo" means nonzero repetition of the satne metaobject. Specially the O-tuple O anit the nul1 set {} are regarded equivalent to NIL, i.e., … |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www.cs.utexas.edu/~hunt/research/hash-cons/hash-cons-papers/hashing-lemmas-goto-kanada.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
