Generalized sorting problems: a symbolic view on reversible algorithms

The paper presents a new framework for canonically associating an algorithm with a set of rewrite systems. We identify an algorithm with the set of all its execution traces. The rewrite systems are defined on the sequences of elementary transforms of the algorithm and are such that their normal forms are exactly the execution traces of the algorithm. The considered algorithms here are those solving a class of problems we define and call the generalized sorting problems. It consists in finding a representative for generating sequences of a presented algebra. Under some reasonable hypotheses, the execution traces are a spanning diagram (colored, directed graph) on the Cayley diagram of the automorphism group of the presented algebra and thus also normal terms of rewrite systems. Then we show that any reversible, always halting algorithm is solving a generalized sorting problem. By a reversible algorithm we mean essentially an algorithm that does not loose information during the executions. Our approach provides a view of all algorithms that solve a given problem with a set of fixed elementary transforms and brings better understanding of the problem: For instance, when any input of the problem has a unique output and the automorphism group of the presented algebra is finite, the diameter of its Cayley graph is a lower bound for the complexity of all the algorithms solving the problem by using the set of fixed elementary transforms. Keywords: ACM classification: G.4.1. Mathematical software-Algorithm design and analysis I.6.5. Simulation and modeling-Model development-Modeling methodologies. Algorithm versus rewrite systems, modeling, symbolic and algebraic algorithms, specification of problems, abstract state machines