=ADD=
=reftype=
14
=number=
98-24
=url=
ftp://ftp.risc.uni-linz.ac.at/pub/techreports/1998/98-24.ps.gz
=year=
1998
=month=
12
=author=
Caprotti; Olga
=title=
Symbolic Pattern Solving in Algebraic Structures
=abstract=
This thesis introduces and develops a new method for finding symbolic solutions
of equations in progressively richer algebraic structures.
A symbolic solution, compared to corresponding 'numeric' answer, is advantageous
because it is expressive, maipulatable, error-free and reusable.
Intensive research in symbolic computation has already produced deep results,
for instance in unification theory and computer algebra.
But, it is not yet sufficient.
As soon as the problems increase in complexity, whether for the number of
equations, or their degree, or for the number of symbols involved, the
symbolic methods fail to perform to the expectations of real-world
applications.
However, the problem instance often suggests a skeleton of the solution, a
{\em solution pattern}.
A promising approach, advocated here, uses these patterns to reduce the
original complexity by requesting only solutions of a specific form.
Pattern solving is successful if some substitution of the unknown
coefficients, whithin the pattern, turns the pattern into a solution.
The core of the method is the possibility of straightforward elimination of
universally quantified variables from formulas related to the input problem and
solution pattern.
It is shown that fast elimination of universal quantifiers is complete in
infinite integral domains, torsion-free modules over an infinite domain,
finite dimensional division algebras over infinite fields, and in graded
exterior algebras, if the underlying scalar field is infinite.
These results promise that pattern solving can even be extended beyond the
rich algebraic structures shown.
=note=
PhD Thesis
=sponsor=
ACCLAIM (EP 7195): Advanced Concurrent Constraint Languages,
CEI-PACT: Programming Environments, Algorithms, Applications, Compilers, and
Tools for Parallel Computation, WP4 on Computer Algebra.