Copyright	(c) 2023 Dakotah Lambert
License	MIT
Safe Haskell	Safe-Inferred
Language	Haskell2010

LTK.DecideS

Contents

Piecewise classes
Local classes
Both Local and Piecewise
Tier-based generalizations
Others between CB and G
Two-Variable Logics

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