> {-# OPTIONS_HADDOCK show-extensions #-}
> {-|
> Module    : LTK.Decide.GLPT
> Copyright : (c) 2021 Dakotah Lambert
> License   : MIT

> This module implements an algorithm to decide whether a syntactic
> semigroup \(S\) is, on certain submonoids, Piecewise Testable (MePT).
> This is the case iff for each of its idempotents \(e\) it holds that
> \(eXe\) is \(\mathcal{J}\)-trivial, where X is the set generated by
> {ege : ugv=e for some u,v}.
>
> @since 1.0
> -}
> module LTK.Decide.GLPT (isGLPT, isGLPTM) where

> import qualified Data.Set as Set

> import LTK.FSA
> import LTK.Algebra

> -- |True iff the syntactic monoid of the automaton is in
> -- \(\mathbf{M_e J}\).
> -- This is a generalization of LPT in the same way that
> -- GLT is a generalization of LT.
> isGLPT :: (Ord n, Ord e) => FSA n e -> Bool
> isGLPT = isGLPTM . syntacticMonoid

J-trivial means MaM = MbM in all and only those cases where a=b
We're asking if X=e*M_e*e is J-trivial
That is, if for all a,b in X, XaX=XbX iff a=b.

It does not appear that a shortcut like that used to test for
local J-triviality is viable.  If it turns out to be, then this
file will shrink dramatically and this test will speed up quite
a bit.

> -- |True iff the given monoid is in \(\mathbf{M_e J}\).
> isGLPTM :: (Ord n, Ord e) => FSA (n, [Symbol e]) e -> Bool
> isGLPTM m = all f $ Set.toList i
>     where i = idempotents m
>           x = Set.toList . emee m
>           f e = isDistinct . map (g e) $ x e
>           g e h = Set.unions $ map (flip (follow m) qi)
>                   [label a ++ label h ++ label b
>                    | a <- x e, b <- x e]
>           qi = Set.findMin $ initials m
>           label = snd . nodeLabel

> isDistinct :: Eq a => [a] -> Bool
> isDistinct [] = True
> isDistinct (x:xs) = not (elem x xs) && isDistinct xs