NDLI: New results for random determination of equivalence of expressions

Please wait, while we are loading the content...

Iris: design of an user interface program for symbolic algebra

MathScribe: a user interface for computer algebra systems

PowerMath: a system for the Macintosh

Applications of a software interconnection system in mathematical problem solving environments

An object-oriented approach to algebra system design

Construction of rational approximations by means of REDUCE

Alkahest III: automatic analysis of periodic weakly nonlinear ODEs

Investigating the structure of a Lie algebra

Code generation for hybrid mixed mode formulation in finite element analysis

Algebraic decomposition of regular curves

How to compute multivariate Pade approximants

Divide-and-conquer in computational group theory

Fast parallel algorithms for similarity of matrices

Limitations to algorithm solvability: Galois methods and models of computation

Summation of binomial coefficients using hypergeometric functions

A fast carry-free algorithm and hardware design for extended integer GCD computation

Symbolic algorithms for Lie algebra computation

There is no “Uspensky's method.”

Usage of REDUCE for computations of group-theoretical weight of Feynman diagrams in non-Abelian gauge theories

A numerical code generation facility for REDUCE

Enlarging the REDUCE domain of computation

Dialogue in REDUCE: experience and development

A sparse distributed representation using prime numbers

Simplification of algebraic expression by multiterm rewriting rules

Constructive solid geometry: a symbolic computation approach

New results for random determination of equivalence of expressions

A semantic matcher for computer algebra

Computer algebra in the undergraduate mathematics classroom

An application of knowledge-base technology in education: a geometry theorem prover

Computer understanding and generalization of symbolic mathematical calculations: a case study in physics problem solving

Edusym—educational symbolic manipulator on a microcomputer

The design of Macaulay: a system for computing in algebraic geometry and commutative algebra

Conform: a conformal mapping system

A system for manipulating polynomials given by straight-line programs

The computer algebra system CAS1 for the IBM-PC

Integration of Liouvillian functions with special functions

Numerical integration in a symbolic context

Formal solutions of linear difference equations: method of Pincherle-Ramis

Algorithm for computing formal invariants of linear differential systems

Geometry theorem proving using Hilbert's Nullstellensatz

Automated geometry theorem proving using Buchberger's algorithm

Critical-pair criteria for the Knuth-Bendix completion procedure

Buchberger's algorithm and staggered linear bases

The Grobner basis of a module over KUX1,...,Xne and polynomial solutions of a system of linear equations

Grobner bases of ideals of convergent power series

A fast implementation of polynomial factorization

On implementing Buchberger's algorithm for Grobner bases

An implementation of operators for symbolic algebra systems

An operator algebra for Macsyma

Gsolve: a faster algorithm for solving systems of algebraic equations

The Bath algebraic number package

New results for random determination of equivalence of expressions

Content Provider	ACM Digital Library
Author	Gonnet, Gaston H.
Abstract	We devise several procedures based on signatures (or hashing functions) to determine equivalence of expressions in Random Polynomial Time (also called Probabilistic Polynomial Time) (RPT). We extend the previous results known to include various new functions that can be tested. These procedures return as result: “equivalent” or “not-equivalent”. The result “not-equivalent” is always correct, while the result “equivalent” is correct with probability at least 1 — ε. This probability depends on a random number generator and is independent of the problem being solved. In all our procedures, the value ε can be made arbitrarily small. This method works for determining equivalence over an important class of functions as well as answering other questions like linearity, polynomial dependence, squareness, independence, etc.The general scheme for all these algorithms is to use a basic heuristic “test” several times. I.e. solve( problem, epsilon ) repeat select suitable characteristic p randomly; assign random values to all variables; t := test( problem, p ); if t = “not-equivalent” then return( t ) until Prob of cumulative failures >= epsilon; return( “equivalent” );It is assumed that “test” gives a wrong answer with probability δ, where δ remains bounded below 1. For all our “test” procedures, δ ≤ 1/2.In what follows we will describe the “test” part of the different procedures, it is always assumed that these are used in the above context.Without loss of generality we will assume that equivalence of expressions (A ≡ B) can be transformed into testing for 0 (A — B ≡ 0).This test can be performed “quickly” in the sense that it can run in polynomial time on the size of the dag (directed acyclic graph) representation of the expression, also known as “linear program representation” of an expression.
Starting Page	127
Ending Page	131
Page Count	5
File Format	PDF
ISBN	0897911997
DOI	10.1145/32439.32465
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	1986-10-01
Publisher Place	New York
Access Restriction	Subscribed
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in