Straight-line Instruction Sequence Completeness for Total Calculation on Cancellation Meadows

A combination of program algebra with the theory of meadows is designed leading to a theory of computation in algebraic structures. It is proven that total functions on cancellation meadows can be computed by straight-line programs using at most five auxiliary variables. A similar result is obtained...

Full description

Saved in:
Bibliographic Details
Published in:Theory of computing systems 2011-05, Vol.48 (4), p.840-864
Main Authors: Bergstra, Jan A., Bethke, Inge
Format: Article
Language:English
Subjects:
Algebra
Algorithms
Computer programming
Computer Science
Investigations
Mathematical analysis
Science
Semantics
Studies
Theory of Computation
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A combination of program algebra with the theory of meadows is designed leading to a theory of computation in algebraic structures. It is proven that total functions on cancellation meadows can be computed by straight-line programs using at most five auxiliary variables. A similar result is obtained for signed meadows.
ISSN:1432-4350
1433-0490
DOI:10.1007/s00224-010-9272-9