CiteULike: AbnerCYH's algebra

Shellable Nonpure Complexes and Posets. II

Anders Bjorner — 2008-05-27T08:00:27-00:00

Vol. 349, No. 10. (October 1997), pp. 3945-3975.

Shellable Nonpure Complexes and Posets. I

Anders Bjorner — 2008-05-27T07:58:17-00:00

Transactions of the American Mathematical Society, Vol. 348, No. 4. (April 1996), pp. 1299-1367.

Shellable graphs and sequentially Cohen-Macaulay bipartite graphs

Adam Van Tuyl — 2008-05-20T04:00:55-00:00

Journal of Combinatorial Theory, Series A, Vol. 115, No. 5. (July 2008), pp. 799-814.

Associated to a simple undirected graph G is a simplicial complex [Delta]G whose faces correspond to the independent sets of G. We call a graph G shellable if [Delta]G is a shellable simplicial complex in the non-pure sense of Björner-Wachs. We are then interested in determining what families of graphs have the property that G is shellable. We show that all chordal graphs are shellable. Furthermore, we classify all the shellable bipartite graphs; they are precisely the sequentially Cohen-Macaulay bipartite graphs. We also give a recursive procedure to verify if a bipartite graph is shellable. Because shellable implies that the associated Stanley-Reisner ring is sequentially Cohen-Macaulay, our results complement and extend recent work on the problem of determining when the edge ideal of a graph is (sequentially) Cohen-Macaulay. We also give a new proof for a result of Faridi on the sequentially Cohen-Macaulayness of simplicial forests.

Singular Value Decomposition and Principal Component Analysis

Michael Wall — 2005-10-17T02:36:40-00:00

(3 Mar 2003)

This chapter describes gene expression analysis by Singular Value Decomposition (SVD), emphasizing initial characterization of the data. We describe SVD methods for visualization of gene expression data, representation of the data using a smaller number of variables, and detection of patterns in noisy gene expression data. In addition, we describe the precise relation between SVD analysis and Principal Component Analysis (PCA) when PCA is calculated using the covariance matrix, enabling our descriptions to apply equally well to either method. Our aim is to provide definitions, interpretations, examples, and references that will serve as resources for understanding and extending the application of SVD and PCA to gene expression analysis.

The support vector machine under test

David Meyer — 2008-05-09T19:40:26-00:00

Neurocomputing, Vol. 55, No. 1-2. (September 2003), pp. 169-186.

Support vector machines (SVMs) are rarely benchmarked against other classification or regression methods. We compare a popular SVM implementation (libsvm) to 16 classification methods and 9 regression methods--all accessible through the software --by the means of standard performance measures (classification error and mean squared error) which are also analyzed by the means of bias-variance decompositions. SVMs showed mostly good performances both on classification and regression tasks, but other methods proved to be very competitive.

Fundamentals of Algebraic Graph Transformation (Monographs in Theoretical Computer Science. An EATCS Series)

H Ehrig — 2007-12-08T00:44:30-00:00

(14 March 2006)

Graphs are widely used to represent structural information in the form of objects and connections between them. Graph transformation is the rule-based manipulation of graphs, an increasingly important concept in computer science and related fields. This is the first textbook treatment of the algebraic approach to graph transformation, based on algebraic structures and category theory. Part I is an introduction to the classical case of graph and typed graph transformation. In Part II basic and advanced results are first shown for an abstract form of replacement systems, so-called adhesive high-level replacement systems based on category theory, and are then instantiated to several forms of graph and Petri net transformation systems. Part III develops typed attributed graph transformation, a technique of key relevance in the modeling of visual languages and in model transformation. Part IV contains a practical case study on model transformation and a presentation of the AGG (attributed graph grammar) tool environment. Finally the appendix covers the basics of category theory, signatures and algebras. The book addresses both research scientists and graduate students in computer science, mathematics and engineering.

Completeness and Reduction in Algebraic Complexity Theory (Algorithms and Computation in Mathematics)

Peter Bürgisser — 2008-04-21T18:11:43-00:00

(26 July 2000)

The theory of NP-completeness is a cornerstone of computational complexity. This monograph provides a thorough and comprehensive treatment of this concept in the framework of algebraic complexity theory. Many of the results presented are new and published for the first time. Topics include: complete treatment of Valiant's algebraic theory of NP-completeness, interrelations with the classical theory as well as the Blum-Shub-Smale model of computation, questions of structural complexity, fast evaluation of representations of general linear groups, and complexity of immanants. The book can be used at the advanced undergraduate or at the beginning graduate level in either mathematics or computer science.

