Copyright	(c) 2017-20202022-2023 Dakotah Lambert
License	MIT
Safe Haskell	Safe-Inferred
Language	Haskell2010
Extensions	Cpp ConstrainedClassMethods MultiParamTypeClasses

LTK.Extract.SP

Description

Find forbidden subsequences of an automaton. Formerly known as LTK.ExtractSP.

Since: 0.2

Synopsis

data ForbiddenSubsequences e = ForbiddenSubsequences {
- attestedAlphabet :: Set e
- getSubsequences :: Set [e]
}
forbiddenSubsequences :: (Ord n, Ord e) => FSA n e -> ForbiddenSubsequences e
fsaFromForbiddenSubsequences :: (Ord e, NFData e) => ForbiddenSubsequences e -> FSA Integer e
isSP :: (Ord n, Ord e) => FSA n e -> Bool
isSSQ :: Eq a => [a] -> [a] -> Bool
subsequenceClosure :: (Ord n, Ord e) => FSA n e -> FSA n e

Documentation

data ForbiddenSubsequences e #

A convenience-type for declaring collections of forbidden subsequences. The member types are (lists of) the raw alphabet type (not (Symbol .))

Constructors

ForbiddenSubsequences
Fields attestedAlphabet :: Set e getSubsequences :: Set [e]

Instances

Instances details

(Read e, Ord e) => Read (ForbiddenSubsequences e) #
Instance details Defined in LTK.Extract.SP Methods readsPrec :: Int -> ReadS (ForbiddenSubsequences e) # readList :: ReadS [ForbiddenSubsequences e] # readPrec :: ReadPrec (ForbiddenSubsequences e) # readListPrec :: ReadPrec [ForbiddenSubsequences e] #
Show e => Show (ForbiddenSubsequences e) #
Instance details Defined in LTK.Extract.SP Methods showsPrec :: Int -> ForbiddenSubsequences e -> ShowS # show :: ForbiddenSubsequences e -> String # showList :: [ForbiddenSubsequences e] -> ShowS #
Eq e => Eq (ForbiddenSubsequences e) #
Instance details Defined in LTK.Extract.SP Methods (==) :: ForbiddenSubsequences e -> ForbiddenSubsequences e -> Bool # (/=) :: ForbiddenSubsequences e -> ForbiddenSubsequences e -> Bool #
Ord e => Ord (ForbiddenSubsequences e) #
Instance details Defined in LTK.Extract.SP Methods compare :: ForbiddenSubsequences e -> ForbiddenSubsequences e -> Ordering # (<) :: ForbiddenSubsequences e -> ForbiddenSubsequences e -> Bool # (<=) :: ForbiddenSubsequences e -> ForbiddenSubsequences e -> Bool # (>) :: ForbiddenSubsequences e -> ForbiddenSubsequences e -> Bool # (>=) :: ForbiddenSubsequences e -> ForbiddenSubsequences e -> Bool # max :: ForbiddenSubsequences e -> ForbiddenSubsequences e -> ForbiddenSubsequences e # min :: ForbiddenSubsequences e -> ForbiddenSubsequences e -> ForbiddenSubsequences e #
Ord e => Container (ForbiddenSubsequences e) [e] #
Instance details Defined in LTK.Extract.SP Methods isIn :: ForbiddenSubsequences e -> [e] -> Bool # isNotIn :: ForbiddenSubsequences e -> [e] -> Bool # contains :: [e] -> ForbiddenSubsequences e -> Bool # doesNotContain :: [e] -> ForbiddenSubsequences e -> Bool # isEmpty :: ForbiddenSubsequences e -> Bool # union :: ForbiddenSubsequences e -> ForbiddenSubsequences e -> ForbiddenSubsequences e # intersection :: ForbiddenSubsequences e -> ForbiddenSubsequences e -> ForbiddenSubsequences e # difference :: ForbiddenSubsequences e -> ForbiddenSubsequences e -> ForbiddenSubsequences e # symmetricDifference :: ForbiddenSubsequences e -> ForbiddenSubsequences e -> ForbiddenSubsequences e # empty :: ForbiddenSubsequences e # insert :: [e] -> ForbiddenSubsequences e -> ForbiddenSubsequences e # singleton :: [e] -> ForbiddenSubsequences e # isSubsetOf :: ForbiddenSubsequences e -> ForbiddenSubsequences e -> Bool # isSupersetOf :: ForbiddenSubsequences e -> ForbiddenSubsequences e -> Bool # isProperSubsetOf :: ForbiddenSubsequences e -> ForbiddenSubsequences e -> Bool # isProperSupersetOf :: ForbiddenSubsequences e -> ForbiddenSubsequences e -> Bool #

forbiddenSubsequences :: (Ord n, Ord e) => FSA n e -> ForbiddenSubsequences e #

Given an FSA \(A\), returns the set of subsequences \(v\) such that for all words \(w\), \(v\sqsubseteq w\) implies that \(w\) is not accepted by \(A\).

fsaFromForbiddenSubsequences :: (Ord e, NFData e) => ForbiddenSubsequences e -> FSA Integer e #

The stringset represented by the forbiddenSubsequences.

isSP :: (Ord n, Ord e) => FSA n e -> Bool #

Returns True iff the stringset represented by the given FSA is Strictly Piecewise, that is, if the FSA accepts all subsequences of every string it accepts.

isSSQ :: Eq a => [a] -> [a] -> Bool #

(isSSQ a b) returns true iff b contains the symbols of a in order, but not necessarily adjacently.

subsequenceClosure :: (Ord n, Ord e) => FSA n e -> FSA n e #

Returns an FSA that accepts every string accepted by the original, as well as every subsequence of these strings.