\documentclass[12pt,twoside]{article}

\usepackage[letterpaper,margin=1in]{geometry}
\usepackage[T1]{fontenc}
\usepackage[english]{babel}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{draftnote}\draftcp
\usepackage{ec-phonology}
\usepackage{mathtools}
\usepackage{microtype}

\input litHaskellcode

\author{JRogers}
\title{ExtractSL}
\date{}

\begin{document}

\maketitle\thispagestyle{empty}
Note: A major difficulty in working with this module is the fact that
sometimes, such as in \texttt{FSA n e} `\texttt{e}' is the base type of
Symbols, so the actual edge label type is \texttt{Symbol e}.  This is also
true in the definition of \texttt{Path} and {\texttt ForbiddenSubstrings}.
At others, such as the definition of\texttt{ForbiddenPaths} it is bound to
\texttt{Symbol e}.  This creates conflicts.

Functions for
\begin{itemize}
\item Determining if the stringset recongized by an automaton is $\SL$ and, if
  so, determining $k$.
\item Extracting the sets of Forbidden Initial, Free and Final Factors,
  and Forbidden Words that (partially) define that stringset.
\item Generating an automaton that provides an $\SL$ approximation of the
  stringset recognized by an automaton.
\item andere Dinge
\end{itemize}

Forbidden factors and words are explained in Rogers and Lambert,
MoL'17 as is the notion of an $\SL$ approximation of a non-$\SL$ stringset.


> {-# OPTIONS_HADDOCK show-extensions #-}
> {-# Language
>   MultiParamTypeClasses
>   #-}
> {-|
> Module    : LTK.Extract.SL
> Copyright : (c) 2017-2019 Jim Rogers and Dakotah Lambert
> License   : MIT
>
> Find forbidden substrings of an automaton.
> Formerly known as @LTK.ExtractSL@.
>
> @since 0.2
> -}
> module LTK.Extract.SL
>        ( ForbiddenSubstrings(..)
>        , ForbiddenPaths(..)
>        , TaggedSubstring(..)
>        -- *Extracting forbidden substrings
>        , factorsFromPaths
>        , forbiddenSubstrings
>        -- *Building automata
>        , buildFSA
>        -- *Determining SL
>        , isSL
>        , slQ
>        ) where

> import Control.DeepSeq (NFData)
> import Data.Set (Set)
> import qualified Data.List as List
> import qualified Data.Set as Set

> import LTK.Factors
> import LTK.FSA
> import LTK.Traversals

\section*{Determining $\SL{k}$}
This is an implementation of the powerset graph based algorithm given in
Edlefsen, et al., MCURCSM'08 and sketched in Rogers and Lambert, MoL'17.
Since we are often working with the full powerset graph anyway, we do not use
the polynomial-time pair-graph version.


> -- |Returns @True@ iff the stringset represented by the given 'FSA'
> -- is Strictly Local, that is,
> -- if it satisfies Suffix-Substition Closure for
> -- some specific factor size \(k\).
> isSL :: (Ord e, Ord n) => FSA n e -> Bool
> isSL :: FSA n e -> Bool
isSL = (Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
> Integer
0) (Integer -> Bool) -> (FSA n e -> Integer) -> FSA n e -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. FSA n e -> Integer
forall e n. (Ord e, Ord n) => FSA n e -> Integer
slQ

> -- |Returns the smallest factor size for which
> -- the stringset represented by the given 'FSA'
> -- satisfies Suffix-Substitution Closure,
> -- or @0@ if there is no such \(k\).
> slQ :: (Ord e, Ord n) => FSA n e -> Integer
> slQ :: FSA n e -> Integer
slQ FSA n e
fsa = FSA (Set n) e -> Integer
forall e n. (Ord e, Ord n) => FSA (Set n) e -> Integer
slPSGQ (FSA n e -> FSA (Set n) e
forall e n. (Ord e, Ord n) => FSA n e -> FSA (Set n) e
powersetGraph FSA n e
fsa)

> -- |slQ with precomputed PSG
> slPSGQ :: (Ord e, Ord n) => FSA (Set n) e -> Integer
> slPSGQ :: FSA (Set n) e -> Integer
slPSGQ FSA (Set n) e
psg = FSA (Set n) e -> Set (Path (Set n) e) -> Integer -> Integer
forall e n.
(Ord e, Ord n) =>
FSA (Set n) e -> Set (Path (Set n) e) -> Integer -> Integer
slTraversal FSA (Set n) e
psg (FSA (Set n) e -> Set (Path (Set n) e)
forall e n. (Ord e, Ord n) => FSA n e -> Set (Path n e)
initialsPaths FSA (Set n) e
psg) Integer
0

slTraversal is a top-down traversal of the powerset graph which
terminates when either a non-singleton cycle is encountered, or all paths
terminate in (at most) singleton state sets.  In the latter case the
corresponding stringset is $\SL{k}$, where $k$ is the length of the longest
path to a singleton stateset plus $1$, and the function evaluates to $k$.
In the former case it evaluates to $0$.

> slTraversal :: (Ord e, Ord n) =>
>                FSA (Set n) e ->         -- PSG
>                Set(Path (Set n) e) ->   -- Current frontier
>                Integer ->               -- Depth of current frontier
>                Integer
> slTraversal :: FSA (Set n) e -> Set (Path (Set n) e) -> Integer -> Integer
slTraversal FSA (Set n) e
psg Set (Path (Set n) e)
ps Integer
k
>     | Set (Path (Set n) e) -> Bool
forall c a. Container c a => c -> Bool
isEmpty Set (Path (Set n) e)
ps  =  Integer
k Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
+ Integer
1
>     | Bool
hasCycle    =  Integer
0
>     | Bool
someSingle  =  FSA (Set n) e -> Set (Path (Set n) e) -> Integer -> Integer
forall e n.
(Ord e, Ord n) =>
FSA (Set n) e -> Set (Path (Set n) e) -> Integer -> Integer
slTraversal FSA (Set n) e
psg (Set (Path (Set n) e)
-> Set (Path (Set n) e) -> Set (Path (Set n) e)
forall c a. Container c a => c -> c -> c
union Set (Path (Set n) e)
live Set (Path (Set n) e)
ps') (Integer -> Integer -> Integer
forall a. Ord a => a -> a -> a
max Integer
k (Integer -> Integer) -> Integer -> Integer
forall a b. (a -> b) -> a -> b
$ Path (Set n) e -> Integer
forall n e. Path n e -> Integer
depth Path (Set n) e
p Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
+ Integer
1)
>     | Bool
otherwise   =  FSA (Set n) e -> Set (Path (Set n) e) -> Integer -> Integer
forall e n.
(Ord e, Ord n) =>
FSA (Set n) e -> Set (Path (Set n) e) -> Integer -> Integer
slTraversal FSA (Set n) e
psg (Set (Path (Set n) e)
-> Set (Path (Set n) e) -> Set (Path (Set n) e)
forall c a. Container c a => c -> c -> c
union Set (Path (Set n) e)
live Set (Path (Set n) e)
ps') Integer
k
>     where (Path (Set n) e
p, Set (Path (Set n) e)
ps')    =  Set (Path (Set n) e) -> (Path (Set n) e, Set (Path (Set n) e))
forall (l :: * -> *) a. Linearizable l => l a -> (a, l a)
choose Set (Path (Set n) e)
ps
>           exts :: Set (Path (Set n) e)
exts        =  FSA (Set n) e -> Path (Set n) e -> Set (Path (Set n) e)
forall e n. (Ord e, Ord n) => FSA n e -> Path n e -> Set (Path n e)
extensions FSA (Set n) e
psg Path (Set n) e
p
>           someSingle :: Bool
someSingle  =  ((Path (Set n) e -> Bool) -> Set (Path (Set n) e) -> Bool)
-> Set (Path (Set n) e) -> (Path (Set n) e -> Bool) -> Bool
forall a b c. (a -> b -> c) -> b -> a -> c
flip (Path (Set n) e -> Bool) -> Set (Path (Set n) e) -> Bool
forall (s :: * -> *) a. Collapsible s => (a -> Bool) -> s a -> Bool
anyS Set (Path (Set n) e)
exts ((Path (Set n) e -> Bool) -> Bool)
-> (Path (Set n) e -> Bool) -> Bool
forall a b. (a -> b) -> a -> b
$
>                          Bool -> (State (Set n) -> Bool) -> Maybe (State (Set n)) -> Bool
forall b a. b -> (a -> b) -> Maybe a -> b
maybe Bool
False ((Integer
1 Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
==) (Integer -> Bool)
-> (State (Set n) -> Integer) -> State (Set n) -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Set n -> Integer
forall (c :: * -> *) b. Collapsible c => c b -> Integer
isize (Set n -> Integer)
-> (State (Set n) -> Set n) -> State (Set n) -> Integer
forall b c a. (b -> c) -> (a -> b) -> a -> c
. State (Set n) -> Set n
forall n. State n -> n
nodeLabel) (Maybe (State (Set n)) -> Bool)
-> (Path (Set n) e -> Maybe (State (Set n)))
-> Path (Set n) e
-> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
>                          Path (Set n) e -> Maybe (State (Set n))
forall n e. Path n e -> Maybe (State n)
endstate
>           live :: Set (Path (Set n) e)
live        =  ((Path (Set n) e -> Bool)
 -> Set (Path (Set n) e) -> Set (Path (Set n) e))
-> Set (Path (Set n) e)
-> (Path (Set n) e -> Bool)
-> Set (Path (Set n) e)
forall a b c. (a -> b -> c) -> b -> a -> c
flip (Path (Set n) e -> Bool)
-> Set (Path (Set n) e) -> Set (Path (Set n) e)
forall (s :: * -> *) a.
(Collapsible s, Container (s a) a) =>
(a -> Bool) -> s a -> s a
keep Set (Path (Set n) e)
exts ((Path (Set n) e -> Bool) -> Set (Path (Set n) e))
-> (Path (Set n) e -> Bool) -> Set (Path (Set n) e)
forall a b. (a -> b) -> a -> b
$
>                          Bool -> (State (Set n) -> Bool) -> Maybe (State (Set n)) -> Bool
forall b a. b -> (a -> b) -> Maybe a -> b
maybe Bool
False ((Integer
1 Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
<) (Integer -> Bool)
-> (State (Set n) -> Integer) -> State (Set n) -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Set n -> Integer
forall (c :: * -> *) b. Collapsible c => c b -> Integer
isize (Set n -> Integer)
-> (State (Set n) -> Set n) -> State (Set n) -> Integer
forall b c a. (b -> c) -> (a -> b) -> a -> c
. State (Set n) -> Set n
forall n. State n -> n
nodeLabel) (Maybe (State (Set n)) -> Bool)
-> (Path (Set n) e -> Maybe (State (Set n)))
-> Path (Set n) e
-> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
>                          Path (Set n) e -> Maybe (State (Set n))
forall n e. Path n e -> Maybe (State n)
endstate
>           hasCycle :: Bool
hasCycle    =  ((Path (Set n) e -> Bool) -> Set (Path (Set n) e) -> Bool)
-> Set (Path (Set n) e) -> (Path (Set n) e -> Bool) -> Bool
forall a b c. (a -> b -> c) -> b -> a -> c
flip (Path (Set n) e -> Bool) -> Set (Path (Set n) e) -> Bool
forall (s :: * -> *) a. Collapsible s => (a -> Bool) -> s a -> Bool
anyS Set (Path (Set n) e)
live ((Path (Set n) e -> Bool) -> Bool)
-> (Path (Set n) e -> Bool) -> Bool
forall a b. (a -> b) -> a -> b
$
>                          Bool -> (State (Set n) -> Bool) -> Maybe (State (Set n)) -> Bool
forall b a. b -> (a -> b) -> Maybe a -> b
maybe Bool
False (Multiset (State (Set n)) -> State (Set n) -> Bool
forall c a. (Container c a, Eq a) => c -> a -> Bool
isIn (Path (Set n) e -> Multiset (State (Set n))
forall n e. Path n e -> Multiset (State n)
stateMultiset Path (Set n) e
p)) (Maybe (State (Set n)) -> Bool)
-> (Path (Set n) e -> Maybe (State (Set n)))
-> Path (Set n) e
-> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
>                          Path (Set n) e -> Maybe (State (Set n))
forall n e. Path n e -> Maybe (State n)
endstate

\section*{Extracting Forbidden Factors}
The algorithms for gathering Forbidden Initial, Free and Final Factors all
involve a traversal of the powerset graph of a DFA.  In the case that the
corresponding stringset is $\SL$ the traversals are guaranteed to terminate.
If it is not, this is not the case.  In practice, it is often sufficient to
limit the traversals to acyclic paths, but in general that is not the case
either.

The cycles of the PSG, other than cycles of singletons, embody, in a strong
sense, the non-$\SL$ aspects of the stringset; paths including cycles of
non-singletons are witnesses to non-closure under SSC.  In order to isolate
these aspects, it is, in principle, sufficient to explore the sequence of
traversals in which cycles are taken increasingly many times, until the set of
cycles occurring in the paths converges.  To support this, we provide
versions of these traversals which are paramaterized by a bound on the number
of times any state is re-entered during the traversal.


If $\f{psg}$ is the powerset graph of a DFA, then $\f{psgQ}\;\f{psg}$ is the
label of its initial state, i.e., the stateset of the original DFA.  Note that
the there is exactly one initial state of a PSG, so this is just lowering the
type of a singleton set.

> psgQ :: (Ord a, Ord b) => FSA (Set b) a -> State (Set b)
> psgQ :: FSA (Set b) a -> State (Set b)
psgQ = Set (State (Set b)) -> State (Set b)
forall a. Set a -> a
Set.findMin (Set (State (Set b)) -> State (Set b))
-> (FSA (Set b) a -> Set (State (Set b)))
-> FSA (Set b) a
-> State (Set b)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. FSA (Set b) a -> Set (State (Set b))
forall n e. FSA n e -> Set (State n)
initials


%% {--------------------------------------------------------------------------}
%%    Forbidden Factors
%%    Forbidden Factors of fsa are the
%%      initial forbidden factors of DFA, free forbidden factors of psGraph,
%%      final forbidden factors of psGraph and forbidden words of DFA.
%%    Initial FF are the labels of acyclic paths from the start state to the
%%      sink state in the minimal but not trimmed DFA.  These are minimal iff
%%      they contain no Free FF.
%%    Free FF are labels of paths Q --> $\emptyset$ in psGraph
%%       These are minimal iff they contain no other Free FF as a suffix
%%    Final FF are labels of paths Q --> state sets in the psGraph other than
%%      $\emptyset$ that are disjoint with the final states of the DFA.
%%      These are minimal iff they contain no other Final FF as a suffix.
%%    Forbidden words are labels of paths from the start state to a
%%      non-accepting state in the DFA that do not include an Initial FF as a
%%      prefix, a Free FF as a substring or a Final FF as a suffix.  For this
%%      set to be bounded, the stringset has to be SL, in which case the bound
%%      is k.

> -- |A convenience-type for declaring collections of  forbidden substrings.
> --  The member types are (lists of) the raw alphabet type (not (Symbol .))
> data ForbiddenSubstrings e
>     = ForbiddenSubstrings
>       { -- |Symbols that actually label transitions
>         ForbiddenSubstrings e -> Set e
attestedUnits      ::  Set e
>         -- |Sequences of symbols that cannot occur as words
>       , ForbiddenSubstrings e -> Set [e]
forbiddenWords     ::  Set [e]
>         -- |Sequences of symbols that cannot occur initially
>       , ForbiddenSubstrings e -> Set [e]
forbiddenInitials  ::  Set [e]
>         -- |Sequences of symbols that cannot occur anywhere
>       , ForbiddenSubstrings e -> Set [e]
forbiddenFrees     ::  Set [e]
>         -- |Sequences of symbols that cannot occur finally
>       , ForbiddenSubstrings e -> Set [e]
forbiddenFinals    ::  Set [e]
>       }
>     deriving (ForbiddenSubstrings e -> ForbiddenSubstrings e -> Bool
(ForbiddenSubstrings e -> ForbiddenSubstrings e -> Bool)
-> (ForbiddenSubstrings e -> ForbiddenSubstrings e -> Bool)
-> Eq (ForbiddenSubstrings e)
forall e.
Eq e =>
ForbiddenSubstrings e -> ForbiddenSubstrings e -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: ForbiddenSubstrings e -> ForbiddenSubstrings e -> Bool
$c/= :: forall e.
Eq e =>
ForbiddenSubstrings e -> ForbiddenSubstrings e -> Bool
== :: ForbiddenSubstrings e -> ForbiddenSubstrings e -> Bool
$c== :: forall e.
Eq e =>
ForbiddenSubstrings e -> ForbiddenSubstrings e -> Bool
Eq, Eq (ForbiddenSubstrings e)
Eq (ForbiddenSubstrings e)
-> (ForbiddenSubstrings e -> ForbiddenSubstrings e -> Ordering)
-> (ForbiddenSubstrings e -> ForbiddenSubstrings e -> Bool)
-> (ForbiddenSubstrings e -> ForbiddenSubstrings e -> Bool)
-> (ForbiddenSubstrings e -> ForbiddenSubstrings e -> Bool)
-> (ForbiddenSubstrings e -> ForbiddenSubstrings e -> Bool)
-> (ForbiddenSubstrings e
    -> ForbiddenSubstrings e -> ForbiddenSubstrings e)
-> (ForbiddenSubstrings e
    -> ForbiddenSubstrings e -> ForbiddenSubstrings e)
-> Ord (ForbiddenSubstrings e)
ForbiddenSubstrings e -> ForbiddenSubstrings e -> Bool
ForbiddenSubstrings e -> ForbiddenSubstrings e -> Ordering
ForbiddenSubstrings e
-> ForbiddenSubstrings e -> ForbiddenSubstrings e
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
forall e. Ord e => Eq (ForbiddenSubstrings e)
forall e.
Ord e =>
ForbiddenSubstrings e -> ForbiddenSubstrings e -> Bool
forall e.
Ord e =>
ForbiddenSubstrings e -> ForbiddenSubstrings e -> Ordering
forall e.
Ord e =>
ForbiddenSubstrings e
-> ForbiddenSubstrings e -> ForbiddenSubstrings e
min :: ForbiddenSubstrings e
-> ForbiddenSubstrings e -> ForbiddenSubstrings e
$cmin :: forall e.
Ord e =>
ForbiddenSubstrings e
-> ForbiddenSubstrings e -> ForbiddenSubstrings e
max :: ForbiddenSubstrings e
-> ForbiddenSubstrings e -> ForbiddenSubstrings e
$cmax :: forall e.
Ord e =>
ForbiddenSubstrings e
-> ForbiddenSubstrings e -> ForbiddenSubstrings e
>= :: ForbiddenSubstrings e -> ForbiddenSubstrings e -> Bool
$c>= :: forall e.
Ord e =>
ForbiddenSubstrings e -> ForbiddenSubstrings e -> Bool
> :: ForbiddenSubstrings e -> ForbiddenSubstrings e -> Bool
$c> :: forall e.
Ord e =>
ForbiddenSubstrings e -> ForbiddenSubstrings e -> Bool
<= :: ForbiddenSubstrings e -> ForbiddenSubstrings e -> Bool
$c<= :: forall e.
Ord e =>
ForbiddenSubstrings e -> ForbiddenSubstrings e -> Bool
< :: ForbiddenSubstrings e -> ForbiddenSubstrings e -> Bool
$c< :: forall e.
Ord e =>
ForbiddenSubstrings e -> ForbiddenSubstrings e -> Bool
compare :: ForbiddenSubstrings e -> ForbiddenSubstrings e -> Ordering
$ccompare :: forall e.
Ord e =>
ForbiddenSubstrings e -> ForbiddenSubstrings e -> Ordering
$cp1Ord :: forall e. Ord e => Eq (ForbiddenSubstrings e)
Ord, Int -> ForbiddenSubstrings e -> ShowS
[ForbiddenSubstrings e] -> ShowS
ForbiddenSubstrings e -> String
(Int -> ForbiddenSubstrings e -> ShowS)
-> (ForbiddenSubstrings e -> String)
-> ([ForbiddenSubstrings e] -> ShowS)
-> Show (ForbiddenSubstrings e)
forall e. Show e => Int -> ForbiddenSubstrings e -> ShowS
forall e. Show e => [ForbiddenSubstrings e] -> ShowS
forall e. Show e => ForbiddenSubstrings e -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [ForbiddenSubstrings e] -> ShowS
$cshowList :: forall e. Show e => [ForbiddenSubstrings e] -> ShowS
show :: ForbiddenSubstrings e -> String
$cshow :: forall e. Show e => ForbiddenSubstrings e -> String
showsPrec :: Int -> ForbiddenSubstrings e -> ShowS
$cshowsPrec :: forall e. Show e => Int -> ForbiddenSubstrings e -> ShowS
Show, ReadPrec [ForbiddenSubstrings e]
ReadPrec (ForbiddenSubstrings e)
Int -> ReadS (ForbiddenSubstrings e)
ReadS [ForbiddenSubstrings e]
(Int -> ReadS (ForbiddenSubstrings e))
-> ReadS [ForbiddenSubstrings e]
-> ReadPrec (ForbiddenSubstrings e)
-> ReadPrec [ForbiddenSubstrings e]
-> Read (ForbiddenSubstrings e)
forall e. (Read e, Ord e) => ReadPrec [ForbiddenSubstrings e]
forall e. (Read e, Ord e) => ReadPrec (ForbiddenSubstrings e)
forall e. (Read e, Ord e) => Int -> ReadS (ForbiddenSubstrings e)
forall e. (Read e, Ord e) => ReadS [ForbiddenSubstrings e]
forall a.
(Int -> ReadS a)
-> ReadS [a] -> ReadPrec a -> ReadPrec [a] -> Read a
readListPrec :: ReadPrec [ForbiddenSubstrings e]
$creadListPrec :: forall e. (Read e, Ord e) => ReadPrec [ForbiddenSubstrings e]
readPrec :: ReadPrec (ForbiddenSubstrings e)
$creadPrec :: forall e. (Read e, Ord e) => ReadPrec (ForbiddenSubstrings e)
readList :: ReadS [ForbiddenSubstrings e]
$creadList :: forall e. (Read e, Ord e) => ReadS [ForbiddenSubstrings e]
readsPrec :: Int -> ReadS (ForbiddenSubstrings e)
$creadsPrec :: forall e. (Read e, Ord e) => Int -> ReadS (ForbiddenSubstrings e)
Read)

> -- |A sequence of symbols, possibly annotated with end-markers.
> data TaggedSubstring e = Free [e] | Initial [e] | Final [e] | Word [e]
>                          deriving (TaggedSubstring e -> TaggedSubstring e -> Bool
(TaggedSubstring e -> TaggedSubstring e -> Bool)
-> (TaggedSubstring e -> TaggedSubstring e -> Bool)
-> Eq (TaggedSubstring e)
forall e. Eq e => TaggedSubstring e -> TaggedSubstring e -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: TaggedSubstring e -> TaggedSubstring e -> Bool
$c/= :: forall e. Eq e => TaggedSubstring e -> TaggedSubstring e -> Bool
== :: TaggedSubstring e -> TaggedSubstring e -> Bool
$c== :: forall e. Eq e => TaggedSubstring e -> TaggedSubstring e -> Bool
Eq, Eq (TaggedSubstring e)
Eq (TaggedSubstring e)
-> (TaggedSubstring e -> TaggedSubstring e -> Ordering)
-> (TaggedSubstring e -> TaggedSubstring e -> Bool)
-> (TaggedSubstring e -> TaggedSubstring e -> Bool)
-> (TaggedSubstring e -> TaggedSubstring e -> Bool)
-> (TaggedSubstring e -> TaggedSubstring e -> Bool)
-> (TaggedSubstring e -> TaggedSubstring e -> TaggedSubstring e)
-> (TaggedSubstring e -> TaggedSubstring e -> TaggedSubstring e)
-> Ord (TaggedSubstring e)
TaggedSubstring e -> TaggedSubstring e -> Bool
TaggedSubstring e -> TaggedSubstring e -> Ordering
TaggedSubstring e -> TaggedSubstring e -> TaggedSubstring e
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
forall e. Ord e => Eq (TaggedSubstring e)
forall e. Ord e => TaggedSubstring e -> TaggedSubstring e -> Bool
forall e.
Ord e =>
TaggedSubstring e -> TaggedSubstring e -> Ordering
forall e.
Ord e =>
TaggedSubstring e -> TaggedSubstring e -> TaggedSubstring e
min :: TaggedSubstring e -> TaggedSubstring e -> TaggedSubstring e
$cmin :: forall e.
Ord e =>
TaggedSubstring e -> TaggedSubstring e -> TaggedSubstring e
max :: TaggedSubstring e -> TaggedSubstring e -> TaggedSubstring e
$cmax :: forall e.
Ord e =>
TaggedSubstring e -> TaggedSubstring e -> TaggedSubstring e
>= :: TaggedSubstring e -> TaggedSubstring e -> Bool
$c>= :: forall e. Ord e => TaggedSubstring e -> TaggedSubstring e -> Bool
> :: TaggedSubstring e -> TaggedSubstring e -> Bool
$c> :: forall e. Ord e => TaggedSubstring e -> TaggedSubstring e -> Bool
<= :: TaggedSubstring e -> TaggedSubstring e -> Bool
$c<= :: forall e. Ord e => TaggedSubstring e -> TaggedSubstring e -> Bool
< :: TaggedSubstring e -> TaggedSubstring e -> Bool
$c< :: forall e. Ord e => TaggedSubstring e -> TaggedSubstring e -> Bool
compare :: TaggedSubstring e -> TaggedSubstring e -> Ordering
$ccompare :: forall e.
Ord e =>
TaggedSubstring e -> TaggedSubstring e -> Ordering
$cp1Ord :: forall e. Ord e => Eq (TaggedSubstring e)
Ord, ReadPrec [TaggedSubstring e]
ReadPrec (TaggedSubstring e)
Int -> ReadS (TaggedSubstring e)
ReadS [TaggedSubstring e]
(Int -> ReadS (TaggedSubstring e))
-> ReadS [TaggedSubstring e]
-> ReadPrec (TaggedSubstring e)
-> ReadPrec [TaggedSubstring e]
-> Read (TaggedSubstring e)
forall e. Read e => ReadPrec [TaggedSubstring e]
forall e. Read e => ReadPrec (TaggedSubstring e)
forall e. Read e => Int -> ReadS (TaggedSubstring e)
forall e. Read e => ReadS [TaggedSubstring e]
forall a.
(Int -> ReadS a)
-> ReadS [a] -> ReadPrec a -> ReadPrec [a] -> Read a
readListPrec :: ReadPrec [TaggedSubstring e]
$creadListPrec :: forall e. Read e => ReadPrec [TaggedSubstring e]
readPrec :: ReadPrec (TaggedSubstring e)
$creadPrec :: forall e. Read e => ReadPrec (TaggedSubstring e)
readList :: ReadS [TaggedSubstring e]
$creadList :: forall e. Read e => ReadS [TaggedSubstring e]
readsPrec :: Int -> ReadS (TaggedSubstring e)
$creadsPrec :: forall e. Read e => Int -> ReadS (TaggedSubstring e)
Read, Int -> TaggedSubstring e -> ShowS
[TaggedSubstring e] -> ShowS
TaggedSubstring e -> String
(Int -> TaggedSubstring e -> ShowS)
-> (TaggedSubstring e -> String)
-> ([TaggedSubstring e] -> ShowS)
-> Show (TaggedSubstring e)
forall e. Show e => Int -> TaggedSubstring e -> ShowS
forall e. Show e => [TaggedSubstring e] -> ShowS
forall e. Show e => TaggedSubstring e -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [TaggedSubstring e] -> ShowS
$cshowList :: forall e. Show e => [TaggedSubstring e] -> ShowS
show :: TaggedSubstring e -> String
$cshow :: forall e. Show e => TaggedSubstring e -> String
showsPrec :: Int -> TaggedSubstring e -> ShowS
$cshowsPrec :: forall e. Show e => Int -> TaggedSubstring e -> ShowS
Show)

> instance Ord e => Container (ForbiddenSubstrings e) (TaggedSubstring e)
>     where empty :: ForbiddenSubstrings e
empty         =  Set e
-> Set [e]
-> Set [e]
-> Set [e]
-> Set [e]
-> ForbiddenSubstrings e
forall e.
Set e
-> Set [e]
-> Set [e]
-> Set [e]
-> Set [e]
-> ForbiddenSubstrings e
ForbiddenSubstrings Set e
forall c a. Container c a => c
empty Set [e]
forall c a. Container c a => c
empty Set [e]
forall c a. Container c a => c
empty Set [e]
forall c a. Container c a => c
empty Set [e]
forall c a. Container c a => c
empty
>           isEmpty :: ForbiddenSubstrings e -> Bool
isEmpty ForbiddenSubstrings e
fs    =  Set [e] -> Bool
forall c a. Container c a => c -> Bool
isEmpty (ForbiddenSubstrings e -> Set [e]
forall e. ForbiddenSubstrings e -> Set [e]
forbiddenWords ForbiddenSubstrings e
fs)     Bool -> Bool -> Bool
&&
>                            Set [e] -> Bool
forall c a. Container c a => c -> Bool
isEmpty (ForbiddenSubstrings e -> Set [e]
forall e. ForbiddenSubstrings e -> Set [e]
forbiddenInitials ForbiddenSubstrings e
fs)  Bool -> Bool -> Bool
&&
>                            Set [e] -> Bool
forall c a. Container c a => c -> Bool
isEmpty (ForbiddenSubstrings e -> Set [e]
forall e. ForbiddenSubstrings e -> Set [e]
forbiddenFrees ForbiddenSubstrings e
fs)     Bool -> Bool -> Bool
&&
>                            Set [e] -> Bool
forall c a. Container c a => c -> Bool
isEmpty (ForbiddenSubstrings e -> Set [e]
forall e. ForbiddenSubstrings e -> Set [e]
forbiddenFinals ForbiddenSubstrings e
fs)
>           insert :: TaggedSubstring e -> ForbiddenSubstrings e -> ForbiddenSubstrings e
insert (Free [e
x]) ForbiddenSubstrings e
c
>               = ForbiddenSubstrings e
c {forbiddenFrees :: Set [e]
forbiddenFrees = [e] -> Set [e] -> Set [e]
forall c a. Container c a => a -> c -> c
insert [e
x] (ForbiddenSubstrings e -> Set [e]
forall e. ForbiddenSubstrings e -> Set [e]
forbiddenFrees ForbiddenSubstrings e
c)}
>           insert (Free [e]
x) ForbiddenSubstrings e
c
>               = ForbiddenSubstrings e
c {forbiddenFrees :: Set [e]
forbiddenFrees = [e] -> Set [e] -> Set [e]
forall c a. Container c a => a -> c -> c
insert [e]
x (ForbiddenSubstrings e -> Set [e]
forall e. ForbiddenSubstrings e -> Set [e]
forbiddenFrees ForbiddenSubstrings e
c)}
>           insert (Final [e]
x) ForbiddenSubstrings e
c
>               = ForbiddenSubstrings e
c {forbiddenFinals :: Set [e]
forbiddenFinals = [e] -> Set [e] -> Set [e]
forall c a. Container c a => a -> c -> c
insert [e]
x (ForbiddenSubstrings e -> Set [e]
forall e. ForbiddenSubstrings e -> Set [e]
forbiddenFinals ForbiddenSubstrings e
c)}
>           insert (Initial [e]
x) ForbiddenSubstrings e
c
>               = ForbiddenSubstrings e
c {forbiddenInitials :: Set [e]
forbiddenInitials = [e] -> Set [e] -> Set [e]
forall c a. Container c a => a -> c -> c
insert [e]
x (ForbiddenSubstrings e -> Set [e]
forall e. ForbiddenSubstrings e -> Set [e]
forbiddenInitials ForbiddenSubstrings e
c)}
>           insert (Word [e]
x) ForbiddenSubstrings e
c
>               = ForbiddenSubstrings e
c {forbiddenWords :: Set [e]
forbiddenWords = [e] -> Set [e] -> Set [e]
forall c a. Container c a => a -> c -> c
insert [e]
x (ForbiddenSubstrings e -> Set [e]
forall e. ForbiddenSubstrings e -> Set [e]
forbiddenWords ForbiddenSubstrings e
c)}
>           contains :: TaggedSubstring e -> ForbiddenSubstrings e -> Bool
contains (Free [e]
x) ForbiddenSubstrings e
c
>               = [e] -> Set [e] -> Bool
forall c a. (Container c a, Eq a) => a -> c -> Bool
contains [e]
x (ForbiddenSubstrings e -> Set [e]
forall e. ForbiddenSubstrings e -> Set [e]
forbiddenFrees ForbiddenSubstrings e
c)
>           contains (Final [e]
x) ForbiddenSubstrings e
c
>               = [e] -> Set [e] -> Bool
forall c a. (Container c a, Eq a) => a -> c -> Bool
contains [e]
x (ForbiddenSubstrings e -> Set [e]
forall e. ForbiddenSubstrings e -> Set [e]
forbiddenFinals ForbiddenSubstrings e
c)
>           contains (Initial [e]
x) ForbiddenSubstrings e
c
>               = [e] -> Set [e] -> Bool
forall c a. (Container c a, Eq a) => a -> c -> Bool
contains [e]
x (ForbiddenSubstrings e -> Set [e]
forall e. ForbiddenSubstrings e -> Set [e]
forbiddenInitials ForbiddenSubstrings e
c)
>           contains (Word [e]
x) ForbiddenSubstrings e
c
>               = [e] -> Set [e] -> Bool
forall c a. (Container c a, Eq a) => a -> c -> Bool
contains [e]
x (ForbiddenSubstrings e -> Set [e]
forall e. ForbiddenSubstrings e -> Set [e]
forbiddenWords ForbiddenSubstrings e
c)
>           union :: ForbiddenSubstrings e
-> ForbiddenSubstrings e -> ForbiddenSubstrings e
union         =  (Set [e] -> Set [e] -> Set [e])
-> ForbiddenSubstrings e
-> ForbiddenSubstrings e
-> ForbiddenSubstrings e
forall e.
Ord e =>
(Set [e] -> Set [e] -> Set [e])
-> ForbiddenSubstrings e
-> ForbiddenSubstrings e
-> ForbiddenSubstrings e
g Set [e] -> Set [e] -> Set [e]
forall c a. Container c a => c -> c -> c
union
>           intersection :: ForbiddenSubstrings e
-> ForbiddenSubstrings e -> ForbiddenSubstrings e
intersection  =  (Set [e] -> Set [e] -> Set [e])
-> ForbiddenSubstrings e
-> ForbiddenSubstrings e
-> ForbiddenSubstrings e
forall e.
Ord e =>
(Set [e] -> Set [e] -> Set [e])
-> ForbiddenSubstrings e
-> ForbiddenSubstrings e
-> ForbiddenSubstrings e
g Set [e] -> Set [e] -> Set [e]
forall c a. (Container c a, Eq a) => c -> c -> c
intersection
>           difference :: ForbiddenSubstrings e
-> ForbiddenSubstrings e -> ForbiddenSubstrings e
difference    =  (Set [e] -> Set [e] -> Set [e])
-> ForbiddenSubstrings e
-> ForbiddenSubstrings e
-> ForbiddenSubstrings e
forall e.
Ord e =>
(Set [e] -> Set [e] -> Set [e])
-> ForbiddenSubstrings e
-> ForbiddenSubstrings e
-> ForbiddenSubstrings e
g Set [e] -> Set [e] -> Set [e]
forall c a. (Container c a, Eq a) => c -> c -> c
difference

> g :: Ord e => (Set [e] -> Set [e] -> Set [e]) ->
>      ForbiddenSubstrings e -> ForbiddenSubstrings e -> ForbiddenSubstrings e
> g :: (Set [e] -> Set [e] -> Set [e])
-> ForbiddenSubstrings e
-> ForbiddenSubstrings e
-> ForbiddenSubstrings e
g Set [e] -> Set [e] -> Set [e]
f ForbiddenSubstrings e
a ForbiddenSubstrings e
b = ForbiddenSubstrings :: forall e.
Set e
-> Set [e]
-> Set [e]
-> Set [e]
-> Set [e]
-> ForbiddenSubstrings e
ForbiddenSubstrings
>           { attestedUnits :: Set e
attestedUnits    =  Set e -> Set e -> Set e
forall c a. Container c a => c -> c -> c
union (ForbiddenSubstrings e -> Set e
forall e. ForbiddenSubstrings e -> Set e
attestedUnits ForbiddenSubstrings e
a) (ForbiddenSubstrings e -> Set e
forall e. ForbiddenSubstrings e -> Set e
attestedUnits ForbiddenSubstrings e
b)
>           , forbiddenWords :: Set [e]
forbiddenWords   =  Set [e] -> Set [e] -> Set [e]
f (ForbiddenSubstrings e -> Set [e]
forall e. ForbiddenSubstrings e -> Set [e]
forbiddenWords ForbiddenSubstrings e
a) (ForbiddenSubstrings e -> Set [e]
forall e. ForbiddenSubstrings e -> Set [e]
forbiddenWords ForbiddenSubstrings e
b)
>           , forbiddenInitials :: Set [e]
forbiddenInitials
>               = Set [e] -> Set [e] -> Set [e]
f (ForbiddenSubstrings e -> Set [e]
forall e. ForbiddenSubstrings e -> Set [e]
forbiddenInitials ForbiddenSubstrings e
a) (ForbiddenSubstrings e -> Set [e]
forall e. ForbiddenSubstrings e -> Set [e]
forbiddenInitials ForbiddenSubstrings e
b)
>           , forbiddenFrees :: Set [e]
forbiddenFrees   =  Set [e] -> Set [e] -> Set [e]
f (ForbiddenSubstrings e -> Set [e]
forall e. ForbiddenSubstrings e -> Set [e]
forbiddenFrees ForbiddenSubstrings e
a) (ForbiddenSubstrings e -> Set [e]
forall e. ForbiddenSubstrings e -> Set [e]
forbiddenFrees ForbiddenSubstrings e
b)
>           , forbiddenFinals :: Set [e]
forbiddenFinals  =  Set [e] -> Set [e] -> Set [e]
f (ForbiddenSubstrings e -> Set [e]
forall e. ForbiddenSubstrings e -> Set [e]
forbiddenFinals ForbiddenSubstrings e
a) (ForbiddenSubstrings e -> Set [e]
forall e. ForbiddenSubstrings e -> Set [e]
forbiddenFinals ForbiddenSubstrings e
b)
>           }

> -- |The internal structure gathered by the PSG traversals.
> -- This structure does not include attested units or forbidden words,
> -- which are computable separately from the FSA and the forbidden paths
> -- and are not relevant until the optimal set of initial, free and
> -- final forbidden paths are fixed.  Labels of paths are (Symbol e).
> -- Note that, since these are paths in the powerset graph, the states of
> -- each path are labelled by elements of type @Set n@ if @n@ is
> -- the type that labels states in the underlying FSA.
> data ForbiddenPaths n e
>     = ForbiddenPaths
>       { -- |Paths witnessing forbidden initial factors
>         ForbiddenPaths n e -> Set (Path n e)
initialPaths :: Set (Path n e)
>         -- |Paths witnessing forbidden free factors
>       , ForbiddenPaths n e -> Set (Path n e)
freePaths    :: Set (Path n e)
>         -- |Paths witnessing forbidden final factors
>       , ForbiddenPaths n e -> Set (Path n e)
finalPaths   :: Set (Path n e)
>       }
>     deriving (ForbiddenPaths n e -> ForbiddenPaths n e -> Bool
(ForbiddenPaths n e -> ForbiddenPaths n e -> Bool)
-> (ForbiddenPaths n e -> ForbiddenPaths n e -> Bool)
-> Eq (ForbiddenPaths n e)
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
forall n e.
(Eq e, Eq n) =>
ForbiddenPaths n e -> ForbiddenPaths n e -> Bool
/= :: ForbiddenPaths n e -> ForbiddenPaths n e -> Bool
$c/= :: forall n e.
(Eq e, Eq n) =>
ForbiddenPaths n e -> ForbiddenPaths n e -> Bool
== :: ForbiddenPaths n e -> ForbiddenPaths n e -> Bool
$c== :: forall n e.
(Eq e, Eq n) =>
ForbiddenPaths n e -> ForbiddenPaths n e -> Bool
Eq, Eq (ForbiddenPaths n e)
Eq (ForbiddenPaths n e)
-> (ForbiddenPaths n e -> ForbiddenPaths n e -> Ordering)
-> (ForbiddenPaths n e -> ForbiddenPaths n e -> Bool)
-> (ForbiddenPaths n e -> ForbiddenPaths n e -> Bool)
-> (ForbiddenPaths n e -> ForbiddenPaths n e -> Bool)
-> (ForbiddenPaths n e -> ForbiddenPaths n e -> Bool)
-> (ForbiddenPaths n e -> ForbiddenPaths n e -> ForbiddenPaths n e)
-> (ForbiddenPaths n e -> ForbiddenPaths n e -> ForbiddenPaths n e)
-> Ord (ForbiddenPaths n e)
ForbiddenPaths n e -> ForbiddenPaths n e -> Bool
ForbiddenPaths n e -> ForbiddenPaths n e -> Ordering
ForbiddenPaths n e -> ForbiddenPaths n e -> ForbiddenPaths n e
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
forall n e. (Ord e, Ord n) => Eq (ForbiddenPaths n e)
forall n e.
(Ord e, Ord n) =>
ForbiddenPaths n e -> ForbiddenPaths n e -> Bool
forall n e.
(Ord e, Ord n) =>
ForbiddenPaths n e -> ForbiddenPaths n e -> Ordering
forall n e.
(Ord e, Ord n) =>
ForbiddenPaths n e -> ForbiddenPaths n e -> ForbiddenPaths n e
min :: ForbiddenPaths n e -> ForbiddenPaths n e -> ForbiddenPaths n e
$cmin :: forall n e.
(Ord e, Ord n) =>
ForbiddenPaths n e -> ForbiddenPaths n e -> ForbiddenPaths n e
max :: ForbiddenPaths n e -> ForbiddenPaths n e -> ForbiddenPaths n e
$cmax :: forall n e.
(Ord e, Ord n) =>
ForbiddenPaths n e -> ForbiddenPaths n e -> ForbiddenPaths n e
>= :: ForbiddenPaths n e -> ForbiddenPaths n e -> Bool
$c>= :: forall n e.
(Ord e, Ord n) =>
ForbiddenPaths n e -> ForbiddenPaths n e -> Bool
> :: ForbiddenPaths n e -> ForbiddenPaths n e -> Bool
$c> :: forall n e.
(Ord e, Ord n) =>
ForbiddenPaths n e -> ForbiddenPaths n e -> Bool
<= :: ForbiddenPaths n e -> ForbiddenPaths n e -> Bool
$c<= :: forall n e.
(Ord e, Ord n) =>
ForbiddenPaths n e -> ForbiddenPaths n e -> Bool
< :: ForbiddenPaths n e -> ForbiddenPaths n e -> Bool
$c< :: forall n e.
(Ord e, Ord n) =>
ForbiddenPaths n e -> ForbiddenPaths n e -> Bool
compare :: ForbiddenPaths n e -> ForbiddenPaths n e -> Ordering
$ccompare :: forall n e.
(Ord e, Ord n) =>
ForbiddenPaths n e -> ForbiddenPaths n e -> Ordering
$cp1Ord :: forall n e. (Ord e, Ord n) => Eq (ForbiddenPaths n e)
Ord)

> -- |Convert Set of Paths to Set of sequences of (Symbol e)
> factorsFromPaths :: (Ord e, Ord n) => Set (Path n e) -> Set [Symbol e]
> factorsFromPaths :: Set (Path n e) -> Set [Symbol e]
factorsFromPaths = (Path n e -> [Symbol e]) -> Set (Path n e) -> Set [Symbol e]
forall (s :: * -> *) b1 b a.
(Collapsible s, Container (s b1) b) =>
(a -> b) -> s a -> s b1
tmap Path n e -> [Symbol e]
forall n e. Path n e -> [Symbol e]
labels

\begin{itemize}
\item Attested units are alphabet elements that actually occur on a productive
  path of the FSA.  Since the FSA is normalized (by precondition) these are
  just the alphabet elements that occur as symbols as the label of any
  transition.
\item Forbidden words are the sequences of alphabet elements occurring on
  non-accepting paths of the FSA bounded by the max of:
  \begin{itemize}
  \item $k$ if it is non-zero
  \item The max length of the free forbidden paths
  \item The max length of the initial or final forbidden paths plus 1
  \end{itemize}
  Note that if $k$ is non-zero then it is an error to have the other three
  bounds be greater than $k$.  This error is not checked.
\end{itemize}

> -- |Forbidden substrings of the given 'FSA' relative to a domain alphabet
> -- which must include the alphabet of the 'FSA'
> forbiddenSubstringsWithAlphabet :: (Ord e, Ord n, Enum n) =>
>                                    Set e -> FSA n e -> ForbiddenSubstrings e
> forbiddenSubstringsWithAlphabet :: Set e -> FSA n e -> ForbiddenSubstrings e
forbiddenSubstringsWithAlphabet Set e
alph FSA n e
fsa =
>     Set e
-> Set [e]
-> Set [e]
-> Set [e]
-> Set [e]
-> ForbiddenSubstrings e
forall e.
Set e
-> Set [e]
-> Set [e]
-> Set [e]
-> Set [e]
-> ForbiddenSubstrings e
ForbiddenSubstrings Set e
aUns Set [e]
fWds Set [e]
fIns Set [e]
fFrs Set [e]
fFis
>         where aUns :: Set e
aUns  =   Set (Symbol e) -> Set e
forall (s :: * -> *) c e.
(Collapsible s, Container c e, Monoid c) =>
s (Symbol e) -> c
unsymbols (Set (Symbol e) -> Set e)
-> (Set (Transition n e) -> Set (Symbol e))
-> Set (Transition n e)
-> Set e
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Transition n e -> Symbol e)
-> Set (Transition n e) -> Set (Symbol e)
forall (s :: * -> *) b1 b a.
(Collapsible s, Container (s b1) b) =>
(a -> b) -> s a -> s b1
tmap Transition n e -> Symbol e
forall n e. Transition n e -> Symbol e
edgeLabel (Set (Transition n e) -> Set e) -> Set (Transition n e) -> Set e
forall a b. (a -> b) -> a -> b
$ FSA n e -> Set (Transition n e)
forall n e. FSA n e -> Set (Transition n e)
transitions FSA n e
fsa
>               fPs :: ForbiddenPaths (Set (Set n)) e
fPs   =  Set e -> FSA n e -> ForbiddenPaths (Set (Set n)) e
forall e n.
(Ord e, Ord n, Enum n) =>
Set e -> FSA n e -> ForbiddenPaths (Set (Set n)) e
forbiddenPathsWithAlphabet Set e
alph FSA n e
fsa
>               fInS :: Set [Symbol e]
fInS  =  Set (Path (Set (Set n)) e) -> Set [Symbol e]
forall e n. (Ord e, Ord n) => Set (Path n e) -> Set [Symbol e]
factorsFromPaths (Set (Path (Set (Set n)) e) -> Set [Symbol e])
-> Set (Path (Set (Set n)) e) -> Set [Symbol e]
forall a b. (a -> b) -> a -> b
$ ForbiddenPaths (Set (Set n)) e -> Set (Path (Set (Set n)) e)
forall n e. ForbiddenPaths n e -> Set (Path n e)
initialPaths ForbiddenPaths (Set (Set n)) e
fPs
>               fFrS :: Set [Symbol e]
fFrS  =  Set (Path (Set (Set n)) e) -> Set [Symbol e]
forall e n. (Ord e, Ord n) => Set (Path n e) -> Set [Symbol e]
factorsFromPaths (Set (Path (Set (Set n)) e) -> Set [Symbol e])
-> Set (Path (Set (Set n)) e) -> Set [Symbol e]
forall a b. (a -> b) -> a -> b
$ ForbiddenPaths (Set (Set n)) e -> Set (Path (Set (Set n)) e)
forall n e. ForbiddenPaths n e -> Set (Path n e)
freePaths ForbiddenPaths (Set (Set n)) e
fPs
>               fFiS :: Set [Symbol e]
fFiS  =  Set (Path (Set (Set n)) e) -> Set [Symbol e]
forall e n. (Ord e, Ord n) => Set (Path n e) -> Set [Symbol e]
factorsFromPaths (Set (Path (Set (Set n)) e) -> Set [Symbol e])
-> Set (Path (Set (Set n)) e) -> Set [Symbol e]
forall a b. (a -> b) -> a -> b
$ ForbiddenPaths (Set (Set n)) e -> Set (Path (Set (Set n)) e)
forall n e. ForbiddenPaths n e -> Set (Path n e)
finalPaths ForbiddenPaths (Set (Set n)) e
fPs
>               fWds :: Set [e]
fWds  =  ([Symbol e] -> [e]) -> Set [Symbol e] -> Set [e]
forall (s :: * -> *) b1 b a.
(Collapsible s, Container (s b1) b) =>
(a -> b) -> s a -> s b1
tmap [Symbol e] -> [e]
forall (s :: * -> *) c e.
(Collapsible s, Container c e, Monoid c) =>
s (Symbol e) -> c
unsymbols (Set [Symbol e] -> Set [e]) -> Set [Symbol e] -> Set [e]
forall a b. (a -> b) -> a -> b
$ FSA n e
-> Integer
-> Set [Symbol e]
-> Set [Symbol e]
-> Set [Symbol e]
-> Set [Symbol e]
forall e n.
(Ord e, Ord n) =>
FSA n e
-> Integer
-> Set [Symbol e]
-> Set [Symbol e]
-> Set [Symbol e]
-> Set [Symbol e]
fWords FSA n e
fsa (FSA n e -> Integer
forall e n. (Ord e, Ord n) => FSA n e -> Integer
slQ FSA n e
fsa) Set [Symbol e]
fInS Set [Symbol e]
fFrS Set [Symbol e]
fFiS
>               fIns :: Set [e]
fIns  =  ([Symbol e] -> [e]) -> Set [Symbol e] -> Set [e]
forall (s :: * -> *) b1 b a.
(Collapsible s, Container (s b1) b) =>
(a -> b) -> s a -> s b1
tmap [Symbol e] -> [e]
forall (s :: * -> *) c e.
(Collapsible s, Container c e, Monoid c) =>
s (Symbol e) -> c
unsymbols Set [Symbol e]
fInS
>               fFrs :: Set [e]
fFrs  =  ([Symbol e] -> [e]) -> Set [Symbol e] -> Set [e]
forall (s :: * -> *) b1 b a.
(Collapsible s, Container (s b1) b) =>
(a -> b) -> s a -> s b1
tmap [Symbol e] -> [e]
forall (s :: * -> *) c e.
(Collapsible s, Container c e, Monoid c) =>
s (Symbol e) -> c
unsymbols Set [Symbol e]
fFrS
>               fFis :: Set [e]
fFis  =  ([Symbol e] -> [e]) -> Set [Symbol e] -> Set [e]
forall (s :: * -> *) b1 b a.
(Collapsible s, Container (s b1) b) =>
(a -> b) -> s a -> s b1
tmap [Symbol e] -> [e]
forall (s :: * -> *) c e.
(Collapsible s, Container c e, Monoid c) =>
s (Symbol e) -> c
unsymbols Set [Symbol e]
fFiS

> -- |Forbidden substrings of the given 'FSA' relative to its alphabet
> forbiddenSubstrings :: (Ord e, Ord n, Enum n) =>
>                        FSA n e -> ForbiddenSubstrings e
> forbiddenSubstrings :: FSA n e -> ForbiddenSubstrings e
forbiddenSubstrings FSA n e
fsa = Set e -> FSA n e -> ForbiddenSubstrings e
forall e n.
(Ord e, Ord n, Enum n) =>
Set e -> FSA n e -> ForbiddenSubstrings e
forbiddenSubstringsWithAlphabet (FSA n e -> Set e
forall (g :: * -> *) e. HasAlphabet g => g e -> Set e
alphabet FSA n e
fsa) FSA n e
fsa

> forbiddenPathsWithAlphabet :: (Ord e, Ord n, Enum n) =>
>                               Set e -> FSA n e ->
>                               ForbiddenPaths (Set (Set n)) e
> forbiddenPathsWithAlphabet :: Set e -> FSA n e -> ForbiddenPaths (Set (Set n)) e
forbiddenPathsWithAlphabet Set e
alph FSA n e
fsa =
>     Set (Path (Set (Set n)) e)
-> Set (Path (Set (Set n)) e)
-> Set (Path (Set (Set n)) e)
-> ForbiddenPaths (Set (Set n)) e
forall n e.
Set (Path n e)
-> Set (Path n e) -> Set (Path n e) -> ForbiddenPaths n e
ForbiddenPaths Set (Path (Set (Set n)) e)
fInitP Set (Path (Set (Set n)) e)
fFreeP Set (Path (Set (Set n)) e)
fFinP
>         where f' :: FSA n e
f'      =  FSA n e
fsa {sigma :: Set e
sigma = Set e -> Set e -> Set e
forall c a. Container c a => c -> c -> c
union Set e
alph (Set e -> Set e) -> Set e -> Set e
forall a b. (a -> b) -> a -> b
$ FSA n e -> Set e
forall (g :: * -> *) e. HasAlphabet g => g e -> Set e
alphabet FSA n e
fsa}
>               psg :: FSA (Set n) e
psg     =  FSA n e -> FSA (Set n) e
forall e n. (Ord e, Ord n) => FSA n e -> FSA (Set n) e
powersetGraph FSA n e
f'
>               fInitP :: Set (Path (Set (Set n)) e)
fInitP  =  FSA n e -> Set (Path (Set (Set n)) e)
forall a b.
(Ord a, Ord b, Enum b) =>
FSA b a -> Set (Path (Set (Set b)) a)
initialFPs FSA n e
f'
>               fFreeP :: Set (Path (Set (Set n)) e)
fFreeP  =  FSA (Set n) e -> Set (Path (Set (Set n)) e)
forall e n.
(Ord e, Ord n, Enum n) =>
FSA (Set n) e -> Set (Path (Set (Set n)) e)
freeFPsPSG FSA (Set n) e
psg
>               fFinP :: Set (Path (Set (Set n)) e)
fFinP   =  FSA (Set n) e -> Set (Path (Set (Set n)) e)
forall e n.
(Ord e, Ord n, Enum n) =>
FSA (Set n) e -> Set (Path (Set (Set n)) e)
finalFPsPSG FSA (Set n) e
psg


%% Forbidden words
%% Labels of acyclic paths from the start state of the DFA that end at a
%% non-accepting state.

%% These could possibly already be barred by a forbidden final factor,
%% but neither an initial or free forbidden factor

%% However, for the nonce we fall back to just filtering rejects as in 2016
%% This just filters the empty string and words with initialFFs as a previc,
%% freeFFs as a substring, or finalFFs as a suffix from rejected words of 
%% length less than or equal to bound

fWords collects the set of words rejected by the given FSA which are not
already excluded by the given initial, free or final FFs that are no longer
than the max of the given bound (typically $k$), one less than the longest
initial or final forbidden factor and two less than the longest free forbidden
factor.

Note that the FFs here are actual forbidden substrings, not forbidden paths

%% Argument order: Initials, Frees, Finals
%% Output: Words

> fWords :: (Ord e, Ord n) => FSA n e -> Integer ->
>           Set [Symbol e] -> Set [Symbol e] -> Set [Symbol e] ->
>           Set [Symbol e]
> fWords :: FSA n e
-> Integer
-> Set [Symbol e]
-> Set [Symbol e]
-> Set [Symbol e]
-> Set [Symbol e]
fWords FSA n e
fsa Integer
bound Set [Symbol e]
iFFs Set [Symbol e]
frFFs Set [Symbol e]
fiFFs
>     = [[Symbol e]] -> Set [Symbol e]
forall a. Ord a => [a] -> Set a
Set.fromList ([[Symbol e]] -> Set [Symbol e])
-> (Set (Path n e) -> [[Symbol e]])
-> Set (Path n e)
-> Set [Symbol e]
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
>       ([Symbol e] -> Bool) -> [[Symbol e]] -> [[Symbol e]]
forall a. (a -> Bool) -> [a] -> [a]
filter
>       (\[Symbol e]
wrd ->
>        Bool -> Bool
not (([Symbol e] -> Bool) -> [[Symbol e]] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
any (\[Symbol e]
x -> [Symbol e] -> [Symbol e] -> Bool
forall a. Eq a => [a] -> [a] -> Bool
List.isSuffixOf [Symbol e]
x [Symbol e]
wrd) (Set [Symbol e] -> [[Symbol e]]
forall a. Set a -> [a]
Set.toList Set [Symbol e]
fiFFs) Bool -> Bool -> Bool
||
>             ([Symbol e] -> Bool) -> [[Symbol e]] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
any (\[Symbol e]
x -> [Symbol e] -> [Symbol e] -> Bool
forall a. Eq a => [a] -> [a] -> Bool
List.isInfixOf  [Symbol e]
x [Symbol e]
wrd) (Set [Symbol e] -> [[Symbol e]]
forall a. Set a -> [a]
Set.toList Set [Symbol e]
frFFs) Bool -> Bool -> Bool
||
>             ([Symbol e] -> Bool) -> [[Symbol e]] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
any (\[Symbol e]
x -> [Symbol e] -> [Symbol e] -> Bool
forall a. Eq a => [a] -> [a] -> Bool
List.isPrefixOf [Symbol e]
x [Symbol e]
wrd) (Set [Symbol e] -> [[Symbol e]]
forall a. Set a -> [a]
Set.toList Set [Symbol e]
iFFs)
>            )
>       ) ([[Symbol e]] -> [[Symbol e]])
-> (Set (Path n e) -> [[Symbol e]])
-> Set (Path n e)
-> [[Symbol e]]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Path n e -> [Symbol e]) -> [Path n e] -> [[Symbol e]]
forall a b. (a -> b) -> [a] -> [b]
map Path n e -> [Symbol e]
forall n e. Path n e -> [Symbol e]
word ([Path n e] -> [[Symbol e]])
-> (Set (Path n e) -> [Path n e]) -> Set (Path n e) -> [[Symbol e]]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Set (Path n e) -> [Path n e]
forall a. Set a -> [a]
Set.toList (Set (Path n e) -> Set [Symbol e])
-> Set (Path n e) -> Set [Symbol e]
forall a b. (a -> b) -> a -> b
$ FSA n e -> Integer -> Set (Path n e)
forall e n. (Ord e, Ord n) => FSA n e -> Integer -> Set (Path n e)
rejectingPaths FSA n e
fsa Integer
bnd
>     where bnd :: Integer
bnd = Integer -> Integer -> Integer
forall a. Ord a => a -> a -> a
max (Set [Symbol e] -> Integer
forall p (c :: * -> *) b.
(Collapsible c, Integral p) =>
Set (c b) -> p
supermax (Set [Symbol e] -> Set [Symbol e] -> Set [Symbol e]
forall a. Ord a => Set a -> Set a -> Set a
Set.union Set [Symbol e]
iFFs Set [Symbol e]
fiFFs) Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- Integer
1) (Integer -> Integer) -> Integer -> Integer
forall a b. (a -> b) -> a -> b
$
>                 Integer -> Integer -> Integer
forall a. Ord a => a -> a -> a
max (Set [Symbol e] -> Integer
forall p (c :: * -> *) b.
(Collapsible c, Integral p) =>
Set (c b) -> p
supermax Set [Symbol e]
frFFs Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- Integer
2) Integer
bound
>           supermax :: Set (c b) -> p
supermax Set (c b)
s
>               | Set (c b) -> Bool
forall a. Set a -> Bool
Set.null Set (c b)
s  =  p
0
>               | Bool
otherwise   =  [p] -> p
forall (t :: * -> *) a. (Foldable t, Ord a) => t a -> a
maximum ([p] -> p) -> ([c b] -> [p]) -> [c b] -> p
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (c b -> p) -> [c b] -> [p]
forall a b. (a -> b) -> [a] -> [b]
map c b -> p
forall (c :: * -> *) a b. (Collapsible c, Integral a) => c b -> a
size ([c b] -> p) -> [c b] -> p
forall a b. (a -> b) -> a -> b
$ Set (c b) -> [c b]
forall a. Set a -> [a]
Set.toList Set (c b)
s


%% Only the labels (a.k.a. word) component of the resulting paths
%% has any validity, as the states of the reversed FSA have no
%% meaningful connection to those of the input.

> initialFPs :: (Ord a, Ord b, Enum b) =>
>               FSA b a -> Set (Path (Set (Set b)) a)
> initialFPs :: FSA b a -> Set (Path (Set (Set b)) a)
initialFPs FSA b a
fsa = (Path (Set (Set b)) a -> Path (Set (Set b)) a)
-> Set (Path (Set (Set b)) a) -> Set (Path (Set (Set b)) a)
forall (s :: * -> *) b1 b a.
(Collapsible s, Container (s b1) b) =>
(a -> b) -> s a -> s b1
tmap (\Path (Set (Set b)) a
p -> Path (Set (Set b)) a
p {labels :: [Symbol a]
labels = Path (Set (Set b)) a -> [Symbol a]
forall n e. Path n e -> [Symbol e]
word Path (Set (Set b)) a
p}) (Set (Path (Set (Set b)) a) -> Set (Path (Set (Set b)) a))
-> Set (Path (Set (Set b)) a) -> Set (Path (Set (Set b)) a)
forall a b. (a -> b) -> a -> b
$
>                    FSA (Set b) a -> Set (Path (Set (Set b)) a)
forall e n.
(Ord e, Ord n, Enum n) =>
FSA (Set n) e -> Set (Path (Set (Set n)) e)
finalFPsPSG (FSA b a -> FSA (Set b) a
forall e n. (Ord e, Ord n) => FSA n e -> FSA (Set n) e
powersetGraph FSA b a
rFSA)
>         where rFSA :: FSA b a
rFSA = FSA Integer a -> FSA b a
forall e n n1.
(Ord e, Ord n, Ord n1, Enum n1) =>
FSA n e -> FSA n1 e
renameStates (FSA Integer a -> FSA b a)
-> (FSA b a -> FSA Integer a) -> FSA b a -> FSA b a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. FSA b a -> FSA Integer a
forall e n. (Ord e, Ord n) => FSA n e -> FSA Integer e
normalize (FSA b a -> FSA b a) -> FSA b a -> FSA b a
forall a b. (a -> b) -> a -> b
$ FSA b a -> FSA b a
forall e n. (Ord e, Ord n) => FSA n e -> FSA n e
LTK.FSA.reverse FSA b a
fsa

> -- if bound >= 0 then take cycles up to bound+1 times
> -- otherwise take cycles arbitrarily many times
> -- bound should be < 0 only if the psg is the PSG of an FSA that recognizes
> -- an SL stringset, otherwise termination is not guaranteed
> freeFPsPSG :: (Ord e, Ord n, Enum n) =>
>               FSA (Set n) e -> Set (Path (Set (Set n)) e)
> freeFPsPSG :: FSA (Set n) e -> Set (Path (Set (Set n)) e)
freeFPsPSG FSA (Set n) e
psg = FSA (Set n) e
-> Set (State (Set n))
-> [Path (Set (Set n)) e]
-> Set (Path (Set (Set n)) e)
-> Set (Path (Set (Set n)) e)
forall e n.
(Ord e, Ord n, Enum n) =>
FSA (Set n) e
-> Set (State (Set n))
-> [Path (Set (Set n)) e]
-> Set (Path (Set (Set n)) e)
-> Set (Path (Set (Set n)) e)
gatherFPs FSA (Set n) e
psgR (State (Set n) -> Set (State (Set n))
forall c a. Container c a => a -> c
singleton State (Set n)
stateQ) [Path (Set (Set n)) e]
initialFront Set (Path (Set (Set n)) e)
forall c a. Container c a => c
empty
>     where psgR :: FSA (Set n) e
psgR    =  FSA (Set n) e -> FSA (Set n) e
forall e n.
(Ord e, Ord n, Enum n) =>
FSA (Set n) e -> FSA (Set n) e
trimRevPSG FSA (Set n) e
psg
>           stateQ :: State (Set n)
stateQ  =  FSA (Set n) e -> State (Set n)
forall a b. (Ord a, Ord b) => FSA (Set b) a -> State (Set b)
psgQ FSA (Set n) e
psg
>           initialFront :: [Path (Set (Set n)) e]
initialFront
>               | State (Set n) -> Set (State (Set n)) -> Bool
forall c a. (Container c a, Eq a) => a -> c -> Bool
contains (Set n -> State (Set n)
forall n. n -> State n
State Set n
forall c a. Container c a => c
empty) (Set (State (Set n)) -> Bool) -> Set (State (Set n)) -> Bool
forall a b. (a -> b) -> a -> b
$ FSA (Set n) e -> Set (State (Set n))
forall e n. (Ord e, Ord n) => FSA n e -> Set (State n)
states FSA (Set n) e
psg
>                     = Path (Set (Set n)) e -> [Path (Set (Set n)) e]
forall c a. Container c a => a -> c
singleton (Path (Set (Set n)) e -> [Path (Set (Set n)) e])
-> Path (Set (Set n)) e -> [Path (Set (Set n)) e]
forall a b. (a -> b) -> a -> b
$
>                       Path :: forall n e.
[Symbol e]
-> Maybe (State n) -> Multiset (State n) -> Integer -> Path n e
Path
>                       { labels :: [Symbol e]
labels    =  [Symbol e]
forall c a. Container c a => c
empty
>                       , endstate :: Maybe (State (Set (Set n)))
endstate  =  State (Set (Set n)) -> Maybe (State (Set (Set n)))
forall a. a -> Maybe a
Just (State (Set (Set n)) -> Maybe (State (Set (Set n))))
-> (Set (Set n) -> State (Set (Set n)))
-> Set (Set n)
-> Maybe (State (Set (Set n)))
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Set (Set n) -> State (Set (Set n))
forall n. n -> State n
State (Set (Set n) -> Maybe (State (Set (Set n))))
-> Set (Set n) -> Maybe (State (Set (Set n)))
forall a b. (a -> b) -> a -> b
$ Set n -> Set (Set n)
forall c a. Container c a => a -> c
singleton Set n
forall c a. Container c a => c
empty
>                       , stateMultiset :: Multiset (State (Set (Set n)))
stateMultiset
>                             = State (Set (Set n)) -> Multiset (State (Set (Set n)))
forall c a. Container c a => a -> c
singleton (State (Set (Set n)) -> Multiset (State (Set (Set n))))
-> (Set (Set n) -> State (Set (Set n)))
-> Set (Set n)
-> Multiset (State (Set (Set n)))
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Set (Set n) -> State (Set (Set n))
forall n. n -> State n
State (Set (Set n) -> Multiset (State (Set (Set n))))
-> Set (Set n) -> Multiset (State (Set (Set n)))
forall a b. (a -> b) -> a -> b
$ Set n -> Set (Set n)
forall c a. Container c a => a -> c
singleton Set n
forall c a. Container c a => c
empty
>                       , depth :: Integer
depth     =  Integer
0
>                       }
>               | Bool
otherwise = [Path (Set (Set n)) e]
forall c a. Container c a => c
empty


%% finalFPs
%%  graph: reversed powerset graph
%%    less: in-edges to $\emptyset$
%%          --- path necessarily would include ff as prefix
%%          out-edges from Q
%%          --- path necessarily includes final ff as suffix
%%  goals: {State Q}
%%  initial states:  {s $\in$ (states psg) |
%%                     s /= $\emptyset$ and
%%                     s $\cap$ (finals fsa) == $\emptyset$}
%%                   This is complement of initial states of reversed psGraph
%% if bound >= 0 then take cycles up to bound+1 times
%% otherwise take cycles arbitrarily many times
%% bound should be < 0 only if the psg is the PSG of an FSA that recognizes an
%%   SL stringset, otherwise termination is not guaranteed

> finalFPsPSG :: (Ord e, Ord n, Enum n) =>
>                  FSA (Set n) e -> Set (Path (Set (Set n)) e)
> finalFPsPSG :: FSA (Set n) e -> Set (Path (Set (Set n)) e)
finalFPsPSG FSA (Set n) e
psg = FSA (Set n) e
-> Set (State (Set n))
-> [Path (Set (Set n)) e]
-> Set (Path (Set (Set n)) e)
-> Set (Path (Set (Set n)) e)
forall e n.
(Ord e, Ord n, Enum n) =>
FSA (Set n) e
-> Set (State (Set n))
-> [Path (Set (Set n)) e]
-> Set (Path (Set (Set n)) e)
-> Set (Path (Set (Set n)) e)
gatherFPs FSA (Set n) e
psgR (State (Set n) -> Set (State (Set n))
forall c a. Container c a => a -> c
singleton State (Set n)
stateQ) [Path (Set (Set n)) e]
front0 Set (Path (Set (Set n)) e)
forall c a. Container c a => c
empty
>     where psgR :: FSA (Set n) e
psgR    =  FSA (Set n) e -> FSA (Set n) e
forall e n.
(Ord e, Ord n, Enum n) =>
FSA (Set n) e -> FSA (Set n) e
trimRevPSG FSA (Set n) e
psg
>           stateQ :: State (Set n)
stateQ  =  FSA (Set n) e -> State (Set n)
forall a b. (Ord a, Ord b) => FSA (Set b) a -> State (Set b)
psgQ FSA (Set n) e
psg
>           front0 :: [Path (Set (Set n)) e]
front0  =  Path (Set (Set n)) e -> [Path (Set (Set n)) e]
forall c a. Container c a => a -> c
singleton (Path (Set (Set n)) e -> [Path (Set (Set n)) e])
-> Path (Set (Set n)) e -> [Path (Set (Set n)) e]
forall a b. (a -> b) -> a -> b
$
>                      Path :: forall n e.
[Symbol e]
-> Maybe (State n) -> Multiset (State n) -> Integer -> Path n e
Path
>                      { labels :: [Symbol e]
labels = [Symbol e]
forall c a. Container c a => c
empty
>                      , endstate :: Maybe (State (Set (Set n)))
endstate = State (Set (Set n)) -> Maybe (State (Set (Set n)))
forall (f :: * -> *) a. Applicative f => a -> f a
pure State (Set (Set n))
nonFin
>                      , stateMultiset :: Multiset (State (Set (Set n)))
stateMultiset = State (Set (Set n)) -> Multiset (State (Set (Set n)))
forall c a. Container c a => a -> c
singleton State (Set (Set n))
nonFin
>                      , depth :: Integer
depth = Integer
0
>                      }
>           nonFin :: State (Set (Set n))
nonFin  =  ([Set n] -> Set (Set n)) -> State [Set n] -> State (Set (Set n))
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap [Set n] -> Set (Set n)
forall a. Ord a => [a] -> Set a
Set.fromList         (State [Set n] -> State (Set (Set n)))
-> (Set (State (Set n)) -> State [Set n])
-> Set (State (Set n))
-> State (Set (Set n))
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
>                      [State (Set n)] -> State [Set n]
forall (t :: * -> *) (m :: * -> *) a.
(Traversable t, Monad m) =>
t (m a) -> m (t a)
sequence ([State (Set n)] -> State [Set n])
-> (Set (State (Set n)) -> [State (Set n)])
-> Set (State (Set n))
-> State [Set n]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Set (State (Set n)) -> [State (Set n)]
forall a. Set a -> [a]
Set.toList     (Set (State (Set n)) -> [State (Set n)])
-> (Set (State (Set n)) -> Set (State (Set n)))
-> Set (State (Set n))
-> [State (Set n)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
>                      Set (State (Set n)) -> Set (State (Set n)) -> Set (State (Set n))
forall c a. (Container c a, Eq a) => c -> c -> c
difference (FSA (Set n) e -> Set (State (Set n))
forall e n. (Ord e, Ord n) => FSA n e -> Set (State n)
states FSA (Set n) e
psgR)  (Set (State (Set n)) -> Set (State (Set n)))
-> (Set (State (Set n)) -> Set (State (Set n)))
-> Set (State (Set n))
-> Set (State (Set n))
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
>                      State (Set n) -> Set (State (Set n)) -> Set (State (Set n))
forall c a. Container c a => a -> c -> c
insert (Set n -> State (Set n)
forall n. n -> State n
State Set n
forall c a. Container c a => c
empty) (Set (State (Set n)) -> State (Set (Set n)))
-> Set (State (Set n)) -> State (Set (Set n))
forall a b. (a -> b) -> a -> b
$ FSA (Set n) e -> Set (State (Set n))
forall n e. FSA n e -> Set (State n)
initials FSA (Set n) e
psgR

%% trimRevPSG psg is reverse of
%%    (psg with in-edges to Q and out-edges from $\emptyset$ removed)
%%    note that such edges are necessarily self-edges

> trimRevPSG :: (Ord e, Ord n, Enum n) => FSA (Set n) e -> FSA (Set n) e
> trimRevPSG :: FSA (Set n) e -> FSA (Set n) e
trimRevPSG FSA (Set n) e
psg
>     = FSA (Set n) e -> FSA (Set n) e
forall e n. (Ord e, Ord n) => FSA n e -> FSA n e
LTK.FSA.reverse (FSA (Set n) e -> FSA (Set n) e) -> FSA (Set n) e -> FSA (Set n) e
forall a b. (a -> b) -> a -> b
$
>       FSA (Set n) e
psg
>       { transitions :: Set (Transition (Set n) e)
transitions
>             = (Transition (Set n) e -> Bool)
-> Set (Transition (Set n) e) -> Set (Transition (Set n) e)
forall (s :: * -> *) a.
(Collapsible s, Container (s a) a) =>
(a -> Bool) -> s a -> s a
keep
>               ((Transition (Set n) e -> Bool)
-> (Transition (Set n) e -> Bool) -> Transition (Set n) e -> Bool
forall a. (a -> Bool) -> (a -> Bool) -> a -> Bool
both
>                ((State (Set n) -> State (Set n) -> Bool
forall a. Eq a => a -> a -> Bool
/= FSA (Set n) e -> State (Set n)
forall a b. (Ord a, Ord b) => FSA (Set b) a -> State (Set b)
psgQ FSA (Set n) e
psg) (State (Set n) -> Bool)
-> (Transition (Set n) e -> State (Set n))
-> Transition (Set n) e
-> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Transition (Set n) e -> State (Set n)
forall n e. Transition n e -> State n
destination)
>                ((State (Set n) -> State (Set n) -> Bool
forall a. Eq a => a -> a -> Bool
/= Set n -> State (Set n)
forall n. n -> State n
State Set n
forall c a. Container c a => c
empty) (State (Set n) -> Bool)
-> (Transition (Set n) e -> State (Set n))
-> Transition (Set n) e
-> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Transition (Set n) e -> State (Set n)
forall n e. Transition n e -> State n
source)) (Set (Transition (Set n) e) -> Set (Transition (Set n) e))
-> Set (Transition (Set n) e) -> Set (Transition (Set n) e)
forall a b. (a -> b) -> a -> b
$
>               FSA (Set n) e -> Set (Transition (Set n) e)
forall n e. FSA n e -> Set (Transition n e)
transitions FSA (Set n) e
psg
>       }

%%  Breadth-first traversal of graph
%%   Returns list of strings labeling paths from initial frontier to a goal
%%    that are:  acyclic other than, if bound < 0, cycles of singletons
%%               & do not include shorter such path as a suffix
%% if bound is >= 0 then follow cycles up to bound+1 times
%% ow follow singleton cycles which, by assumption, will be the only cycles
%% This is guaranteed to terminate if (and only if) bound >=0 or graph is the
%%   reversed PSG of an FSA that recognizes an SL stringset.
%% The k in the comments is an iteration counter and is the length of the FPs
%%   being in a given pass 

> gatherFPs :: (Ord e, Ord n, Enum n) =>
>           FSA (Set n) e -> Set (State (Set n)) -> [Path (Set (Set n)) e] ->
>           Set (Path (Set (Set n)) e) -> Set (Path (Set (Set n)) e)
> gatherFPs :: FSA (Set n) e
-> Set (State (Set n))
-> [Path (Set (Set n)) e]
-> Set (Path (Set (Set n)) e)
-> Set (Path (Set (Set n)) e)
gatherFPs FSA (Set n) e
psg Set (State (Set n))
goal [Path (Set (Set n)) e]
front Set (Path (Set (Set n)) e)
fps
>     | [Path (Set (Set n)) e] -> Bool
forall c a. Container c a => c -> Bool
isEmpty [Path (Set (Set n)) e]
front = Set (Path (Set (Set n)) e)
fps
>     | Bool
otherwise = FSA (Set n) e
-> Set (State (Set n))
-> [Path (Set (Set n)) e]
-> Set (Path (Set (Set n)) e)
-> Set (Path (Set (Set n)) e)
forall e n.
(Ord e, Ord n, Enum n) =>
FSA (Set n) e
-> Set (State (Set n))
-> [Path (Set (Set n)) e]
-> Set (Path (Set (Set n)) e)
-> Set (Path (Set (Set n)) e)
gatherFPs FSA (Set n) e
psg Set (State (Set n))
goal [Path (Set (Set n)) e]
nextFront (Set (Path (Set (Set n)) e)
-> Set (Path (Set (Set n)) e) -> Set (Path (Set (Set n)) e)
forall c a. Container c a => c -> c -> c
union Set (Path (Set (Set n)) e)
nextFPs Set (Path (Set (Set n)) e)
fps)
>     where ([Path (Set (Set n)) e]
nextFront, Set (Path (Set (Set n)) e)
nextFPs)
>               = Set (State (Set n))
-> [Path (Set (Set n)) e]
-> [Path (Set (Set n)) e]
-> Set (Path (Set (Set n)) e)
-> ([Path (Set (Set n)) e], Set (Path (Set (Set n)) e))
forall e n.
(Ord e, Ord n, Enum n) =>
Set (State (Set n))
-> [Path (Set (Set n)) e]
-> [Path (Set (Set n)) e]
-> Set (Path (Set (Set n)) e)
-> ([Path (Set (Set n)) e], Set (Path (Set (Set n)) e))
passK Set (State (Set n))
goal
>                 (Set (Path (Set (Set n)) e) -> [Path (Set (Set n)) e]
forall a. Set a -> [a]
Set.toList (Set (Path (Set (Set n)) e) -> [Path (Set (Set n)) e])
-> Set (Path (Set (Set n)) e) -> [Path (Set (Set n)) e]
forall a b. (a -> b) -> a -> b
$
>                  (Path (Set (Set n)) e
 -> Set (Path (Set (Set n)) e) -> Set (Path (Set (Set n)) e))
-> Set (Path (Set (Set n)) e)
-> [Path (Set (Set n)) e]
-> Set (Path (Set (Set n)) e)
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (Set (Path (Set (Set n)) e)
-> Set (Path (Set (Set n)) e) -> Set (Path (Set (Set n)) e)
forall c a. Container c a => c -> c -> c
union (Set (Path (Set (Set n)) e)
 -> Set (Path (Set (Set n)) e) -> Set (Path (Set (Set n)) e))
-> (Path (Set (Set n)) e -> Set (Path (Set (Set n)) e))
-> Path (Set (Set n)) e
-> Set (Path (Set (Set n)) e)
-> Set (Path (Set (Set n)) e)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Path (Set (Set n)) e -> Set (Path (Set (Set n)) e)
acceptableExtensions) Set (Path (Set (Set n)) e)
forall c a. Container c a => c
empty [Path (Set (Set n)) e]
front)
>                 [Path (Set (Set n)) e]
forall c a. Container c a => c
empty Set (Path (Set (Set n)) e)
forall c a. Container c a => c
empty
>           acceptableExtensions :: Path (Set (Set n)) e -> Set (Path (Set (Set n)) e)
acceptableExtensions = FSA (Set n) e -> Path (Set (Set n)) e -> Set (Path (Set (Set n)) e)
forall e n.
(Ord e, Ord n) =>
FSA n e -> Path (Set n) e -> Set (Path (Set n) e)
nondeterministicAcyclicExtensions FSA (Set n) e
psg


%% passK scans extensions of kth frontier for length k FPs 
%%  paths with label of a known k-FP are dropped
%%  paths that end at a goal are added to FPs and paths with same label
%%      already in front k+1 are stripped
%% Returns (front k+1, k-FPs)
%% This k is not that k

> passK :: (Ord e, Ord n, Enum n) =>
>          Set (State (Set n)) -> [Path (Set (Set n)) e] ->
>          [Path (Set (Set n)) e] -> Set (Path (Set (Set n)) e) ->
>          ( [Path (Set (Set n)) e]
>          , Set (Path (Set (Set n)) e) )
> passK :: Set (State (Set n))
-> [Path (Set (Set n)) e]
-> [Path (Set (Set n)) e]
-> Set (Path (Set (Set n)) e)
-> ([Path (Set (Set n)) e], Set (Path (Set (Set n)) e))
passK Set (State (Set n))
_ [] [Path (Set (Set n)) e]
front Set (Path (Set (Set n)) e)
fps = ([Path (Set (Set n)) e]
front, Set (Path (Set (Set n)) e)
fps)
> passK Set (State (Set n))
goals (Path (Set (Set n)) e
p:[Path (Set (Set n)) e]
ps) [Path (Set (Set n)) e]
front Set (Path (Set (Set n)) e)
fps
>     | [Symbol e] -> Set [Symbol e] -> Bool
forall c a. (Container c a, Eq a) => a -> c -> Bool
contains (Path (Set (Set n)) e -> [Symbol e]
forall n e. Path n e -> [Symbol e]
labels Path (Set (Set n)) e
p) ((Path (Set (Set n)) e -> [Symbol e])
-> Set (Path (Set (Set n)) e) -> Set [Symbol e]
forall (s :: * -> *) b1 b a.
(Collapsible s, Container (s b1) b) =>
(a -> b) -> s a -> s b1
tmap Path (Set (Set n)) e -> [Symbol e]
forall n e. Path n e -> [Symbol e]
labels Set (Path (Set (Set n)) e)
fps)
>         = Set (State (Set n))
-> [Path (Set (Set n)) e]
-> [Path (Set (Set n)) e]
-> Set (Path (Set (Set n)) e)
-> ([Path (Set (Set n)) e], Set (Path (Set (Set n)) e))
forall e n.
(Ord e, Ord n, Enum n) =>
Set (State (Set n))
-> [Path (Set (Set n)) e]
-> [Path (Set (Set n)) e]
-> Set (Path (Set (Set n)) e)
-> ([Path (Set (Set n)) e], Set (Path (Set (Set n)) e))
passK Set (State (Set n))
goals [Path (Set (Set n)) e]
ps [Path (Set (Set n)) e]
front Set (Path (Set (Set n)) e)
fps
>     | Bool
-> (State (Set (Set n)) -> Bool)
-> Maybe (State (Set (Set n)))
-> Bool
forall b a. b -> (a -> b) -> Maybe a -> b
maybe Bool
False ((Set n -> Bool) -> Set (Set n) -> Bool
forall (s :: * -> *) a. Collapsible s => (a -> Bool) -> s a -> Bool
anyS (Set (State (Set n)) -> State (Set n) -> Bool
forall c a. (Container c a, Eq a) => c -> a -> Bool
isIn Set (State (Set n))
goals (State (Set n) -> Bool)
-> (Set n -> State (Set n)) -> Set n -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Set n -> State (Set n)
forall n. n -> State n
State) (Set (Set n) -> Bool)
-> (State (Set (Set n)) -> Set (Set n))
-> State (Set (Set n))
-> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. State (Set (Set n)) -> Set (Set n)
forall n. State n -> n
nodeLabel) (Maybe (State (Set (Set n))) -> Bool)
-> Maybe (State (Set (Set n))) -> Bool
forall a b. (a -> b) -> a -> b
$ Path (Set (Set n)) e -> Maybe (State (Set (Set n)))
forall n e. Path n e -> Maybe (State n)
endstate Path (Set (Set n)) e
p
>         = Set (State (Set n))
-> [Path (Set (Set n)) e]
-> [Path (Set (Set n)) e]
-> Set (Path (Set (Set n)) e)
-> ([Path (Set (Set n)) e], Set (Path (Set (Set n)) e))
forall e n.
(Ord e, Ord n, Enum n) =>
Set (State (Set n))
-> [Path (Set (Set n)) e]
-> [Path (Set (Set n)) e]
-> Set (Path (Set (Set n)) e)
-> ([Path (Set (Set n)) e], Set (Path (Set (Set n)) e))
passK Set (State (Set n))
goals [Path (Set (Set n)) e]
ps
>            ((Path (Set (Set n)) e -> Bool)
-> [Path (Set (Set n)) e] -> [Path (Set (Set n)) e]
forall (s :: * -> *) a.
(Collapsible s, Container (s a) a) =>
(a -> Bool) -> s a -> s a
keep
>               (Set [Symbol e] -> [Symbol e] -> Bool
forall c a. (Container c a, Eq a) => c -> a -> Bool
isNotIn ([Symbol e] -> Set [Symbol e] -> Set [Symbol e]
forall c a. Container c a => a -> c -> c
insert (Path (Set (Set n)) e -> [Symbol e]
forall n e. Path n e -> [Symbol e]
labels Path (Set (Set n)) e
p) (Set [Symbol e] -> Set [Symbol e])
-> Set [Symbol e] -> Set [Symbol e]
forall a b. (a -> b) -> a -> b
$ (Path (Set (Set n)) e -> [Symbol e])
-> Set (Path (Set (Set n)) e) -> Set [Symbol e]
forall (s :: * -> *) b1 b a.
(Collapsible s, Container (s b1) b) =>
(a -> b) -> s a -> s b1
tmap Path (Set (Set n)) e -> [Symbol e]
forall n e. Path n e -> [Symbol e]
labels Set (Path (Set (Set n)) e)
fps) ([Symbol e] -> Bool)
-> (Path (Set (Set n)) e -> [Symbol e])
-> Path (Set (Set n)) e
-> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Path (Set (Set n)) e -> [Symbol e]
forall n e. Path n e -> [Symbol e]
labels)
>               [Path (Set (Set n)) e]
front) (Set (Path (Set (Set n)) e)
 -> ([Path (Set (Set n)) e], Set (Path (Set (Set n)) e)))
-> Set (Path (Set (Set n)) e)
-> ([Path (Set (Set n)) e], Set (Path (Set (Set n)) e))
forall a b. (a -> b) -> a -> b
$ Path (Set (Set n)) e
-> Set (Path (Set (Set n)) e) -> Set (Path (Set (Set n)) e)
forall c a. Container c a => a -> c -> c
insert Path (Set (Set n)) e
p Set (Path (Set (Set n)) e)
fps
>     | Bool
otherwise = Set (State (Set n))
-> [Path (Set (Set n)) e]
-> [Path (Set (Set n)) e]
-> Set (Path (Set (Set n)) e)
-> ([Path (Set (Set n)) e], Set (Path (Set (Set n)) e))
forall e n.
(Ord e, Ord n, Enum n) =>
Set (State (Set n))
-> [Path (Set (Set n)) e]
-> [Path (Set (Set n)) e]
-> Set (Path (Set (Set n)) e)
-> ([Path (Set (Set n)) e], Set (Path (Set (Set n)) e))
passK Set (State (Set n))
goals [Path (Set (Set n)) e]
ps (Path (Set (Set n)) e
pPath (Set (Set n)) e
-> [Path (Set (Set n)) e] -> [Path (Set (Set n)) e]
forall a. a -> [a] -> [a]
:[Path (Set (Set n)) e]
front) Set (Path (Set (Set n)) e)
fps


%% verification 

> buildFSAsFromFFs :: (NFData e, Ord e) => ForbiddenSubstrings e ->
>                     ( Set e            -- alphabet
>                     , [FSA Integer e]  -- words
>                     , [FSA Integer e]  -- initials
>                     , [FSA Integer e]  -- free
>                     , [FSA Integer e]  -- finals
>                     )
> buildFSAsFromFFs :: ForbiddenSubstrings e
-> (Set e, [FSA Integer e], [FSA Integer e], [FSA Integer e],
    [FSA Integer e])
buildFSAsFromFFs ForbiddenSubstrings e
fs = (Set e
alphs, [FSA Integer e]
ws, [FSA Integer e]
is, [FSA Integer e]
frs, [FSA Integer e]
fis)
>     where alphs :: Set e
alphs        =  ForbiddenSubstrings e -> Set e
forall e. ForbiddenSubstrings e -> Set e
attestedUnits ForbiddenSubstrings e
fs
>           f :: Bool -> Bool -> [e] -> FSA n e
f Bool
h Bool
t        =  Set e -> Literal e -> FSA n e
forall n e. (Enum n, Ord n, Ord e) => Set e -> Literal e -> FSA n e
buildLiteral Set e
alphs (Literal e -> FSA n e) -> ([e] -> Literal e) -> [e] -> FSA n e
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Factor e -> Literal e
forall e. Factor e -> Literal e
forbidden (Factor e -> Literal e) -> ([e] -> Factor e) -> [e] -> Literal e
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
>                           (\[Set e]
x -> [Set e] -> Bool -> Bool -> Factor e
forall e. [Set e] -> Bool -> Bool -> Factor e
Substring [Set e]
x Bool
h Bool
t) ([Set e] -> Factor e) -> ([e] -> [Set e]) -> [e] -> Factor e
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (e -> Set e) -> [e] -> [Set e]
forall (s :: * -> *) b1 b a.
(Collapsible s, Container (s b1) b) =>
(a -> b) -> s a -> s b1
tmap e -> Set e
forall c a. Container c a => a -> c
singleton
>           buildHT :: Bool -> Bool -> Set [e] -> [FSA n e]
buildHT Bool
h Bool
t  =  ([e] -> FSA n e) -> [[e]] -> [FSA n e]
forall (s :: * -> *) b1 b a.
(Collapsible s, Container (s b1) b) =>
(a -> b) -> s a -> s b1
tmap (Bool -> Bool -> [e] -> FSA n e
forall n. (Enum n, Ord n) => Bool -> Bool -> [e] -> FSA n e
f Bool
h Bool
t) ([[e]] -> [FSA n e]) -> (Set [e] -> [[e]]) -> Set [e] -> [FSA n e]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Set [e] -> [[e]]
forall a. Set a -> [a]
Set.toList
>           ws :: [FSA Integer e]
ws           =  Bool -> Bool -> Set [e] -> [FSA Integer e]
forall n. (Enum n, Ord n) => Bool -> Bool -> Set [e] -> [FSA n e]
buildHT Bool
True   Bool
True   (ForbiddenSubstrings e -> Set [e]
forall e. ForbiddenSubstrings e -> Set [e]
forbiddenWords ForbiddenSubstrings e
fs)
>           is :: [FSA Integer e]
is           =  Bool -> Bool -> Set [e] -> [FSA Integer e]
forall n. (Enum n, Ord n) => Bool -> Bool -> Set [e] -> [FSA n e]
buildHT Bool
True   Bool
False  (ForbiddenSubstrings e -> Set [e]
forall e. ForbiddenSubstrings e -> Set [e]
forbiddenInitials ForbiddenSubstrings e
fs)
>           frs :: [FSA Integer e]
frs          =  Bool -> Bool -> Set [e] -> [FSA Integer e]
forall n. (Enum n, Ord n) => Bool -> Bool -> Set [e] -> [FSA n e]
buildHT Bool
False  Bool
False  (ForbiddenSubstrings e -> Set [e]
forall e. ForbiddenSubstrings e -> Set [e]
forbiddenFrees ForbiddenSubstrings e
fs)
>           fis :: [FSA Integer e]
fis          =  Bool -> Bool -> Set [e] -> [FSA Integer e]
forall n. (Enum n, Ord n) => Bool -> Bool -> Set [e] -> [FSA n e]
buildHT Bool
False  Bool
True   (ForbiddenSubstrings e -> Set [e]
forall e. ForbiddenSubstrings e -> Set [e]
forbiddenFinals ForbiddenSubstrings e
fs)

%% build FSA from FSAs

> combineFSAs :: (NFData e, Ord e) => ( Set e            -- alphabet
>                                     , [FSA Integer e]  -- words
>                                     , [FSA Integer e]  -- initials
>                                     , [FSA Integer e]  -- free
>                                     , [FSA Integer e]  -- finals
>                                     ) -> FSA Integer e
> combineFSAs :: (Set e, [FSA Integer e], [FSA Integer e], [FSA Integer e],
 [FSA Integer e])
-> FSA Integer e
combineFSAs (Set e
alphs,[FSA Integer e]
ws,[FSA Integer e]
is,[FSA Integer e]
frs,[FSA Integer e]
fis)
>     = [FSA Integer e] -> FSA Integer e
forall n e.
(Enum n, Ord n, NFData n, Ord e, NFData e) =>
[FSA n e] -> FSA n e
flatIntersection ([FSA Integer e] -> FSA Integer e)
-> [FSA Integer e] -> FSA Integer e
forall a b. (a -> b) -> a -> b
$ Set e -> FSA Integer e
forall e n. (Ord e, Enum n, Ord n) => Set e -> FSA n e
totalWithAlphabet Set e
alphs FSA Integer e -> [FSA Integer e] -> [FSA Integer e]
forall a. a -> [a] -> [a]
: [[FSA Integer e]] -> [FSA Integer e]
forall (t :: * -> *) a. Foldable t => t [a] -> [a]
concat [[FSA Integer e]
ws, [FSA Integer e]
is, [FSA Integer e]
frs, [FSA Integer e]
fis]

%% build FSA from forbidden factors
%% Since this uses renameStates the State type of the result will be Integer
%% This really needs to be as strict as possible, which I hope it isn't

> -- |Create an 'FSA' satisfying the conditions imposed by the
> -- given sets of forbidden substrings.
> buildFSA :: (NFData e, Ord e) => ForbiddenSubstrings e -> FSA Integer e
> buildFSA :: ForbiddenSubstrings e -> FSA Integer e
buildFSA = (Set e, [FSA Integer e], [FSA Integer e], [FSA Integer e],
 [FSA Integer e])
-> FSA Integer e
forall e.
(NFData e, Ord e) =>
(Set e, [FSA Integer e], [FSA Integer e], [FSA Integer e],
 [FSA Integer e])
-> FSA Integer e
combineFSAs ((Set e, [FSA Integer e], [FSA Integer e], [FSA Integer e],
  [FSA Integer e])
 -> FSA Integer e)
-> (ForbiddenSubstrings e
    -> (Set e, [FSA Integer e], [FSA Integer e], [FSA Integer e],
        [FSA Integer e]))
-> ForbiddenSubstrings e
-> FSA Integer e
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ForbiddenSubstrings e
-> (Set e, [FSA Integer e], [FSA Integer e], [FSA Integer e],
    [FSA Integer e])
forall e.
(NFData e, Ord e) =>
ForbiddenSubstrings e
-> (Set e, [FSA Integer e], [FSA Integer e], [FSA Integer e],
    [FSA Integer e])
buildFSAsFromFFs

\end{document}