Complexes of Graphs with Bounded Matching Size

Svante Linusson — 2008-04-14T10:00:17-00:00

Journal of Algebraic Combinatorics, Vol. 27, No. 3. (10 May 2008), pp. 331-349.

Abstract For positive integers k,n, we investigate the simplicial complex of all graphs G on vertex set [n] such that every matching in G has size less than k. This complex (along with other associated cell complexes) is found to be homotopy equivalent to a wedge of spheres. The number and dimension of the spheres in the wedge are determined, and (partially conjectural) links to other combinatorially defined complexes are described. In addition we study for positive integers r,s and k the simplicial complex of all bipartite graphs G on bipartition such that there is no matching of size k in G, and obtain results similar to those obtained for .

Notes on topological vector spaces

Stephen Semmes — 2008-03-28T16:50:53-00:00

(13 Apr 2003)

These are some informal notes concerning topological vector spaces, with a brief overview of background material and basic notions, and emphasis on examples related to classical analysis.

Cones of Matrices and Set-Functions and 0–1 Optimization

Lovász — 2008-03-26T14:22:54-00:00

SIAM Journal on Optimization, Vol. 1, No. 2. (1991), pp. 166-190.

It has been recognized recently that to represent a polyhedron as the projection of a higher-dimensional, but simpler, polyhedron, is a powerful tool in polyhedral combinatorics. A general method is developed to construct higher-dimensional polyhedra (or, in some cases, convex sets) whose projection approximates the convex hull of 0–1 valued solutions of a system of linear inequalities. An important feature of these approximations is that one can optimize any linear objective function over them in polynomial time.In the special case of the vertex packing polytope, a sequence of systems of inequalities is obtained such that the first system already includes clique, odd hole, odd antihole, wheel, and orthogonality constraints. In particular, for perfect (and many other) graphs, this first system gives the vertex packing polytope. For various classes of graphs, including $t$-perfect graphs, it follows that the stable set polytope is the projection of a polytope with a polynomial number of facets.An extension of the method is also discussed which establishes a connection with certain submodular functions and the Möbius function of a lattice.

Domination, Fractional Domination, 2-Packing, and Graph Products

David Fisher — 2007-02-18T23:54:52-00:00

SIAM Journal on Discrete Mathematics, Vol. 7, No. 3. (1994), pp. 493-498.

Complexity of Finding Embeddings in a $k$-Tree

Stefan Arnborg — 2007-04-27T18:34:38-00:00

SIAM Journal on Algebraic and Discrete Methods, Vol. 8, No. 2. (1987), pp. 277-284.

The algebraic Monge property and path problems

Wolfgang Bein — 2008-03-24T17:42:43-00:00

Discrete Applied Mathematics, Vol. 145, No. 3. (30 January 2005), pp. 455-464.

We give algorithmic results for combinatorial problems with cost arrays possessing certain algebraic Monge properties. We extend Monge-array results for two shortest path problems to a general algebraic setting, with values in an ordered commutative semigroup, if the semigroup operator is strictly compatible with the order relation. We show how our algorithms can be modified to solve bottleneck shortest path problems, even though strict compatibility does not hold in that case. For example, we give a linear time algorithm for the unrestricted shortest path bottleneck problem on n nodes, also O(kn) and O(n3/2 log5/2 n) time algorithms for the k-shortest path bottleneck problem.

On the dominating set polytope

M Bouchakour — 2008-03-10T16:19:34-00:00

European Journal of Combinatorics, Vol. 29, No. 3. (April 2008), pp. 652-661.

In this paper, we study the dominating set polytope in the class of graphs that decompose by one-node cutsets where the pieces are cycles. We describe some classes of facets and procedures to construct facets of the polytope in that class of graphs, and establish some structural properties. As a consequence we obtain a complete description of the polytope by a system of inequalities when the graph is a cycle. We also show that the separation problem related to that system can be solved in polynomial time. This yields a polynomial time cutting plane algorithm for the minimum weight dominating set problem in that case. We further discuss the applications for the class of cactus graphs.

Hopf Algebras in General and in Combinatorial Physics: a practical introduction

