LTK.Algebra

This module centralizes definitions of some commonly used algebraic properties.

Since: 1.0

Type

type SynMon n e = FSA ([Maybe n], [Symbol e]) e

A simpler way to denote syntactic monoids in type signatures.

Tests

isCommutative :: (Ord n, Ord e) => FSA (n, [Symbol e]) e -> Set (State (n, [Symbol e])) -> Bool

True iff the supplied elements commute with one another in the provided monoid.

Generated Submonoids and Subsemigroups

me :: (Ord n, Ord e) => FSA (S n e) e -> T n e -> Set (T n e)

For a given idempotent \(e\), return the set generated by \(\{m : (\exists u,v)[umv=e]\}\).

emee :: (Ord n, Ord e) => FSA (S n e) e -> T n e -> Set (T n e)

For a given idempotent \(e\), return the set me monoid e multiplied on the left and right by \(e\).

ese :: (Ord n, Ord e) => FSA (S n e) e -> T n e -> Set (T n e)

The semigroup multiplied on the left and right by the given idempotent.

Powers

idempotents :: (Ord n, Ord e) => FSA (n, [Symbol e]) e -> Set (T n e)

All elements \(e\) of the given monoid such that \(e*e=e\). Except the identity element. Add that manually if you need it.

omega :: (Ord n, Ord e) => FSA (S n e) e -> T n e -> T n e

omega monoid s is the unique element \(t\) where \(t*t\) = \(t\) and \(t\) is in \(\{s, s^2, s^3, \ldots\}\). In other words, \(t\) is the unique idempotent element in this set. This method used here assumes monoid is aperiodic and finite and uses this to skip many otherwise necessary checks.