Groebner-Shirshov bases, introduced independently by Shirshov in 1962 and Buchberger in 1965, are powerful computational tools in mathematics, science, engineering, and computer science. This thesis focuses on the theories, algorithms, and applications of Groebner-Shirshov bases for two classes of noncommutative algebras: differential difference algebras and skew solvable polynomial rings. This thesis consists of three manuscripts (Chapters 2--4), an introductory chapter (Chapter 1) and a concluding chapter (Chapter 5). In Chapter 1, we introduce the background and the goals of the thesis. In Chapter 2, we investigate the Gelfand-Kirillov dimension of differential difference algebras. We find lower and upper bounds of the Gelfand-Kirillov dimension of a differential difference algebra under some conditions. We also give examples to demonstrate that our bounds are sharp. In Chapter 3, we generalize the Groebner-Shirshov basis theory to differential difference algebras with respect to any left admissible ordering and develop the Groebner-Shirshov basis theory of finitely generated free modules over differential difference algebras. By using the theory we develop, we present an algorithm to compute the Gelfand-Kirillov dimensions of finitely generated modules over differential difference algebras. In Chapter 4, we first define skew solvable polynomial rings, which are generalizations of solvable polynomial algebras and (skew) PBW extensions. Then we present a signature-based algorithm for computing Groebner-Shirshov bases in skew solvable polynomial rings over fields. Our algorithm can detect redundant reductions and therefore it is more efficient than the traditional Buchberger algorithm. Finally, in Chapter 5, we summarize our results and propose possible future work.

Die Arbeit basiert auf zwei Veröffentlichungen zur graduierten kommutativen Algebra: Thema des ersten Artikels ist die Übertragung eines klassischen Ergebnisses zur Höhe von Primidealen in Polynomringen auf allgemeine multigraduierte Ringe; einige Anwendungen für die multigraduierte Dimensionstheorie werden vorgestellt. Der zweite Artikel behandelt Hilbertreihen von Moduln über einem standard-graduierten Polynomring über einem Körper. Ausgehend von einem grundlegenden Ergebnis über gewisse formale Laurentreihen werden unter anderem die möglichen Hilbertreihen und h-Vektoren solcher Moduln charakterisiert.

Error-control codes provide a mechanism to increase the reliability of digital data being processed, transmitted, or stored under noisy conditions. Cyclic codes constitute an important class of error-control code, offering powerful error detection and correction capabilities. They can easily be generated and verified in hardware, which makes them particularly well suited to the practical use as error detecting codes.A cyclic code is based on a generator polynomial which determines its properties including the specific error detection strength. The optimal choice of polynomial depends on many factors that may be influenced by the underlying application. It is therefore advantageous to employ programmable cyclic code hardware that allows a flexible choice of polynomial to be applied to different requirements. A novel method is presented in this thesis to realise programmable cyclic code circuits that are fast, energy-efficient and minimise implementation resources.It can be shown that the correction of a single-bit error on the basis of a cyclic code is equivalent to the solution of an instance of the discrete logarithm problem. A new approach is proposed for computing discrete logarithms; this leads to a generic deterministic algorithm for analysed group orders that equal Mersenne numbers with an exponent of a power of two. The algorithm exhibits a worst-case runtime in the order of the square root of the group order and constant space requirements.This thesis establishes new relationships for finite fields that are represented as the polynomial ring over the binary field modulo a primitive polynomial. With a subset of these properties, a novel approach is developed for the solution of the discrete logarithm in the multiplicative groups of these fields. This leads to a deterministic algorithm for small group orders that has linear space and linearithmic time requirements in the degree of defining polynomial, enabling an efficient correction of single-bit errors based on the corresponding cyclic codes.

The multiple constant multiplication (MCM) operation is a fundamental operation in digital signal processing (DSP) and digital image processing (DIP). Examples of the MCM are in finite impulse response (FIR) and infinite impulse response (IIR) filters, matrix multiplication, and transforms. The aim of this work is minimizing the complexity of the MCM operation using common subexpression elimination (CSE) technique and redundant number representations. The CSE technique searches and eliminates common digit patterns (subexpressions) among MCM coefficients. More common subexpressions can be found by representing the MCM coefficients using redundant number representations. A CSE algorithm is proposed that works on a type of redundant numbers called the zero-dominant set (ZDS). The ZDS is an extension over the representations of minimum number of non-zero digits called minimum Hamming weight (MHW). Using the ZDS improves CSE algorithms' performance as compared with using the MHW representations. The disadvantage of using the ZDS is it increases the possibility of overlapping patterns (digit collisions). In this case, one or more digits are shared between a number of patterns. Eliminating a pattern results in losing other patterns because of eliminating the common digits. A pattern preservation algorithm (PPA) is developed to resolve the overlapping patterns in the representations. A tree and graph encoders are proposed to generate a larger space of number representations. The algorithms generate redundant representations of a value for a given digit set, radix, and wordlength. The tree encoder is modified to search for common subexpressions simultaneously with generating of the representation tree. A complexity measure is proposed to compare between the subexpressions at each node. The algorithm terminates generating the rest of the representation tree when it finds subexpressions with maximum sharing. This reduces the search space while minimizes the hardware complexity. A combinatoric model of the MCM problem is proposed in this work. The model is obtained by enumerating all the possible solutions of the MCM that resemble a graph called the demand graph. Arc routing on this graph gives the solutions of the MCM problem. A similar arc routing is found in the capacitated arc routing such as the winter salting problem. Ant colony optimization (ACO) meta-heuristics is proposed to traverse the demand graph. The ACO is simulated on a PC using Python programming language. This is to verify the model correctness and the work of the ACO. A parallel simulation of the ACO is carried out on a multi-core super computer using C++ boost graph library.