Copyright | (c) 2023 Dakotah Lambert |
---|---|
License | MIT |
Safe Haskell | Safe-Inferred |
Language | Haskell2010 |
This module collects and exports the entire interface for representations of finite semigroups.
Synopsis
- class FiniteSemigroupRep a where
- data FSMult
- data GeneratedAction
- fromBases :: [[Int]] -> GeneratedAction
- mapsInto :: GeneratedAction -> IntSet -> Int -> IntSet
- independentBases :: FiniteSemigroupRep s => s -> [[Int]]
- subsemigroup :: FiniteSemigroupRep s => s -> IntSet -> IntSet
- asActions :: FiniteSemigroupRep s => s -> [Int] -> GeneratedAction
- localSubsemigroup :: FiniteSemigroupRep s => s -> Int -> FSMult
- localSubmonoids :: FiniteSemigroupRep s => s -> [FSMult]
- emee :: FiniteSemigroupRep s => s -> [FSMult]
- dual :: FiniteSemigroupRep s => s -> FSMult
- monoid :: FiniteSemigroupRep s => s -> FSMult
- projectedSubsemigroup :: FiniteSemigroupRep s => s -> FSMult
- ideal2 :: FiniteSemigroupRep s => s -> Int -> IntSet
- jleq :: FiniteSemigroupRep s => s -> Int -> Int -> Bool
- neutralElement :: FiniteSemigroupRep s => s -> Maybe Int
- adjoinOne :: FiniteSemigroupRep s => s -> FSMult
- zeroElement :: FiniteSemigroupRep s => s -> Maybe Int
- adjoinZero :: FiniteSemigroupRep s => s -> FSMult
- idempotents :: FiniteSemigroupRep s => s -> IntSet
- omega :: FiniteSemigroupRep s => s -> Int -> Int
- omegas :: FiniteSemigroupRep s => s -> [Int]
- lClasses :: FiniteSemigroupRep s => s -> [NonEmpty Int]
- rClasses :: FiniteSemigroupRep s => s -> [NonEmpty Int]
- module Data.Representation.FiniteSemigroup.Classification
- module Data.Representation.FiniteSemigroup.Order
- module Data.Representation.FiniteSemigroup.Variety
Representations of Finite Semigroups
class FiniteSemigroupRep a where Source #
A representation of a finite semigroup.
Unlike the Semigroup
typeclass,
this does not refer to a type whose objects
collectively form a semigroup.
Instead, it is a type
whose objects individually represent semigroups.
fsappend :: a -> Int -> Int -> Int Source #
The multiplication of the semigroup.
fstable :: a -> FSMult Source #
The multiplication table of the semigroup.
In the list at index x
, the element at index y
is xy
.
The number of elements in the semigroup.
The number of generators (always the first elements).
Instances
A semigroup presented as a multiplication table.
Use getTable
to extract the actual table;
this type is otherwise opaque.
data GeneratedAction Source #
A semigroup presented as a collection of actions.
The bases
are the given set of generating actions,
while the completion
is the set of other semigroup elements.
Instances
Generation by Elements
fromBases :: [[Int]] -> GeneratedAction Source #
Construct a semigroup from a set of generating transformations.
Transformations are given as functions over an initial segment
of the nonnegative integers.
The transformation [a,b,c]
maps 0 to a
, 1 to b
, and 2 to c
.
mapsInto :: GeneratedAction -> IntSet -> Int -> IntSet Source #
Returns the set of element indices in the given transformation that map the given object into the given set.
independentBases :: FiniteSemigroupRep s => s -> [[Int]] Source #
Find a small set of basis elements such that none can be written in terms of the others and the entire semigroup can be written in terms of these bases.
subsemigroup :: FiniteSemigroupRep s => s -> IntSet -> IntSet Source #
The subsemigroup of the given semigroup generated by the indicated elements.
asActions :: FiniteSemigroupRep s => s -> [Int] -> GeneratedAction Source #
Create an action semigroup whose bases correspond to the given elements; for each element \(i\), there is a basis representing the transformation \(f(x)=xi\).
Derived Semigroups
localSubsemigroup :: FiniteSemigroupRep s => s -> Int -> FSMult Source #
Return the local subsemigroup of the given semigroup \(S\) formed by wrapping elements with the given element \(i\). That is, all and only elements of the form \(isi\) for \(s\in S\) are included.
localSubmonoids :: FiniteSemigroupRep s => s -> [FSMult] Source #
Return the local subsemigroups of the given semigroup which happen to be monoids. These are the ones whose wrapping element is idempotent. If the semigroup itself is a monoid, it is in the list.
emee :: FiniteSemigroupRep s => s -> [FSMult] Source #
Return a list of subsemigroups of the form \(e\cdot M_e\cdot e\) for idempotent \(e\), where \(M_e\) is the set of elements generated by those elements greater than or equal to \(e\) with respect to the \(\mathcal{J}\)-order.
dual :: FiniteSemigroupRep s => s -> FSMult Source #
Reverse the multiplication of the semigroup.
monoid :: FiniteSemigroupRep s => s -> FSMult Source #
If the given semigroup is already a monoid, returns it. Otherwise, returns a monoid by adjoining a neutral element.
projectedSubsemigroup :: FiniteSemigroupRep s => s -> FSMult Source #
If the given semigroup is not a monoid, then it is returned as-is. Otherwise, the neutral element is removed if possible, that is, if it cannot be written in terms of other elements.
Ideals and Orders
Here, an order is a reflexive, transitive relation parameterized by semigroup.
ideal2 :: FiniteSemigroupRep s => s -> Int -> IntSet Source #
Given an element \(x\), return the set of elements representable as \(sxt\) for some \(s\) and \(t\) in \(S^1\), as a distinct ascending list.
jleq :: FiniteSemigroupRep s => s -> Int -> Int -> Bool Source #
The \(\mathcal{J}\)-order: \(x\leq y\) if and only if \(x=syt\) for some \(s\) and \(t\) in \(S^1\).
Special Kinds of Elements
neutralElement :: FiniteSemigroupRep s => s -> Maybe Int Source #
adjoinOne :: FiniteSemigroupRep s => s -> FSMult Source #
Insert a new element \(e\) such that for all elements \(x\), it holds that \(ex=x=xe\).
zeroElement :: FiniteSemigroupRep s => s -> Maybe Int Source #
adjoinZero :: FiniteSemigroupRep s => s -> FSMult Source #
Insert a new element \(e\) such that for all elements \(x\), it holds that \(ex=e=xe\).
idempotents :: FiniteSemigroupRep s => s -> IntSet Source #
Return the elements that square to themselves as an ascending list.
omega :: FiniteSemigroupRep s => s -> Int -> Int Source #
Return the unique idempotent power of the given element.
The result of omega s i
is the i
th element of omegas s
,
if i
is a valid element index.
omegas :: FiniteSemigroupRep s => s -> [Int] Source #
Return an action mapping semigroup elements to their unique idempotent powers.
lClasses :: FiniteSemigroupRep s => s -> [NonEmpty Int] Source #
Partition the elements of the semigroup \(S\) such that distinct elements \(x\) and \(y\) are in the same region if and only if there are \(s\) and \(t\) such that \(y=xs\) and \(x=yt\).