Copyright | (c) 2023 Dakotah Lambert |
---|---|
License | MIT |
Safe Haskell | Safe-Inferred |
Language | Haskell2010 |
Functions used for deciding the complexity class of a monoid.
Each complexity class for which these operations are implemented
has a separate Decide.classM module as well. Many of the functions
in LTK.Decide
use these functions internally, so using these
directly prevents rederiving the monoid when many tests are desired.
One may note that LTK.Decide
contains strictly more tests.
The classes not closed under complementation are not classified
by their syntactic monoids or semigroups, but by properties of
the automaton from which it was derived.
Since: 1.2
Synopsis
- isPTs :: FiniteSemigroupRep s => s -> Bool
- isDefs :: FiniteSemigroupRep s => s -> Bool
- isRDefs :: FiniteSemigroupRep s => s -> Bool
- isGDs :: FiniteSemigroupRep s => s -> Bool
- isLTs :: FiniteSemigroupRep s => s -> Bool
- isLTTs :: FiniteSemigroupRep s => s -> Bool
- isLAcoms :: FiniteSemigroupRep s => s -> Bool
- isAcoms :: FiniteSemigroupRep s => s -> Bool
- isCBs :: FiniteSemigroupRep s => s -> Bool
- isGLTs :: FiniteSemigroupRep s => s -> Bool
- isLPTs :: FiniteSemigroupRep s => s -> Bool
- isGLPTs :: FiniteSemigroupRep s => s -> Bool
- isSFs :: FiniteSemigroupRep s => s -> Bool
- isDot1s :: FiniteSemigroupRep s => s -> Bool
- isTDefs :: FiniteSemigroupRep s => s -> Bool
- isTRDefs :: FiniteSemigroupRep s => s -> Bool
- isTGDs :: FiniteSemigroupRep s => s -> Bool
- isTLTs :: FiniteSemigroupRep s => s -> Bool
- isTLTTs :: FiniteSemigroupRep s => s -> Bool
- isTLAcoms :: FiniteSemigroupRep s => s -> Bool
- isTLPTs :: FiniteSemigroupRep s => s -> Bool
- isMTFs :: FiniteSemigroupRep s => s -> Bool
- isMTDefs :: FiniteSemigroupRep s => s -> Bool
- isMTRDefs :: FiniteSemigroupRep s => s -> Bool
- isMTGDs :: FiniteSemigroupRep s => s -> Bool
- isBs :: FiniteSemigroupRep s => s -> Bool
- isLBs :: FiniteSemigroupRep s => s -> Bool
- isTLBs :: FiniteSemigroupRep s => s -> Bool
- isFO2s :: FiniteSemigroupRep s => s -> Bool
- isFO2Bs :: FiniteSemigroupRep s => s -> Bool
- isFO2Ss :: FiniteSemigroupRep s => s -> Bool
Piecewise classes
isPTs :: FiniteSemigroupRep s => s -> Bool Source #
True iff the semigroup is \(\mathcal{J}\)-trivial
Since: 1.2
Local classes
isDefs :: FiniteSemigroupRep s => s -> Bool Source #
True iff \(Se=e\) for idempotents \(e\).
Since: 1.2
isRDefs :: FiniteSemigroupRep s => s -> Bool Source #
True iff \(eS=e\) for idempotents \(e\).
Since: 1.2
isGDs :: FiniteSemigroupRep s => s -> Bool Source #
True iff the semigroup satisfies \(eSe=e\) for all idempotents \(e\).
Since: 1.2
isLTs :: FiniteSemigroupRep s => s -> Bool Source #
True iff the given semigroup is locally a semilattice.
Since: 1.2
isLTTs :: FiniteSemigroupRep s => s -> Bool Source #
True iff the semigroup recognizes an LTT stringset.
Since: 1.2
isLAcoms :: FiniteSemigroupRep s => s -> Bool Source #
True iff the semigroup recognizes a LAcom stringset.
Since: 1.2
Both Local and Piecewise
isAcoms :: FiniteSemigroupRep s => s -> Bool Source #
True iff the semigroup is aperiodic and commutative
Since: 1.2
isCBs :: FiniteSemigroupRep s => s -> Bool Source #
True iff the semigroup is a semilattice.
Since: 1.2
isGLTs :: FiniteSemigroupRep s => s -> Bool Source #
True iff the semigroup lies in \(M_e J_1\).
Since: 1.2
isLPTs :: FiniteSemigroupRep s => s -> Bool Source #
True iff the semigroup is locally \(\mathcal{J}\)-trivial.
Since: 1.2
isGLPTs :: FiniteSemigroupRep s => s -> Bool Source #
True iff the given semigroup is in \(\mathbf{M_e J}\).
Since: 1.2
isSFs :: FiniteSemigroupRep s => s -> Bool Source #
True iff the semigroup is aperiodic.
Since: 1.2
isDot1s :: FiniteSemigroupRep s => s -> Bool Source #
True iff the semigroup recognizes a dot-depth one stringset. That is, for idempotents \(e\) and \(f\) and elements \(a\), \(b\), \(c\) and \(d\), it holds that ((eafb)^{omega}eafde(cfde)^{omega} = (eafb)^{omega}e(cfde)^{omega}).
Tier-based generalizations
isTDefs :: FiniteSemigroupRep s => s -> Bool Source #
Definite on the projected subsemigroup.
Since: 1.2
isTRDefs :: FiniteSemigroupRep s => s -> Bool Source #
Reverse definite on the projected subsemigroup.
Since: 1.2
isTGDs :: FiniteSemigroupRep s => s -> Bool Source #
True iff the projected subsemigroup satisfies eSe=e
Since: 1.2
isTLTs :: FiniteSemigroupRep s => s -> Bool Source #
True iff the semigroup recognizes a TLT stringset.
Since: 1.2
isTLTTs :: FiniteSemigroupRep s => s -> Bool Source #
True iff the semigroup recognizes a TLTT stringset.
Since: 1.2
isTLAcoms :: FiniteSemigroupRep s => s -> Bool Source #
True iff the semigroup recognizes a TLAcom stringset.
Since: 1.2
isTLPTs :: FiniteSemigroupRep s => s -> Bool Source #
True iff the semigroup recognizes a TLPT stringset.
Since: 1.2
isMTFs :: FiniteSemigroupRep s => s -> Bool Source #
True iff the semigroup is aperiodic and satisfies \(x^{\omega}y=yx^{\omega}\).
Since: 1.2
isMTDefs :: FiniteSemigroupRep s => s -> Bool Source #
True iff the semigroup satisifes \(xyx^{\omega}=yx^{\omega}\).
Since: 1.2
isMTRDefs :: FiniteSemigroupRep s => s -> Bool Source #
True iff the semigroup satisifes \(x^{\omega}yx=x^{\omega}y\).
Since: 1.2
isMTGDs :: FiniteSemigroupRep s => s -> Bool Source #
True iff the semigroup satisfies \(x^{\omega}uxvx^{\omega}=x^{\omega}uvx^{\omega}\) and \(x^{\omega}uxzvz^{\omega}=x^{\omega}uzxvz^{\omega}\). Thanks to Almeida (1995) for the simplification.
Since: 1.2
Others between CB and G
isBs :: FiniteSemigroupRep s => s -> Bool Source #
True iff the semigroup is a band.
Since: 1.2
isLBs :: FiniteSemigroupRep s => s -> Bool Source #
True iff the semigroup is locally a band.
Since: 1.2
isTLBs :: FiniteSemigroupRep s => s -> Bool Source #
True iff the semigroup is locally a band on some tier.
Since: 1.2
Two-Variable Logics
isFO2s :: FiniteSemigroupRep s => s -> Bool Source #
True iff the monoid represents a language in \(\mathrm{FO}^{2}[<]\).
Since: 1.2
isFO2Bs :: FiniteSemigroupRep s => s -> Bool Source #
True iff the semigroup represents a stringset
that satisfies isFO2B
.
Since: 1.2
isFO2Ss :: FiniteSemigroupRep s => s -> Bool Source #
True iff the local submonoids are in \(\mathrm{FO}^{2}[<]\). This means the whole is in \(\mathrm{FO}^{2}[<,+1]\).
Since: 1.2