Copyright	(c) 2017-20192023 Jim Rogers and Dakotah Lambert
License	MIT
Safe Haskell	Safe-Inferred
Language	Haskell2010
Extensions	ConstrainedClassMethods MultiParamTypeClasses

LTK.Extract.SL

Contents

Extracting forbidden substrings
Building automata
Determining SL

Description

Find forbidden substrings of an automaton. Formerly known as LTK.ExtractSL.

Since: 0.2

Synopsis

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)
}
data TaggedSubstring e
- = Free [e]
- | Initial [e]
- | Final [e]
- | Word [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
isSL :: (Ord e, Ord n) => FSA n e -> Bool
slQ :: (Ord e, Ord n) => FSA n e -> Integer

Documentation

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 #

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 #

Extracting forbidden substrings

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

Building automata

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

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

Determining SL

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

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

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