GHE Duchamp — 2008-02-11T20:11:28-00:00

(2 Feb 2008)

This tutorial is intended to give an accessible introduction to Hopf algebras. The mathematical context is that of representation theory, and we also illustrate the structures with examples taken from combinatorics and quantum physics, showing that in this latter case the axioms of Hopf algebra arise naturally. The text contains many exercises, some taken from physics, aimed at expanding and exemplifying the concepts introduced.

Zero-Knowledge Proofs of the Conjugacy for Permutation Groups

Oleg Verbitsky — 2008-02-02T06:12:03-00:00

(31 Jan 2008)

We design a perfect zero-knowledge proof system for recognition if two permutation groups are conjugate.

Computer algebra in systems biology

Reinhard Laubenbacher — 2007-12-28T08:52:17-00:00

(27 Dec 2007)

Systems biology focuses on the study of entire biological systems rather than on their individual components. With the emergence of high-throughput data generation technologies for molecular biology and the development of advanced mathematical modeling techniques, this field promises to provide important new insights. At the same time, with the availability of increasingly powerful computers, computer algebra has developed into a useful tool for many applications. This article illustrates the use of computer algebra in systems biology by way of a well-known gene regulatory network, the Lac Operon in the bacterium E. coli.

Partitioning Sparse Graphs using the Second Eigenvector of their Graph Laplacian

David De Wit — 2007-11-23T20:19:40-00:00

(6 Mar 2000)

Partitioning a graph into three pieces, with two of them large and connected, and the third a small “separator” set, is useful for improving the performance of a number of combinatorial algorithms. This is done using the second eigenvector of a matrix defined solely in terms of the incidence matrix, called the graph Laplacian. For sparse graphs, the eigenvector can be efficiently computed using the Lanczos algorithm. This graph partitioning algorithm is extended to provide a complete hierarchical subdivision of the graph. The method has been implemented and numerical results obtained both for simple test problems and for several grid graphs.

Model indexing: the graph-hashing approach

H Sossa — 2007-12-06T03:07:36-00:00

Computer Vision and Pattern Recognition, 1992. Proceedings CVPR '92., 1992 IEEE Computer Society Conference on (1992), pp. 811-814.

The problem of object recognition in computer vision is addressed. A method for model indexing, which, given a group of image features, rapidly extracts from the list of objects those objects containing this group of features, is presented. The method operates on an abstract representation of features, more precisely, groups of features. In practice, this abstract representation takes the form of a graph. The present study deals with binary graphs only, that is, only one feature-type and one feature-relationship-type can be embedded in the representation

Indexing hierarchical structures using graph spectra

A Shokoufandeh — 2007-12-06T03:06:57-00:00

Transactions on Pattern Analysis and Machine Intelligence, Vol. 27, No. 7. (2005), pp. 1125-1140.

Hierarchical image structures are abundant in computer vision and have been used to encode part structure, scale spaces, and a variety of multiresolution features. In this paper, we describe a framework for indexing such representations that embeds the topological structure of a directed acyclic graph (DAG) into a low-dimensional vector space. Based on a novel spectral characterization of a DAG, this topological signature allows us to efficiently retrieve a promising set of candidates from a database of models using a simple nearest-neighbor search. We establish the insensitivity of the signature to minor perturbation of graph structure due to noise, occlusion, or node split/merge. To accommodate large-scale occlusion, the DAG rooted at each nonleaf node of the query "votes" for model objects that share that "part," effectively accumulating local evidence in a model DAG's topological subspaces. We demonstrate the approach with a series of indexing experiments in the domain of view-based 3D object recognition using shock graphs.

Entropy of capacities on lattices and set systems

Aoi Honda — 2007-11-14T08:37:40-00:00

(13 Nov 2007)

We propose a definition for the entropy of capacities defined on lattices. Classical capacities are monotone set functions and can be seen as a generalization of probability measures. Capacities on lattices address the general case where the family of subsets is not necessarily the Boolean lattice of all subsets. Our definition encompasses the classical definition of Shannon for probability measures, as well as the entropy of Marichal defined for classical capacities. Some properties and examples are given.

Algebraic decision trees and Euler characteristics

Andrew Yao — 2005-09-28T15:25:48-00:00

Theor. Comput. Sci., Vol. 141, No. 1-2. (1995), pp. 133-150.

