Full-text indexing of documents containing mathematics cannot be considered a complete success unless the mathematics symbolism is extracted and represented in a standardized form permitting both searching for formulas, and re-use of this information in (for example) computer algebra systems. Most documents produced in the past and subsequently digitally encoded, and even most of those potentially "born digital" in current journal production are---at best---encoded in a printer form such as Adobe Postscript [1], in which mathematics is not explicitly marked or easily identifiable. While one might look forward in the future to other document encodings such as MathML, the common journal or textbook product is essentially without semantic content: a jumble of odd characters. Sometimes it is just a jumble of black and white dots! In this paper we demonstrate an approach to decoding, to recognizing and extracting mathematical expressions, from a Postscript document. We can produce a syntactic representation of the extracted expressions which can then be used to generate various forms. For example, if we extract TeX or Presentation MathML, we can re-typeset the expression, but perhaps in a different size or font family. More significantly, if we start from this presentation information, we can hope to combine it with additional contextual processing of the surrounding text and meta-data associated with the document, to assign semantics,(e.g. content MathML), or provide versions in computer algebra system languages such as Maple or Mathematica. Finally, it is possible to use this material to present audio or braille versions of mathematics for the visually disabled. We have previously addressed some aspects of the higher level of processing (parsing TeX for example). In this paper we address the only first stage and concentrate on what may seem to be overly simple, but is in fact difficult to do precisely: extracting the mathematics parts from text.

One problem in applying elementary methods to prove correctness of interesting scientific programs is the large discrepancy in level of discourse between low-level proof methods and the logic of scientific calculation, especially that used in a complex numerical program. The justification of an algorithm typically relies on algebra or analysis, but the correctness of the program requires that the arithmetic expressions are written correctly and that iterations converge to correct values in spite of truncation of infinite processes or series and the commission of numerical roundoff errors. We hope to help bridge this gap by showing how we can, in some cases, state a high-level requirement and by using a computer algebra system (CAS) demonstrate that a program satisfies that requirement. A CAS can contribute program manipulation, partial evaluation, simplification or other algorithmic methods. A novelty here is that we add to the usual list of techniques algorithm differentiation, a method already widely used in different contexts (usually optimization), to those used already for program proofs. We sketch a proof of a numerical program to compute sine, and display a related approach to a version of a Bessel function algorithm for J0(x) based on a recurrence.

Programs written in languages supporting call-by-reference continue to be of interest in functional programming circumstances where call-by-value is standard. In particular, if we can find a neat interface, by converting Fortran to Lisp we allow programmers to take advantage of an interactive functional symbolic system while running legacy numerical code. We show this can be done without unacceptable loss of efficiency. In building a combined symbolic-numeric environment such a conversion and combination may increase the synergy between the two approaches to scientific computing. This paper builds upon earlier reported work on f2cl.

We exploit the gap in ability between human and machine vision systems to craft a family of automatic challenges that tell human and machine users apart via graphical interfaces including Internet browsers. Turing proposed (1950) a method whereby human judges might validate "artificial intelligence" by failing to distinguish between human and machine interlocutors. Stimulated by the "chat room problem", and influenced by the CAPTCHA project of Blum et al. (2000), we propose a variant of the Turing test using pessimal print: that is, low-quality images of machine-printed text synthesized pseudo-randomly over certain ranges of words, typefaces, and image degradations. We show experimentally that judicious choice of these ranges can ensure that the images are legible to human readers but illegible to several of the best present-day optical character recognition (OCR) machines. Our approach is motivated by a decade of research on performance evaluation of OCR machines and on quantitative stochastic models of document image quality. The slow pace of evolution of OCR and other species of machine vision over many decades suggests that pessimal print will defy automated attack for many years. Applications include 'bot' barriers and database rationing.

The electronic representation of scientific documents (journals, technical reports, program documentation, laboratory notebooks, etc.) presents challenges in several distinct communities. We see five distinct groups who are concerned with electronic versions of scientific documents: (1) publishers of journals, texts and reference works, and their authors; (2) software publishers for OCR/document analysis and document formatting; (3) software publishers whose products access "contents semantics" from documents, including library keyword search programs, natural language search programs, database systems, visual presentation systems, mathematical computation systems, etc.; (4) institutions maintaining access to electronic libraries, which must be broadly construed to include data and programs of all sorts; and (5) individuals and programs acting as their agents who need to use these libraries to identify, locate and retrieve relevant documents. It would be good to have a convergence in design and standards for encoding new or pre-existing (typically paper-based) documents in order to meet the needs of all these groups. Various efforts, some loosely coordinated, but just as often competing, are trying to set standards and build tools. This paper discusses where we are headed.

