| Copyright | (c) 2023 Dakotah Lambert |
|---|---|
| License | MIT |
| Safe Haskell | Safe-Inferred |
| Language | Haskell2010 |
LTK.DecideS
Description
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 #
True iff the semigroup is \(\mathcal{J}\)-trivial
Since: 1.2
Local classes
isDefs :: FiniteSemigroupRep s => s -> Bool #
True iff \(Se=e\) for idempotents \(e\).
Since: 1.2
isRDefs :: FiniteSemigroupRep s => s -> Bool #
True iff \(eS=e\) for idempotents \(e\).
Since: 1.2
isGDs :: FiniteSemigroupRep s => s -> Bool #
True iff the semigroup satisfies \(eSe=e\) for all idempotents \(e\).
Since: 1.2
isLTs :: FiniteSemigroupRep s => s -> Bool #
True iff the given semigroup is locally a semilattice.
Since: 1.2
isLTTs :: FiniteSemigroupRep s => s -> Bool #
True iff the semigroup recognizes an LTT stringset.
Since: 1.2
isLAcoms :: FiniteSemigroupRep s => s -> Bool #
True iff the semigroup recognizes a LAcom stringset.
Since: 1.2
Both Local and Piecewise
isAcoms :: FiniteSemigroupRep s => s -> Bool #
True iff the semigroup is aperiodic and commutative
Since: 1.2
isCBs :: FiniteSemigroupRep s => s -> Bool #
True iff the semigroup is a semilattice.
Since: 1.2
isGLTs :: FiniteSemigroupRep s => s -> Bool #
True iff the semigroup lies in \(M_e J_1\).
Since: 1.2
isLPTs :: FiniteSemigroupRep s => s -> Bool #
True iff the semigroup is locally \(\mathcal{J}\)-trivial.
Since: 1.2
isGLPTs :: FiniteSemigroupRep s => s -> Bool #
True iff the given semigroup is in \(\mathbf{M_e J}\).
Since: 1.2
isSFs :: FiniteSemigroupRep s => s -> Bool #
True iff the semigroup is aperiodic.
Since: 1.2
isDot1s :: FiniteSemigroupRep s => s -> Bool #
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 #
Definite on the projected subsemigroup.
Since: 1.2
isTRDefs :: FiniteSemigroupRep s => s -> Bool #
Reverse definite on the projected subsemigroup.
Since: 1.2
isTGDs :: FiniteSemigroupRep s => s -> Bool #
True iff the projected subsemigroup satisfies eSe=e
Since: 1.2
isTLTs :: FiniteSemigroupRep s => s -> Bool #
True iff the semigroup recognizes a TLT stringset.
Since: 1.2
isTLTTs :: FiniteSemigroupRep s => s -> Bool #
True iff the semigroup recognizes a TLTT stringset.
Since: 1.2
isTLAcoms :: FiniteSemigroupRep s => s -> Bool #
True iff the semigroup recognizes a TLAcom stringset.
Since: 1.2
isTLPTs :: FiniteSemigroupRep s => s -> Bool #
True iff the semigroup recognizes a TLPT stringset.
Since: 1.2
isMTFs :: FiniteSemigroupRep s => s -> Bool #
True iff the semigroup is aperiodic and satisfies \(x^{\omega}y=yx^{\omega}\).
Since: 1.2
isMTDefs :: FiniteSemigroupRep s => s -> Bool #
True iff the semigroup satisifes \(xyx^{\omega}=yx^{\omega}\).
Since: 1.2
isMTRDefs :: FiniteSemigroupRep s => s -> Bool #
True iff the semigroup satisifes \(x^{\omega}yx=x^{\omega}y\).
Since: 1.2
isMTGDs :: FiniteSemigroupRep s => s -> Bool #
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 #
True iff the semigroup is a band.
Since: 1.2
isLBs :: FiniteSemigroupRep s => s -> Bool #
True iff the semigroup is locally a band.
Since: 1.2
isTLBs :: FiniteSemigroupRep s => s -> Bool #
True iff the semigroup is locally a band on some tier.
Since: 1.2
Two-Variable Logics
isFO2s :: FiniteSemigroupRep s => s -> Bool #
True iff the monoid represents a language in \(\mathrm{FO}^{2}[<]\).
Since: 1.2
isFO2Bs :: FiniteSemigroupRep s => s -> Bool #
True iff the semigroup represents a stringset
that satisfies isFO2B.
Since: 1.2
isFO2Ss :: FiniteSemigroupRep s => s -> Bool #
True iff the local submonoids are in \(\mathrm{FO}^{2}[<]\). This means the whole is in \(\mathrm{FO}^{2}[<,+1]\).
Since: 1.2