For any set Image, let χ(S) denote its Euler characteristic. In this paper, we show that any algebraic computation tree or fixed-degree algebraic decision tree must have height Ω(log¦χ(S)¦ − cn) for deciding the membership question of a compact semi-algebraic set S. This extends a result in Björner et al. (1992), where it was shown that any linear decision tree for deciding the membership question of a closed polyhedron S must have height greater than or equal to log3¦χ(S)¦.

Permutation Group Algorithms

Ákos Seress — 2007-11-08T18:13:45-00:00

(15 July 2002)

Permutation group algorithms are indispensable in the proofs of many deep results, including the construction and study of sporadic finite simple groups. This work describes the theory behind permutation group algorithms, up to the most recent developments based on the classification of finite simple groups. Rigorous complexity estimates, implementation hints, and advanced exercises are included throughout. The central theme is the description of nearly linear time algorithms, which are extremely fast both in terms of asymptotic analysis and of practical running time. The book fills a significant gap in the symbolic computation literature for readers interested in using computers in group theory. Permutation group algorithms are one of the workhorses of symbolic algebra systems computing with groups. They played an indispensable role in the proof of many deep results, including the construction and study of sporadic finite simple groups. This book describes the theory behind permutation group algorithms, up to the most recent developments based on the classification of finite simple groups. Rigorous complexity estimates, implementation hints, and advanced exercises are included throughout. The central theme is the description of nearly linear time algorithms, which are extremely fast both in terms of asymptotic analysis and of practical running time. A significant part of the permutation group library of the computational group algebra system GAP is based on nearly linear time algorithms. The book fills a significant gap in the symbolic computation literature. It is recommended for everyone interested in using computers in group theory, and is suitable for advanced graduate courses.

The Discrete Fundamental Group of the Order Complex of $B_n$

Hélène Barcelo — 2007-11-07T12:25:51-00:00

(6 Nov 2007)

A few years ago Kramer and Laubenbacher introduced a discrete notion of homotopy for simplicial complexes. In this paper, we compute the discrete fundamental group of the order complex of the Boolean lattice. As it turns out, it is equivalent to computing the discrete homotopy group of the 1-skeleton of the permutahedron. To compute this group we introduce combinatorial techniques that we believe will be helpful in computing discrete fundamental groups of other polytopes. More precisely, we use the language of words, over the alphabet of simple transpositions, to obtain conditions that are necessary and sufficient to characterize the equivalence classes of cycles. The proof requires only simple combinatorial arguments. As a corollary, we also obtain a combinatorial proof of the fact that the first Betti number of the complement of the 3-equal arrangement is equal to $2^n-3(n^2-5n+8)-1.$ This formula was originally obtained by Björner and Welker in 1995.

Elements of Algebraic Topology

James Munkres — 2007-10-31T17:40:49-00:00

(01 December 1993)

Lattices and Ordered Algebraic Structures (Universitext)

TS Blyth — 2007-10-17T07:18:06-00:00

(22 March 2005)

Lattices and Ordered Algebraic Structures provides a lucid and concise introduction to the basic results concerning the notion of an order. Although as a whole it is mainly intended for beginning postgraduates, the prerequisities are minimal and selected parts can profitably be used to broaden the horizon of the advanced undergraduate. The treatment is modern, with a slant towards recent developments in the theory of residuated lattices and ordered regular semigroups. Topics covered include: residuated mappings; Galois connections; modular, distributive, and complemented lattices; Boolean algebras; pseudocomplemented lattices; Stone algebras; Heyting algebras; ordered groups; lattice-ordered groups; representable groups; Archimedean ordered structures; ordered semigroups; naturally ordered regular and inverse Dubreil-Jacotin semigroups. Featuring material that has been hitherto available only in research articles, and an account of the range of applications of the theory, there are also many illustrative examples and numerous exercises throughout, making it ideal for use as a course text, or as a basic introduction to the field for researchers in mathematics, logic and computer science.

A Group Theoretic Model for Information

Hua Li — 2007-10-09T19:55:15-00:00

(5 Oct 2007)