\Ve describe advantages to using network socket facilities for communication and distributed computing from the perspective of symbolic mathematics systems.For some applications, an easily constructed Lisp server model provides a flexible portal between computer algebra and other programs, and onc need not use new languages or new systems or write new stand-alone web-specific cgi-bin applications.Such socket programs can use, if necessary, HTML as a common transport encoding, but more efficient means are possible, lVe show that, rather than distributing afl information to each computer algebra user's system, it makes sense to consider networking for accessing tables of information maintained iit one or a few sites.Finally, we mention some consequences of the economic value of computation.Pmn)ission t,] ,nakr digital /har(l COPY of all or part Of this work for I)ersonal ur classroom use is granted witho{lt fee provided that copies we lint I)ladc

Article Free Access Share on Symbolic mathematics system evaluators (extended abstract) Author: Richard J. Fateman Computer Sciences Division, Electrical Engineering and Computer Sciences Department, University of California, Berkeley, CA Computer Sciences Division, Electrical Engineering and Computer Sciences Department, University of California, Berkeley, CAView Profile Authors Info & Claims ISSAC '96: Proceedings of the 1996 international symposium on Symbolic and algebraic computationOctober 1996 Pages 86–94https://doi.org/10.1145/236869.236907Published:01 October 1996Publication History 5citation251DownloadsMetricsTotal Citations5Total Downloads251Last 12 Months16Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We describe the design of data structures and a computer program for storing a table of symbolic indefinite or definite integrals and retrieving user-requested integrals on demand. Typical times are so short that a preliminary look-up attempt prior to any algorithmic integration approach seems justified. In one such test for a table with around 700 entries, matches were found requiring an average of 2.8 milliseconds per request, on a Hewlett Packard 9000/712 workstation. 1 Introduction and objectives A goal of our recent work is to explore storage and retrieval of mathematical knowledge in a computer problem-solving environment. In particular we have considered how to supplement a computer algebra system's procedures for computing the form of indefinite or definite integrals by including in the system the mass of integrals that have been tabulated during the last two centuries. Of course some of this tabulated material (and more) can be computed algorithmically, but some of it cannot...

The Heuristic Polynomial GCD procedure (GCDHEU) is used by the Maple computer algebra system, but no other. Because Maple has an especially efficient kernel that provides fast integer arithmetic, but a relatively slower interpreter for non-kernel code, the GCDHEU routine is especially effective in that it moves much of the computation into "bignum" arithmetic and hence executes primarily in the kernel. We speculated that in other computer algebra systems an implementation GCDHEU would not be advantageous. In particular, if all the system code is compiled to run at "full speed" in a (presumably more bulky) kernel that is entirely written in C or compiled Lisp, then there would seem to be no point in recasting the polynomial gcd problem into a bignum GCD problem. Manipulating polynomials that are vectors of coefficients would seem to be equivalent computationally to manipulating vectors of big digits. Yet our evidence suggests that one can take advantage of the GCDHEU in a Lisp system as...

Lisp, one of the oldest higher-level programming languages, has rarely been used for fast numerical (floating-point) computation. We explore the benefits of Common Lisp, an emerging new language standard with some excellent implementations, for numerical computation. We compare it to Fortran in terms of the speed of efficiency of generated code, as well as the structure and convenience of the language. There are a surprising number of advantages to Lisp, especially in cases where a mixture of symbolic and numeric processing is needed.

There is a wealth of mathematical knowledge that could be potentially very useful in many computational applications, but is not available in electronic form. This knowledge comes in the form of mechanically typeset books and journals going back more than a hundred years. Besides these older sources, there are a great many current publications, filled with useful mathematical information, which are difficult if not impossible to obtain in electronic form. What we would like to do is extract character information from these documents, which could then be passed to higher-level parsing routines for further extraction of mathematical content (or any other useful 2-dimensional semantic content). Unfortunately, current commercial OCR (optical character recognition) software packages are quite unable to handle mathematical formulas, since their algorithms at all levels use heuristics developed for other document styles. We are concerned with the development of OCR methods that are able to handle this specialized task of mathematical expression recognition.

Most computer algebra systems provide little assistance in working with expressions involving functions with complex branch cuts. Worse, by their ignorance of the existence of branch cuts, algebra systems sometimes simplify complex expressions incorrectly. We propose a computer representation for branch cuts; we show how a complex expression's branch cuts may be mechanically computed, and how an expression with branch cuts may sometimes be algebraically simplified within each of its branches.

