language-toolkit-1.2.0.0: A set of tools for analyzing languages via logic and automata
Copyright(c) 2021-2023 Dakotah Lambert
LicenseMIT
Safe HaskellSafe-Inferred
LanguageHaskell2010

LTK.Algebra

Description

This module centralizes definitions of some commonly used algebraic properties.

Since: 1.0

Synopsis

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 (n, [Symbol e]) e -> State (n, [Symbol e]) -> Set (State (n, [Symbol e])) #

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

emee :: (Ord n, Ord e) => FSA (n, [Symbol e]) e -> State (n, [Symbol e]) -> Set (State (n, [Symbol 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 (n, [Symbol e]) e -> State (n, [Symbol e]) -> Set (State (n, [Symbol e])) #

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

Other generation

syntacticOrder :: (Ord n, Ord e) => SynMon n e -> FSA [e] () #

Returns a machine whose states represent monoid elements and where a transition exists from \(p\) to \(q\) if and only if \(p\leq q\).

Since: 1.1

emblock :: (Ord n, Ord e) => SynMon n e -> SynMon Integer Integer #

Construct a monoid based on the idempotent paths as described by Straubing (1985). Elements are of the form \((e,esf,f)\) for idempotents \(e\) and \(f\) and arbitrary \(s\).

Since: 1.1

Powers

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

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

omega :: (Ord n, Ord e) => FSA (n, [Symbol e]) e -> State (n, [Symbol e]) -> State (n, [Symbol 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.