LTK.DecideM

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.0

Piecewise classes

isPTM :: (Ord n, Ord e) => SynMon n e -> Bool

True iff the monoid is \(\mathcal{J}\)-trivial

Since: 1.0

Local classes

isDefM :: (Ord n, Ord e) => SynMon n e -> Bool

True iff \(Se=e\) for idempotents \(e\).

isRDefM :: (Ord n, Ord e) => SynMon n e -> Bool

True iff \(eS=e\) for idempotents \(e\).

isGDM :: (Ord n, Ord e) => SynMon n e -> Bool

True iff the monoid satisfies \(eSe=e\) for all idempotents \(e\).

isLTM :: (Ord n, Ord e) => SynMon n e -> Bool

True iff the given monoid is locally a semilattice.

Since: 1.0

isLTTM :: (Ord n, Ord e) => SynMon n e -> Bool

True iff the monoid recognizes an LTT stringset.

Since: 1.0

Both Local and Piecewise

isCBM :: (Ord n, Ord e) => SynMon n e -> Bool

True iff the monoid is a semilattice.

isGLTM :: (Ord n, Ord e) => FSA (n, [Symbol e]) e -> Bool

True iff the monoid satisfies the generalized local testabiltiy condition.

isLPTM :: (Ord n, Ord e) => SynMon n e -> Bool

True iff the monoid is locally \(\mathcal{J}\)-trivial.

isGLPTM :: (Ord n, Ord e) => FSA (n, [Symbol e]) e -> Bool

True iff the given monoid is in \(\mathbf{M_e J}\).

isSFM :: (Ord n, Ord e) => SynMon n e -> Bool

True iff the monoid is aperiodic.

Since: 1.0

Tier-based generalizations

isTDefM :: (Ord n, Ord e) => SynMon n e -> Bool

Definite on the projected subsemigroup.

isTRDefM :: (Ord n, Ord e) => SynMon n e -> Bool

Reverse definite on the projected subsemigroup.

isTGDM :: (Ord n, Ord e) => SynMon n e -> Bool

True iff the projected subsemigroup satisfies eSe=e

isTLTM :: (Ord n, Ord e) => SynMon n e -> Bool

True iff the monoid recognizes a TLT stringset.

Since: 1.0

isTLTTM :: (Ord n, Ord e) => SynMon n e -> Bool

True iff the monoid recognizes a TLTT stringset.

Since: 1.0

isTLPTM :: (Ord n, Ord e) => SynMon n e -> Bool

True iff the monoid recognizes a TLPT stringset.

Others between CB and G

isBM :: (Ord n, Ord e) => SynMon n e -> Bool

True iff the monoid is a band.

isLBM :: (Ord n, Ord e) => SynMon n e -> Bool

True iff the monoid is locally a band.

isTLBM :: (Ord n, Ord e) => SynMon n e -> Bool

True iff the monoid is locally a band on some tier.

Two-Variable Logics

isFO2M :: (Ord n, Ord e) => SynMon n e -> Bool

True iff the monoid represents a language in \(\mathrm{FO}^{2}[<]\).

isFO2BM :: (Ord n, Ord e) => SynMon n e -> Bool

True iff the monoid represents a stringset that satisfies isFO2B.

isFO2SM :: (Ord n, Ord e) => SynMon n e -> Bool

True iff the local subsemigroups are in \(\mathrm{FO}^{2}[<]\). This means the whole is in \(\mathrm{FO}^{2}[<,+1]\).