Safe Haskell	None
Language	Haskell2010

Modelling.PetriNet.Reach.Filter

Contents

Pattern detection
Solution set validation
Configuration

Description

Module for filtering sequences in Petri net reach/deadlock tasks.

This module provides functions to filter out sequences and solution sets based on various criteria that make instances too simple or too complicated:

Cyclic patterns: [t3, t2, t1, t4, t3, t2, t1, t4]
Repetitive subsequences: [t4, t4, t4, t4] as prefix/suffix
Grouped repeats: [t3, t3, t2, t2, t1, t1, t4, t4]
Too many shortest solutions
Insufficient transition coverage in solutions
Insufficient number of transitions absent from all solutions
Solutions are (not) all permutations of each other

The filtering only happens on/with minimal solution sequences for a task.

Synopsis

isCyclicPatternWithAnyOf :: Eq a => [Int] -> [a] -> Bool
hasRepetitiveSubsequence :: Eq a => Int -> [a] -> Bool
hasSpaceballsPrefix :: (Enum a, Eq a) => Int -> [a] -> Bool
hasGroupedRepeats :: Eq a => [a] -> Bool
hasInsufficientTransitionCoverage :: Ord a => Int -> [a] -> Ratio Int -> Bool
shouldDiscardSolutions :: (Enum a, Ord a) => FilterConfig -> Int -> [[a]] -> Bool
data FilterConfig = FilterConfig {
- rejectGroupedRepeats :: !Bool
- repetitiveSubsequenceThreshold :: !(Maybe Int)
- spaceballsPrefixThreshold :: !(Maybe Int)
- forbiddenCycleLengths :: ![Int]
- requireCycleLengthsAny :: ![Int]
- solutionSetLimit :: !(Maybe Int)
- requireSolutionsArePermutations :: !Bool
- absentTransitionsRequirement :: !Int
- transitionCoverageRequirement :: !(Ratio Int)
}
defaultFilterConfig :: FilterConfig
noFiltering :: FilterConfig

Pattern detection

isCyclicPatternWithAnyOf :: Eq a => [Int] -> [a] -> Bool Source #

Check if a sequence follows a cyclic pattern (e.g., [t3,t2,t1,t4,t3,t2,t1,t4]) The pattern is considered cyclic if it can be represented as `take n (cycle pattern)` where `length pattern` is one of the given cycle lengths

hasRepetitiveSubsequence :: Eq a => Int -> [a] -> Bool Source #

Check if a sequence has repetitive subsequences as prefix or suffix (e.g., [t4,t4,t4,t4] at the beginning or end)

hasSpaceballsPrefix :: (Enum a, Eq a) => Int -> [a] -> Bool Source #

Check if a sequence begins with a Spaceballs PIN pattern

hasGroupedRepeats :: Eq a => [a] -> Bool Source #

Check if a sequence has grouped repeats (e.g., [t3,t3,t3,t1,t1,t1,t4,t4]) This means each unique element appears in consecutive groups of size > 1

hasInsufficientTransitionCoverage :: Ord a => Int -> [a] -> Ratio Int -> Bool Source #

Check if a sequence has insufficient transition coverage

Solution set validation

shouldDiscardSolutions :: (Enum a, Ord a) => FilterConfig -> Int -> [[a]] -> Bool Source #

Check if a set of solutions should be discarded according to the given configuration

Returns True if the solution set should be discarded (filtered out), False if it should be kept.

Configuration

data FilterConfig Source #

Configuration for sequence filtering

Constructors

FilterConfig

Fields

rejectGroupedRepeats :: !Bool
Enable filtering of grouped repeats (e.g., [t3,t3,t3,t2,t2,t2,t1,t1])
repetitiveSubsequenceThreshold :: !(Maybe Int)
Threshold length for repetitive subsequences to reject (e.g., [t4,t4,t4,t4] as prefix/suffix)
Sequences with repetitive subsequences of at least this length are filtered out. Nothing means no filtering of such repetitive subsequences.
spaceballsPrefixThreshold :: !(Maybe Int)
Threshold length for Spaceballs PIN prefix pattern to reject (e.g., [t1,t2,t3,t4,t5] as prefix)
Sequences with Spaceballs prefix patterns of at least this length are filtered out. Nothing means no filtering of such Spaceballs PIN prefix patterns.
forbiddenCycleLengths :: ![Int]
Forbidden cycle lengths for cyclic patterns to reject (e.g., [t3,t2,t1,t4,t3,t2,t1,t4]; always full cycles checked)
Sequences with cyclic patterns having one of these cycle lengths are filtered out. The list should be sorted and contain only true divisors of the target sequence length. An empty list means no rejection filtering of such cyclic patterns.
requireCycleLengthsAny :: ![Int]
If nonempty, cycle lengths any of which is required for acceptance
Solution sets where no solution has a cyclic pattern with one of these cycle lengths are filtered out. The list should be sorted and contain only divisors of the target sequence length. An empty list means no acceptance requirement for cyclic patterns.
solutionSetLimit :: !(Maybe Int)
Maximum number of shortest solution sequences in a solution set
Solution sets with more than this many sequences are filtered out. Nothing means no limit on the number of solution sequences.
requireSolutionsArePermutations :: !Bool
Whether all (shortest) solutions must be permutations of each other
- True means filter out instances where solutions are NOT all permutations
- False means don't care about the permutation property
absentTransitionsRequirement :: !Int
Minimum number of transitions required to be absent from all solutions
At least this many transitions from the available transitions must appear in none of the solution sequences. A value of 0 means no filtering based on absent transitions.
transitionCoverageRequirement :: !(Ratio Int)
Minimum transition coverage required for each solution
Each solution must use at least this fraction of available transitions. For example, 4 % 5 requires that each solution uses at least 80% of the available transitions. A value of 0 means no minimum coverage requirement.