A computer program to honestly plot curves y = $(x) must locate maxima and minima in the domain of the graph.To do so it may have to solve a classic problem in computation -global optimization.Reducing an easy problem to a hard one is usually not an advantage, but in fact there is a route to solving both problems if the function can be evaluated using interval arithmetic.Since some computer algebra systems supply a version of interval arithmetic, it seems we have the ingredients for a solution.In this paper we address a particular problem how to compute and display "honest" graphs of 2-D mathematical curves.By "honest" we mean that no significant features (such as the location of poles, the values at maxima or minima, or the behavior of a curve at asymptotes)are misrepresented, By "mathematical"we mean curves like those generally needed in scientific disciplines where functions are represented by composition of common mathematical operations: rational operations (+, -, *, /), exponential and log, trigonometric functions as well as continuous and differentiable functions from applied mathematics.

Lisp, as well as many other programming languages, '{canonicalizing') an already-constructed list structure.

In a given large fixed table of bit-vectors, we would like to find, as rapidly as possible, those bit-vectors which have the least Hamming distances from a newly-presented arbitrary bit-vector.

We compare and contrast several techniques for the implementation of components of an algebraic manipulation system. On one hand is the mathematical-algebraic approach which characterizes (for example) IBM's Scratchpad II. On the other hand is the more ad hoc approach which characterizes many other popular systems (for example, Macsyma, Reduce, Maple, and Mathematica). While the algebraic approach has generally positive results, careful examination suggests that there are significant remaining problems, especially in the representation and manipulation of analytical, as opposed to algebraic mathematics. We describe some of these problems, and some general approaches for solutions.

Techniques for a MACSYMA package for expanding an arbitrary univariate expression as a truncated series in Chebyshev polynomials and manipulating such expansions is described. A data structure is introduced to represent a truncated expansion in a set of orthogonal polynomials. The data structure contains the independent variable, the name of the orthogonal polynomial set, the number of terms retained, and a list of the expansion coefficients. Although we restrict attention here to the set of Chebyshev polynomials as the orthogonal set, extension to other orthogonal polynomials will be done later. A data structure for truncated power series is provided as an alternative.

Speed of convergence of Newton-like iterations in an algebraic domain can be affected heavily by the increasing cost of each step, so much so that a quadratically convergent algorithm with complex steps may be comparable to a slower one with simple steps. This note gives two examples: solving algebraic and first-order ordinary differential equations using the MACSYMA algebraic manipulation system, demonstrating this phenomenon. The relevant programs are exhibited in the hope that they might give rise to more widespread application of these techniques.

The use of lookup tables can reduce the complexity of calculation of functions defined typically by mathematical recurrence relations. Although this technique has been adopted by several algebraic manipulation systems, it has not been examined critically in the literature. While the use of tabulation or “memoization” seems to be a particularly simple and worthwhile technique in some areas, there are some negative consequences. Furthermore, the expansion of this technique to other areas (other than recurrences) has not been subjected to analysis.

The successes and failures of the Macsyma algebraic manipulation system are reviewed from the point of view of one of the original contributors. A retrospective examination is provided of some of the controversial ideas that worked, and some that did not. Input/output, language semantics, knowledge-adjunction, mathematical semantics, the model of the user, and other issues are considered. Possible future directions for algebraic manipulation system building are discussed.>

Abstract Run‐time program profiling is a valuable tool in understanding software efficiency. Techniques for obtaining profiles make assumptions that may result in misleading data. In the paper we illustrate flaws in two profiling systems: the Unix ‘Gprof’ family (including the packages ‘monitor’, ‘prof’ and ‘profil’), and the TI Explorer metering package for Lisp.

An IEEE Computer Society working group on floating-point arithmetic has recommended a standard for binary floating.pointnumber formats, operations, and semantics.This paper, which has evolved in part during the deliberations of that committee, describes the significance to languages and, in particular, to FORTRAN and its Variants, of various novel features of the recommended standard.

This paper examines multiplication and powering of dense symbolic polynomials, in one or several variables, with “nongrowing” coefficients (e.g., coefficients in a finite field). We use a “completely dense” model for polynomials, in order to present worst-case analyses. In this context, the use and abuse of asymptotic analysis techniques is discussed. Six algorithms for computing polynomial powers are analyzed in terms of the time required for execution on a typical digital computer, and procedures are derived for choosing the fastest algorithm, exactly, as a function of degree, number of variables, and power to be computed. The case of sparse polynomials is discussed in a separate paper [6].