In this paper we formalize the notions of information elements and information lattices, first proposed by Shannon. Exploiting this formalization, we identify a comprehensive parallelism between information lattices and subgroup lattices. Qualitatively, we demonstrate isomorphisms between information lattices and subgroup lattices. Quantitatively, we establish a decisive approximation relation between the entropy structures of information lattices and the log-index structures of the corresponding subgroup lattices. This approximation extends the approximation for joint entropies carried out previously by Chan and Yeung. As a consequence of our approximation result, we show that any continuous law holds in general for the entropies of information elements if and only if the same law holds in general for the log-indices of subgroups. As an application, by constructing subgroup counterexamples we find surprisingly that common information, unlike joint information, obeys neither the submodularity nor the supermodularity law. We emphasize that the notion of information elements is conceptually significant--formalizing it helps to reveal the deep connection between information theory and group theory. The parallelism established in this paper admits an appealing group-action explanation and provides useful insights into the intrinsic structure among information elements from a group-theoretic perspective.

Posets of Matrices and Permutations with Forbidden Subsequences

Nigel Ray — 2007-10-03T11:00:47-00:00

Annals of Combinatorics, Vol. 7, No. 1. (1 June 2003), pp. 55-88.

The enumeration of permutations with specific forbidden subsequences has applications in areas ranging from algebraic geometry to the study of sorting algorithms. We consider a ranked poset of permutation matrices whose global structure incorporates the solution to the equivalent problem of enumerating permutations which contain a required subsequence. We describe this structure completely for saturated chains of lengths one and two, so settling several new and general instances of the original problem, and conclude with a superficial asymptotic investigation of arbitrary chains whose length is small by comparison with the rank of its constituent permutations. The value of this approach is reflected in the appearance of closed polynomial formulae (related to the Robinson-Schensted correspondence) and of a framework for the systematic analysis of associated combinatorial questions; indeed, we begin by studying a simpler poset of 0-1 sequences as the natural environment in which to introduce our insertion and deletion operators.

Deterministic restrictions in circuit complexity

Shiva Chaudhuri — 2007-08-28T07:16:22-00:00

(1996), pp. 30-36.

Constant-Depth Circuits for Arithmetic in Finite Fields of Characteristic Two

Alexander Healy — 2007-08-28T07:13:48-00:00

STACS 2006 (2006), pp. 672-683.

We study the complexity of arithmetic in finite fields of characteristic two, . We concentrate on the following two problems:

Algebraic topology and concurrency

Lisbeth Fajstrup — 2007-08-09T15:58:27-00:00

Theoretical Computer Science, Vol. 357, No. 1-3. (25 July 2006), pp. 241-278.

We show in this article that some concepts from homotopy theory, in algebraic topology, are relevant for studying concurrent programs. We exhibit a natural semantics of semaphore programs, based on partially ordered topological spaces, which are studied up to "elastic deformation" or homotopy, giving information about important properties of the program, such as deadlocks, unreachables, serializability, essential schedules, etc. In fact, it is not quite ordinary homotopy that has to be used, but rather a "directed homotopy" that does not reverse the flow of time. We show some of the essential differences between ordinary and directed homotopy through examples. We also relate the topological view to a combinatorial view of concurrent programs closer to transition systems, through the notion of a cubical set. Finally we apply some of these concepts to the proof of the safeness of a two-phase protocol, well-known and used in concurrent database theory. We end up with a list of problems from both a mathematical and a computer-scientific point of view.

Combinatorial Group Testing and Its Applications (Applied Mathematics)

Ding-Zhu Du — 2007-07-26T11:37:00-00:00

(01 January 2000)

The branchwidth of graphs and their cycle matroids

Illya Hicks — 2007-07-17T16:13:21-00:00

Journal of Combinatorial Theory, Series B, Vol. 97, No. 5. (September 2007), pp. 681-692.

We prove a conjecture stating that the branchwidth of a graph and the branchwidth of the graph's cycle matroid are equal if the graph has a cycle of length at least 2.

The Principal Components Analysis of a Graph, and its Relationships to Spectral Clustering

Marco Francois — 2005-04-21T03:15:43-00:00

This work presents a novel procedure for computing (1) distances between nodes of a weighted, undirected, graph, called the Euclidean Commute Time Distance (ECTD), and (2) a subspace projection of the nodes of the graph that preserves as much variance as possible, in terms of the ECTD -- a principal components analysis of the graph. It is based on a Markov-chain model of random walk through the graph. The model assigns transition probabilities to the links between nodes, so that a random...

The $25,000,000,000 Eigenvector: The Linear Algebra behind Google

