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

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) Source #
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) Source #
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) Source #
Instance details Defined in LTK.Extract.SP Methods (==) :: ForbiddenSubsequences e -> ForbiddenSubsequences e -> Bool # (/=) :: ForbiddenSubsequences e -> ForbiddenSubsequences e -> Bool #
Ord e => Ord (ForbiddenSubsequences e) Source #
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] Source #
Instance details Defined in LTK.Extract.SP Methods isIn :: ForbiddenSubsequences e -> [e] -> Bool Source # isNotIn :: ForbiddenSubsequences e -> [e] -> Bool Source # contains :: [e] -> ForbiddenSubsequences e -> Bool Source # doesNotContain :: [e] -> ForbiddenSubsequences e -> Bool Source # isEmpty :: ForbiddenSubsequences e -> Bool Source # union :: ForbiddenSubsequences e -> ForbiddenSubsequences e -> ForbiddenSubsequences e Source # intersection :: ForbiddenSubsequences e -> ForbiddenSubsequences e -> ForbiddenSubsequences e Source # difference :: ForbiddenSubsequences e -> ForbiddenSubsequences e -> ForbiddenSubsequences e Source # symmetricDifference :: ForbiddenSubsequences e -> ForbiddenSubsequences e -> ForbiddenSubsequences e Source # empty :: ForbiddenSubsequences e Source # insert :: [e] -> ForbiddenSubsequences e -> ForbiddenSubsequences e Source # singleton :: [e] -> ForbiddenSubsequences e Source # isSubsetOf :: ForbiddenSubsequences e -> ForbiddenSubsequences e -> Bool Source # isSupersetOf :: ForbiddenSubsequences e -> ForbiddenSubsequences e -> Bool Source # isProperSubsetOf :: ForbiddenSubsequences e -> ForbiddenSubsequences e -> Bool Source # isProperSupersetOf :: ForbiddenSubsequences e -> ForbiddenSubsequences e -> Bool Source #

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

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

The stringset represented by the forbiddenSubsequences.

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

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

(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 Source #

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