| 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 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
- 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 ForbiddenSubstrings e Source #
A convenience-type for declaring collections of forbidden substrings. The member types are (lists of) the raw alphabet type (not (Symbol .))
Constructors
| ForbiddenSubstrings | |
Fields
| |
Instances
data ForbiddenPaths n e Source #
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
| |
Instances
| (Eq e, Eq n) => Eq (ForbiddenPaths n e) Source # | |
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) Source # | |
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 Source #
A sequence of symbols, possibly annotated with end-markers.
Instances
factorsFromPaths :: (Ord e, Ord n) => Set (Path n e) -> Set [Symbol e] Source #
Convert Set of Paths to Set of sequences of (Symbol e)
forbiddenSubstrings :: (Ord e, Ord n, Enum n) => FSA n e -> ForbiddenSubstrings e Source #
Forbidden substrings of the given FSA relative to its alphabet
buildFSA :: (NFData e, Ord e) => ForbiddenSubstrings e -> FSA Integer e Source #
Create an FSA satisfying the conditions imposed by the
given sets of forbidden substrings.
slQ :: (Ord e, Ord n) => FSA n e -> Integer Source #
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 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
| |
Instances
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.
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.
module LTK.Extract.TSL