In abstract algebra, a branch of mathematics, a monoid is a set equipped with an associative binary operation and an identity element. For example, the nonnegative integers with addition form a monoid, the identity element being 0.
In mathematics, a semigroup is an algebraic structure consisting of a set together with an associative internal binary operation on it.
In abstract algebra, a generating set of a group is a subset of the group set such that every element of the group can be expressed as a combination of finitely many elements of the subset and their inverses.
In abstract algebra, a semiring is an algebraic structure similar to a ring, but without the requirement that each element must have an additive inverse.
In abstract algebra, the free monoid on a set is the monoid whose elements are all the finite sequences of zero or more elements from that set, with string concatenation as the monoid operation and with the unique sequence of zero elements, often called the empty string and denoted by ε or λ, as the identity element. The free monoid on a set A is usually denoted A∗. The free semigroup on A is the subsemigroup of A∗ containing all elements except the empty string. It is usually denoted A+.
In mathematics and computer science, the syntactic monoid of a formal language is the smallest monoid that recognizes the language .
In universal algebra, a variety of algebras or equational class is the class of all algebraic structures of a given signature satisfying a given set of identities. For example, the groups form a variety of algebras, as do the abelian groups, the rings, the monoids etc. According to Birkhoff's theorem, a class of algebraic structures of the same signature is a variety if and only if it is closed under the taking of homomorphic images, subalgebras, and (direct) products. In the context of category theory, a variety of algebras, together with its homomorphisms, forms a category; these are usually called finitary algebraic categories.
In mathematics, the bicyclic semigroup is an algebraic object important for the structure theory of semigroups. Although it is in fact a monoid, it is usually referred to as simply a semigroup. It is perhaps most easily understood as the syntactic monoid describing the Dyck language of balanced pairs of parentheses. Thus, it finds common applications in combinatorics, such as describing binary trees and associative algebras.
In group theory, an inverse semigroupS is a semigroup in which every element x in S has a unique inversey in S in the sense that x = xyx and y = yxy, i.e. a regular semigroup in which every element has a unique inverse. Inverse semigroups appear in a range of contexts; for example, they can be employed in the study of partial symmetries.
In theoretical computer science and mathematical logic a string rewriting system (SRS), historically called a semi-Thue system, is a rewriting system over strings from a alphabet. Given a binary relation between fixed strings over the alphabet, called rewrite rules, denoted by , an SRS extends the rewriting relation to all strings in which the left- and right-hand side of the rules appear as substrings, that is , where , , , and are strings.
In algebra, a presentation of a monoid is a description of a monoid in terms of a set Σ of generators and a set of relations on the free monoid Σ∗ generated by Σ. The monoid is then presented as the quotient of the free monoid by these relations. This is an analogue of a group presentation in group theory.
In mathematics, the congruence lattice problem asks whether every algebraic distributive lattice is isomorphic to the congruence lattice of some other lattice. The problem was posed by Robert P. Dilworth, and for many years it was one of the most famous and long-standing open problems in lattice theory; it had a deep impact on the development of lattice theory itself. The conjecture that every distributive lattice is a congruence lattice is true for all distributive lattices with at most ℵ1 compact elements, but F. Wehrung provided a counterexample for distributive lattices with ℵ2 compact elements using a construction based on Kuratowski's free set theorem.
In theoretical computer science and mathematics, especially in the area of combinatorics on words, the Levi lemma states that, for all strings u, v, x and y, if uv = xy, then there exists a string w such that either
In mathematics, particularly in abstract algebra, a semigroup with involution or a *-semigroup is a semigroup equipped with an involutive anti-automorphism, which—roughly speaking—brings it closer to a group because this involution, considered as unary operator, exhibits certain fundamental properties of the operation of taking the inverse in a group: uniqueness, double application "cancelling itself out", and the same interaction law with the binary operation as in the case of the group inverse. It is thus not a surprise that any group is a semigroup with involution. However, there are significant natural examples of semigroups with involution that are not groups.
In mathematics, a numerical semigroup is a special kind of a semigroup. Its underlying set is the set of all nonnegative integers except a finite number and the binary operation is the operation of addition of integers. Also, the integer 0 must be an element of the semigroup. For example, while the set {0, 2, 3, 4, 5, 6, ...} is a numerical semigroup, the set {0, 1, 3, 5, 6, ...} is not because 1 is in the set and 1 + 1 = 2 is not in the set. Numerical semigroups are commutative monoids and are also known as numerical monoids.
In computer science, more precisely in automata theory, a rational set of a monoid is an element of the minimal class of subsets of this monoid that contains all finite subsets and is closed under union, product and Kleene star. Rational sets are useful in automata theory, formal languages and algebra.
In mathematics, a rational monoid is a monoid, an algebraic structure, for which each element can be represented in a "normal form" that can be computed by a finite transducer: multiplication in such a monoid is "easy", in the sense that it can be described by a rational function.
In mathematics, and more precisely in semigroup theory, a variety of finite semigroups is a class of semigroups having some nice algebraic properties. Those classes can be defined in two distinct ways, using either algebraic notions or topological notions. Varieties of finite monoids, varieties of finite ordered semigroups and varieties of finite ordered monoids are defined similarly.
