perm filename SIX[BIB,CSR] blob sn#484141 filedate 1979-10-23 generic text, type C, neo UTF8

COMMENT ⊗ VALID 00016 PAGES C REC PAGE DESCRIPTION C00001 00001 C00003 00002 .require "setup.abs[bib,csr]" source file C00004 00003 .begin center C00007 00004 .begin nofill <<CS-760>> C00009 00005 .begin nofill <<CS-761>> C00010 00006 .begin nofill <<CS-762>> C00011 00007 .begin nofill <<CS-763>> C00012 00008 .begin nofill <<CS-764>> C00013 00009 .begin nofill <<CS-765>> C00014 00010 .begin nofill <<CS-766>> C00016 00011 .begin nofill <<CS-767>> C00017 00012 .begin nofill <<CS-768>> C00019 00013 .begin nofill <<CS-769>> C00025 00014 .begin nofill <<CS-770>> C00027 00015 .begin nofill <<cs-771>> C00032 00016 .select 4 <<order form>> C00035 ENDMK C⊗; .require "setup.abs[bib,csr]" source file; .font A "math40"; .font B "math50"; .at "⊗" ⊂"%5αQ%*"⊃ .begin center S T A N F O R D U N I V E R S I T Y MOST RECENT COMPUTER SCIENCE REPORTS - 1979 .end No. 6↔October @Listed here are abstracts of the most recent reports published by the Department of Computer Science at Stanford University. @TO REQUEST REPORTS: Check the appropriate places on the enclosed order form, and return the entire order form page (including mailing label) by December 28, 1979. In many cases we can print only a limited number of copies, and requests will be filled on a first come, first served basis. If the code (FREE) is printed on your mailing label, you will not be charged for hardcopy. This exemption from payment is limited primarily to libraries. (The costs shown include all applicable sales taxes. PLEASE SEND NO MONEY NOW, WAIT UNTIL YOU GET AN INVOICE.) @ALTERNATIVELY: Copies of most Stanford CS Reports may be obtained by writing (about 2 months after the MOST RECENT CS REPORTS listing) to NATIONAL TECHNICAL INFORMATION SERVICE, 5285 Port Royal Road, Springfield, Virginia 22161. Stanford Ph.D. theses are available from UNIVERSITY MICROFILMS, 300 North Zeeb Road, Ann Arbor, Michigan 48106. .skip .begin nofill <<CS-760>> STAN-CS-79-760 @SOME MONOTONICITY PROPERTIES OF PARTIAL ORDERS Authors: R. L. Graham, A. C. Yao, and F. F. Yao 21 pages↔Cost: $2.30 .end @A fundamental quantity which arises in the sorting of %2n%1 numbers %2a↓1,a↓2,...,a↓n%1 is %2Pr(a↓i#<#a↓j#|#P)%1, the probability that %2a↓i#<#a↓j%1 assuming that all linear extensions of the partial order %2P%1 are equally likely. In this paper we establish various properties of %2Pr(a↓i#<#a↓j#|#P)%1 and related quantities. In particular, it is shown that %2Pr(a↓i#<#b↓j#|#P')#≥#Pr(a↓i#<#b↓j#|#P)%1, if the partial order %2P%1 consists of two disjoint linearly ordered sets %2A#=#{a↓1#<#a↓2#<#...#<#a↓m} , B#=#{b↓1#<#b↓2#<#...#<#b↓n}%1 and %2P'#=#Pα∪{%1any relations of the form %2a↓k#<#b↓l}%1. The inequalities have applications in determining the complexity of certain sorting-like computations. .skip .begin nofill <<CS-761>> STAN-CS-79-761 @GOSSIPING WITHOUT DUPLICATE TRANSMISSIONS Author: Douglas B. West 7 pages↔Cost: $1.90 .end @%2n%1 people have distinct bits of information, which they communicate via telephone calls in which they transmit everything they know. We require that no one ever hear the same piece of information twice. In the case %24%1 divides %2n, n#≥#8%1, we provide a construction that transmits all information using only %29n/4-6%1 calls. Previous constructions used !! _;%2n log n%1 calls. .next page .begin nofill <<CS-762>> STAN-CS-79-762 @METAFONT: A System for Alphabet Design Author: Donald E. Knuth 107 pages↔Cost: $4.70 .end @This is the user's manual for METAFONT, a companion to the TEX typesetting system. The system makes it fairly easy to define high quality fonts of type in a machine-independent manner; a user writes "programs" in a new language developed for this purpose. By varying parameters of a design, an unlimited number of typefaces can be obtained from a single set of programs. The manual also sketches the algorithms used by the system to draw the character shapes. .skip .begin nofill <<CS-763>> STAN-CS-79-763 @A SYMMETRIC CHAIN DECOMPOSITION OF %2L(4,n)%1 Author: Douglas B. West 17 pages↔Cost: $2.20 .end @%2L(m,n)%1 is the set of integer %2m%1-tuples %2(a↓1,...,a↓m)%1 with %20#≤#a↓1#≤#...#≤#a↓m#≤#n%1, ordered by %2a#≤#b%1 when %2a↓i#≤#b↓i%1 for all %2i%1. R. Stanley conjectured that %2L(m,n)%1 is a symmetric chain order for all %2(m,n)%1. We verify this by construction for %2m#=#4%1. .skip .begin nofill <<CS-764>> STAN-CS-79-764 @ON THE TIME-SPACE TRADEOFF FOR SORTING WITH LINEAR QUERIES Author: Andrew Chi-Chih Yao 33 pages↔Cost: $2.65 .end @Extending a result of Borodin, et. al. [1], we show that any branching program using linear queries "#%A$%5l%2↓ix↓i#:#c%1#" to sort %2n%1 numbers %2x↓1,x↓2,...,x↓n%1 must satisfy the time-space tradeoff relation %2TS#=#%5W%2(n↑2)%1. The same relation is also shown to be true for branching programs that uses queries "#%2min#R#=#?%1#" where %2R%1 is any subset of %2{x↓1,x↓2,...,x↓n}%1. .skip .begin nofill <<CS-765>> STAN-CS-79-765 @RELATION BETWEEN THE COMPLEXITY AND THE PROBABILITY OF LARGE NUMBERS Author: Peter Gacs 8 pages↔Cost: $1.95 .end @%2H(x)%1, the negative logarithm of the apriori probability %2M(x)%1, is Levin's variant of Kolmogorov's complexity of a natural number %2x%1. Let %2αα(n)%1 be the minimum complexity of a number larger than %2n%1, %2s(n)%1 the logarithm of the apriori probability of obtaining a number larger than %2n%1. It was known that .skip .once center %2s(n)#≤#αα(n)#≤#s(n)#+#H(%3k%2s(n)%3l%2)%1#. We show that the second estimate is in some sense sharp. .next page .begin nofill <<CS-766>> STAN-CS-79-766↔(SU326 P3069) @EQUIDISTRIBUTING MESHES WITH CONSTRAINTS Authors: J. Kautsky and N. K. Nichols 27 pages↔Available in microfiche only. .end @Adaptive methods for selecting meshes which "equi-distribute" a given positive weight function are now used fairly widely in solving boundary value problems. The disadvantage of such schemes is that the resulting mesh may not be smoothly varying, which adversely affects accuracy and convergence properties. In this paper an adaptive technique is developed for equidistributing a function subject to constraints on the ratios of %2adjacent%1 steps in the mesh. Given a weight function %2f ≥ 0%1 on interval %2[a,b]%1 and constants %2c%1 and %2K%1, the method produces a mesh with points %2x↓0#=#a, x∪[j+1]#=#x↓j#+#h↓j, j#=#0,1,..#n-1%1 and %2x↓n#=#b%1 such that .skip .begin bf .tabs 15,20 \%2x∪[j+1] \%BI%2\f ≤ c%1 and %2l/K ≤ h∪[j+1]/h↓j ≤ K%1 for %2j = 0,1,..n-1 \x↓j%1 .end A theoretical analysis of the procedure is presented, and numerical algorithms for implementing the method are given. Applications show that the procedure is effective in practice. Other types of constraints on equidistributing meshes are also discussed. .skip .begin nofill <<CS-767>> STAN-CS-79-767 @ON STEWART'S SINGULAR VALUE DECOMPOSITION FOR PARTITIONED ORTHOGONAL @MATRICES Author: Charles Van Loan 17 pages↔Available in microfiche only. .end A variant of the singular value decomposition for orthogonal matrices due to G. W. Stewart is discussed. It is shown to be useful in the analysis of (a) the total least squares problem, (b) the Golub-Klema-Stewart subset selection algorithm, and (c) the algebraic Riccati equation. .skip .begin nofill <<CS-768>> STAN-CS-79-768 @CAUSAL NETWORKS or What Is a Deterministic Computation? Authors: Peter Gacs and Leonid A. Levin 24 pages↔Cost: $2.40 .end @We introduce the concept of casual networks which can be considered as the most general concept of the record of a computation (sequential or parallel). Causality and locality are distinguished as the only important properties of networks representing such records. Different types of complexities of computations correspond to different geometrical characteristics of the corresponding causal networks which have the advantage of being finite objects. Synchronity becomes a relative notion. Our networks can be symmetric therefore the question will make sense what can be computed from arbitrary symmetric inputs. Here we obtain a complete group-theoretical characterisation of the kind of symmetrics that can be allowed in parallel computations. .next page .begin nofill <<CS-769>> STAN-CS-79-769 @TRANSFER OF RULE-BASED EXPERTISE THROUGH A TUTORIAL DIALOGUE Author: William John Clancey↔(Thesis) 462 pages↔Available in microfiche only. .end @This dissertation describes an intelligent, computer-aided instructional (ICAI) program, named GUIDON, with capabilities to carry on a structured case method dialogue, generate teaching material from production rules, construct and verify a model of what the student knows, and explain expert reasoning. The principle objective of this research has been to convert MYCIN, a knowledge-based consultation program, into an effective instructional tool. GUIDON combines the subject matter knowledge of the consultation system with tutorial discourse knowledge, while keeping the two distinct. @MYCIN-like knowledge-based consultation programs are designed to provide expert-level advise about difficult scientific and medical problems. High performance is attained by interpreting a large, specialized set of facts and domain relations that take the form of rules about what to do in a given circumstance. Such a rule base is generally built by interviewing human experts to formulate the knowledge that they use to solve similar problems in their area of expertise. While it is generally believed that these programs have significant educational potential, little work has been done to evaluate the problems of realizing this potential. @Using a rule base for teaching provides a new perspective for showing what production rules have to do with human expertise. This dissertation closely examines the usefulness and adequacy of MYCIN's rules for infectious disease diagnosis as an instructional vehicle: as topics to be discussed in a tutorial, as problem-solving methods for understanding a student's behavior, and as skills to be learned by a student. It is argued that MYCIN-like rule-bases systems constitute a good starting point for developing a tutorial program, but they are not sufficient in themselves for making knowledge accessible to a student. Using GUIDON as an interactive medium for transferring expertise provides a larger context about human cognition; this is reflected in our consideration of subject matter representation and principles of tutorial discourse. @The study of subject matter representation focuses on knowledge that allows the tutor to articulate the structure, underlying principles, and strategies of the domain. This dissertation pays particular attention to aspects of human expertise that have not been captured by the MYCIN rule base, a kind of investigation that has not arisen in the construction, maintenance, and use of this knowledge base for consultation. @The study of tutorial discourse principles focuses on managing the dialogue to achieve economical, systematic presentation of problem-solving expertise. In addition, tutoring methods for opportunistically presenting new material and providing hints on the basis of an hypothesis revision strategy are demonstrated. GUIDON's teaching and discourse expertise is represented as explicit rules. These rules comprise strategies for modeling the student, means for sharing initiative, and knowledge of conventional procedures for discussing a problem in a "goal-directed" way. @After the basic set of tutorial expertise was developed using MYCIN's infectious disease rule set, some perspective on GUIDON's generality and domain independence was attained by coupling it to rule sets for other domains, including an engineering application. Two experiments of this type were performed. They reveal the relationship of discourse strategies to the reasoning structure of the problem being discussed. .skip .begin nofill <<CS-770>> STAN-CS-79-770↔(PVG-13) @PRETTY PRINTING Author: Derek C. Oppen 20 pages↔Cost: $2.30 .end @An algorithm for pretty printing is given. For an input stream of length %2n%1 and an output device with margin width %2m%1, the algorithm requires time %2O(n)%1 and space %2O(m)%1. The algorithm is described in terms of two parallel processes; the first scans the input stream to determine the space required to print logical blocks of tokens; the second uses this information to decide where to break lines of text; the two processes communicate by means of a buffer of size %2O(m)%1. The algorithm does not wait for the entire stream to be input, but begins printing as soon as it has received a linefull of input. The algorithm is easily implemented. .skip .begin nofill <<cs-771>> STAN-CS-79-771 @KNOWLEDGE-BASED EXPERIMENT DESIGN IN MOLECULAR GENETICS Author Peter E. Friedland↔(Thesis) 137 pages↔Available in microfiche only. .end @Laboratory science includes both a design and an implementation stage. Before a competent experimentalist commits his time and resources to achieving some goal, he produces a working outline of the experiment, a guide to each step of the process. The purpose of this work -- MOLGEN -- is to examine and model this design process for the domain of molecular genetics with the aim of producing a tool of significant utility to the laboratory scientist. @The work may be viewed in two perspectives within the domain of artificial intelligence. First, it is a substantial experiment in knowledge engineering with a real system. The experiment design system encompasses problems of knowledge representation and acquisition, as well as research into using that knowledge effectively within a hierarchial planning system. Second, the work has a strong cognitive science aspect. An informal study of human scientists was made with the aim of developing a theory of human performance in a complex scientific task, and then implementing this theory in an automated experiment design system. @The research described in this thesis consits of five major parts: work toward a theory of how scientists design experiments, construction of a system for knowledge-base acquisition, building an expert knowledge-base for a large part of the domain, implementing the theory of human performance in a manner whichmakes efficient use of that knowledge base, and testing the system on real problems in molecular genetics. Individual chapters detail each of the parts, and also provide an annotated example of the design system at work and a description of current problems and future research @The design system is based on the observation that scientists rarely invent an experiment design from scratch. Usually they begin with an abstract or "skeletal" plan which contains the basic steps, which, if successfully carried out, will provide a solution for the experimental goal. The major design task is to instantiate each of the plan-steps with a method which will actually work within the environment of the particular problem. The skeletal plans range from general to specific, depending upon the experimenter and the problem. @The experiment design system is currently (June 1979) operational on a variety of design problems in molecular genetics. It has been most successful, i.e. it produces plausible experimental plans, for analytical problems where the goal is to elucidate structural features of nucleic acid molecules. The knowledge base, build by expert molecular biologists, contains declarative and procedural information about structures, laboratory conditions, laboratory techniques which modify, separate, and detect structural features, and abstract experimental plans for structural analysis. .next page .select 4 <<order form>> REPORT ORDER FORM α#6↔Order Deadline: December 28, 1979 To order reports, or to change your mailing address, complete and return the ENTIRE form (including the mailing label) to: Publications Coordinator, Department of Computer Science, Stanford University, Stanford, California 94305, U.S.A. .skip .begin nofill Hardcopy Microfiche 1._____ STAN-CS-79-760 $2.30 2._____ STAN-CS-79-760 FREE 3._____ STAN-CS-79-761 $1.90 4._____ STAN-CS-79-761 FREE 5._____ AIM-332 $4.70 6._____ AIM-332 FREE 7._____ STAN-CS-79-763 $2.20 8._____ STAN-CS-79-763 FREE 9._____ STAN-CS-79-764 $2.65 A._____ STAN-CS-79-764 FREE B._____ STAN-CS-79-765 $1.95 C._____ STAN-CS-79-765 FREE E._____ STAN-CS-79-766 FREE G._____ STAN-CS-79-767 FREE H._____ STAN-CS-79-768 $2.40 I._____ STAN-CS-79-768 FREE K._____ STAN-CS-79-769 FREE L._____ STAN-CS-79-770 $2.30 M._____ STAN-CS-79-770 FREE O._____ STAN-CS-79-771 FREE .end %4Please do NOT send money with your order. Wait until you receive an invoice, which is enclosed with the reports when they're sent. .skip .begin indent 0,8,0 _____ Check here to change your address. Print the changes above the mailing label, and return this ENTIRE form (including the mailing label) to: Publications Coordinator, Department of Computer Science, Stanford University. .end .skip 10 .begin nofill %4Stanford University Department of Computer Science Stanford, California 94305 .end