language-toolkit-1.2.0.0: A set of tools for analyzing languages via logic and automata
Copyright(c) 2017-20192023 Jim Rogers and Dakotah Lambert
LicenseMIT
Safe HaskellSafe-Inferred
LanguageHaskell2010
Extensions
  • ConstrainedClassMethods
  • MultiParamTypeClasses

LTK.Extract.SL

Description

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

Since: 0.2

Synopsis

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

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

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

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