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

LTK.Extract.SP

Description

Find forbidden subsequences of an automaton. Formerly known as LTK.ExtractSP.

Since: 0.2

Synopsis

Documentation

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.

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

Returns True iff the stringset represented by the given FSA is Strictly Piecewise, that is, if the FSA accepts all subsequences of every string it accepts.

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.