Kurt Bryan — 2006-12-07T16:36:25-00:00

SIAM Review, Vol. 48, No. 3. (2006), pp. 569-581.

Pages 569-581,

Algebraic Calculation of Graph and Sorting Algorithms (Invited Paper)

Bernhard M&\#246;ller — 2007-04-08T13:47:30-00:00

(1993), pp. 394-413.

Simple image set of linear mappings in a max-min algebra

Martin Gavalec — 2007-03-27T10:53:05-00:00

Discrete Applied Mathematics, Vol. 155, No. 5. (15 March 2007), pp. 611-622.

For a given linear mapping, determined by a square matrix A in a max-min algebra, the set SA consisting of all vectors with a unique pre-image (in short: the simple image set of A) is considered. It is shown that if the matrix A is generally trapezoidal, then the closure of SA is a subset of the set of all eigenvectors of A. In the general case, there is a permutation [pi], such that the closure of SA is a subset of the set of all eigenvectors permuted by [pi]. The simple image set of the matrix square and the topological aspects of the problem are also described.

An Algebraic Perspective of Group Relaxations

Rekha Thomas — 2007-03-27T10:27:02-00:00

(3 Oct 2001)

This is an expository article on recent developments in the theory of group relaxations in integer programming from an algebraic perspective.

Max-algebra: the linear algebra of combinatorics?

Peter Butkovic — 2007-03-15T00:55:31-00:00

Linear Algebra and its Applications, Vol. 367 (1 July 2003), pp. 313-335.

Let a[circled plus]b=max(a,b), a[circle times operator]b=a+b for . By max-algebra we understand the analogue of linear algebra developed for the pair of operations ([circled plus],[circle times operator]) extended to matrices and vectors. Max-algebra, which has been studied for more than 40 years, is an attractive way of describing a class of nonlinear problems appearing for instance in machine-scheduling, information technology and discrete-event dynamic systems. This paper focuses on presenting a number of links between basic max-algebraic problems like systems of linear equations, eigenvalue-eigenvector problem, linear independence, regularity and characteristic polynomial on one hand and combinatorial or combinatorial optimisation problems on the other hand. This indicates that max-algebra may be regarded as a linear-algebraic encoding of a class of combinatorial problems. The paper is intended for wider readership including researchers not familiar with max-algebra.

The Euler characteristic of a category

Tom Leinster — 2006-10-10T07:37:37-00:00

(8 Oct 2006)

The Euler characteristic of a finite category is defined and shown to be compatible with Euler characteristics of other types of object, including orbifolds. A formula for the cardinality of the colimit of a diagram of sets is proved, generalizing the classical inclusion-exclusion formula. Both rest on a generalization of Mobius-Rota inversion from posets to categories.

Combinatorial Convexity and Algebraic Geometry (Graduate Texts in Mathematics)

Günter Ewald — 2006-05-11T19:28:28-00:00

(03 October 1996)

This text provides an introduction to the theory of convex polytopes and polyhedral sets, to algebraic geometry and to the fascinating connections between these fields: the theory of toric varieties (or torus embeddings). The fist part of the book contains an introduction to the theory of polytopes - one of the most important parts of classical geometry in n-dimensional Euclidean space. Since the discussion here is independent of any applications to algebraic geometry, it would also be suitable for a course in geometry. This part also provides large parts of the mathematical background of linear optimization and of the geometrical aspects in Computer Science. The second part introduces toric varieties in an elementary way, building on the concepts of combinatorial geometry introduced in the first part. Many of the general concepts of algebraic geometry arise in this treatment and can be dealt with concretely. This part of the book can thus serve for a one-semester introduction to algebraic geometry, with the first part serving as a reference for combinatorial geometry.

Algebraic Automata Theory (Cambridge Studies in Advanced Mathematics)

M Holcombe — 2006-05-07T17:11:27-00:00

(19 August 1982)

This is a self-contained, modern treatment of the algebraic theory of machines. Dr Holcombe examines various applications of the idea of a machine in biology, biochemistry and computer science and gives also a rigorous treatment of the way in which these machines can be decomposed and simulated by simpler ones. This treatment is based on fundamental ideas from modern algebra. Motivation for many of the newer results is provided by way of applications so this account should be accessible and valuable for those studying applied algebra or theoretical computer science at advanced undergraduate or beginning postgraduate level, as well as for those undertaking research in those areas.