language-toolkit-1.2.0.0: A set of tools for analyzing languages via logic and automata
Copyright(c) 2019 Dakotah Lambert
LicenseMIT
Safe HaskellSafe-Inferred
LanguageHaskell2010

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

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

Show e => Show (TaggedSubstring e) # 
Instance details

Defined in LTK.Extract.SL

Eq e => Eq (TaggedSubstring e) # 
Instance details

Defined in LTK.Extract.SL

Ord e => Ord (TaggedSubstring e) # 
Instance details

Defined in LTK.Extract.SL

Ord e => Container (ForbiddenSubstrings e) (TaggedSubstring e) # 
Instance details

Defined in LTK.Extract.SL

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

Instances

Instances details
(Read e, Ord e) => Read (ForbiddenSubstrings e) # 
Instance details

Defined in LTK.Extract.SL

Show e => Show (ForbiddenSubstrings e) # 
Instance details

Defined in LTK.Extract.SL

Eq e => Eq (ForbiddenSubstrings e) # 
Instance details

Defined in LTK.Extract.SL

Ord e => Ord (ForbiddenSubstrings e) # 
Instance details

Defined in LTK.Extract.SL

Ord e => Container (ForbiddenSubstrings e) (TaggedSubstring e) # 
Instance details

Defined in LTK.Extract.SL

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

Instances

Instances details
(Eq e, Eq n) => Eq (ForbiddenPaths n e) # 
Instance details

Defined in LTK.Extract.SL

(Ord e, Ord n) => Ord (ForbiddenPaths n e) # 
Instance details

Defined in LTK.Extract.SL

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

Instances

Instances details
(Read e, Ord e) => Read (ForbiddenSubsequences e) # 
Instance details

Defined in LTK.Extract.SP

Show e => Show (ForbiddenSubsequences e) # 
Instance details

Defined in LTK.Extract.SP

Eq e => Eq (ForbiddenSubsequences e) # 
Instance details

Defined in LTK.Extract.SP

Ord e => Ord (ForbiddenSubsequences e) # 
Instance details

Defined in LTK.Extract.SP

Ord e => Container (ForbiddenSubsequences e) [e] # 
Instance details

Defined in LTK.Extract.SP

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.