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

LTK.Extract

Description

Functions used for extracting constraints from automata. Each complexity class for which these operations are implemented has a separate Extract.class module as well.

This module does not export decision algorithms. For those, see Decide.

Since: 0.2

Synopsis

data TaggedSubstring e
- = Free [e]
- | Initial [e]
- | Final [e]
- | Word [e]
data ForbiddenSubstrings e = ForbiddenSubstrings {
- attestedUnits :: Set e
- forbiddenWords :: Set [e]
- forbiddenInitials :: Set [e]
- forbiddenFrees :: Set [e]
- forbiddenFinals :: Set [e]
}
data ForbiddenPaths n e = ForbiddenPaths {
- initialPaths :: Set (Path n e)
- freePaths :: Set (Path n e)
- finalPaths :: Set (Path n e)
}
factorsFromPaths :: (Ord e, Ord n) => Set (Path n e) -> Set [Symbol e]
forbiddenSubstrings :: (Ord e, Ord n, Enum n) => FSA n e -> ForbiddenSubstrings e
buildFSA :: (NFData e, Ord e) => ForbiddenSubstrings e -> FSA Integer e
slQ :: (Ord e, Ord n) => FSA n e -> Integer
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
isSSQ :: Eq a => [a] -> [a] -> Bool
subsequenceClosure :: (Ord n, Ord e) => FSA n e -> FSA n e
module LTK.Extract.TSL

Documentation

data TaggedSubstring e #

A sequence of symbols, possibly annotated with end-markers.

Constructors

Free [e]
Initial [e]
Final [e]
Word [e]

Instances

Instances details

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

data ForbiddenSubstrings e #

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

Constructors

ForbiddenSubstrings
Fields attestedUnits :: Set e Symbols that actually label transitions forbiddenWords :: Set [e] Sequences of symbols that cannot occur as words forbiddenInitials :: Set [e] Sequences of symbols that cannot occur initially forbiddenFrees :: Set [e] Sequences of symbols that cannot occur anywhere forbiddenFinals :: Set [e] Sequences of symbols that cannot occur finally

Instances

Instances details

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

data ForbiddenPaths n e #

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.

Constructors

ForbiddenPaths
Fields initialPaths :: Set (Path n e) Paths witnessing forbidden initial factors freePaths :: Set (Path n e) Paths witnessing forbidden free factors finalPaths :: Set (Path n e) Paths witnessing forbidden final factors

Instances

Instances details

(Eq e, Eq n) => Eq (ForbiddenPaths n e) #
Instance details Defined in LTK.Extract.SL Methods (==) :: ForbiddenPaths n e -> ForbiddenPaths n e -> Bool # (/=) :: ForbiddenPaths n e -> ForbiddenPaths n e -> Bool #
(Ord e, Ord n) => Ord (ForbiddenPaths n e) #
Instance details Defined in LTK.Extract.SL Methods compare :: 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 # max :: ForbiddenPaths n e -> ForbiddenPaths n e -> ForbiddenPaths n e # min :: ForbiddenPaths n e -> ForbiddenPaths n e -> ForbiddenPaths n e #

factorsFromPaths :: (Ord e, Ord n) => Set (Path n e) -> Set [Symbol e] #

Convert Set of Paths to Set of sequences of (Symbol e)

forbiddenSubstrings :: (Ord e, Ord n, Enum n) => FSA n e -> ForbiddenSubstrings e #

Forbidden substrings of the given FSA relative to its alphabet

buildFSA :: (NFData e, Ord e) => ForbiddenSubstrings e -> FSA Integer e #

Create an FSA satisfying the conditions imposed by the given sets of forbidden substrings.

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

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\).

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.

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.

module LTK.Extract.TSL