dfalearningtoolkit

package
v1.0.0 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: May 30, 2021 License: GPL-3.0 Imports: 16 Imported by: 0

Documentation

Index

Constants

View Source 
const (
	REJECTING  = iota // 0
	ACCEPTING         // 1
	UNLABELLED        // 2
)

Constants which represent the 3 possible state labels.

Variables

View Source 
var SymbolAlphabetMappingAbbadingo = map[int]string{0: "a", 1: "b"}

SymbolAlphabetMappingAbbadingo represents the symbol-alphabet mapping for the Abbadingo competition standard (using only a's and b's / 0s and 1s).

Functions

func AbbadingoDataset 

func AbbadingoDataset(dfa DFA, sparsityPercentage float64, testingRatio float64) (Dataset, Dataset)

AbbadingoDataset returns a training and testing Dataset using the Abbadingo protocol given a DFA, a sparsity percentage and a training:testing ratio.

func AbbadingoDatasetExact 

func AbbadingoDatasetExact(dfa DFA, trainingSetSize int, testingSetSize int) (Dataset, Dataset)

AbbadingoDatasetExact returns a training and testing Dataset using the Abbadingo protocol given a DFA and a set size for each.

func AbbadingoInstance 

func AbbadingoInstance(numberOfStates int, exact bool, sparsityPercentage float64, testingRatio float64) (DFA, Dataset, Dataset)

AbbadingoInstance returns a random DFA using the Abbadingo protocol given a number of states while returning a training and testing dataset built on the generated DFA given a sparsity percentage and a training:testing ratio. If exact is set to true, the resultant DFA will have the required depth as per Abbadingo protocol.

func AbbadingoInstanceExact 

func AbbadingoInstanceExact(numberOfStates int, exact bool, trainingSetSize int, testingSetSize int) (DFA, Dataset, Dataset)

AbbadingoInstanceExact returns a random DFA using the Abbadingo protocol given a number of states while returning a training and testing dataset built on the generated DFA given a set size for each. If exact is set to true, the resultant DFA will have the required depth as per Abbadingo protocol.

func BlueFringeEDSM 

func BlueFringeEDSM(APTA DFA) (DFA, MergeData)

BlueFringeEDSM is a Blue Fringe version of Evidence Driven State-Merging. It takes a DFA (APTA) as an argument which is used within the blue-fringe search.

func BlueFringeEDSMFromDataset 

func BlueFringeEDSMFromDataset(dataset Dataset) (DFA, MergeData)

BlueFringeEDSMFromDataset is a Blue Fringe version of Evidence Driven State-Merging. It takes a dataset as an argument which is used to generate an APTA.

func BlueFringeSearchUsingScoringFunction 

func BlueFringeSearchUsingScoringFunction(statePartition StatePartition, scoringFunction ScoringFunction) (StatePartition, MergeData)

BlueFringeSearchUsingScoringFunction deterministically merges possible state pairs within red-blue sets. The state pair to be merged is chosen using a scoring function passed as a parameter. Returns the resultant state partition and merge data when no more valid merges are possible.

func DefaultStaminaDataset 

func DefaultStaminaDataset(dfa DFA, sparsityPercentage float64) (Dataset, Dataset)

DefaultStaminaDataset returns a training and testing Dataset using the Stamina protocol given a DFA and a sparsity percentage. The default values for the initial strings generated (20000) and the maximum testing string instances (1500) which were used within the Stamina competition are used within this function.

func DefaultStaminaInstance 

func DefaultStaminaInstance(alphabetSize, targetDFASize int, sparsityPercentage float64) (DFA, Dataset, Dataset)

DefaultStaminaInstance returns a random DFA using the Stamina protocol given a target size while returning a training and testing dataset built on the generated DFA given a sparsity percentage. The default values for the initial strings generated (20000) and the maximum testing string instances (1500) which were used within the Stamina competition are used within this function.

func ExhaustiveEDSM 

func ExhaustiveEDSM(APTA DFA) (DFA, MergeData)

ExhaustiveEDSM is a greedy version of Evidence Driven State-Merging. It takes a DFA (APTA) as an argument which is used within the greedy search.

func ExhaustiveEDSMFromDataset 

func ExhaustiveEDSMFromDataset(dataset Dataset) (DFA, MergeData)

ExhaustiveEDSMFromDataset is a greedy version of Evidence Driven State-Merging. It takes a dataset as an argument which is used to generate an APTA.

func ExhaustiveSearchUsingScoringFunction 

func ExhaustiveSearchUsingScoringFunction(statePartition StatePartition, scoringFunction ScoringFunction) (StatePartition, MergeData)

ExhaustiveSearchUsingScoringFunction deterministically merges all possible state pairs. The state pair to be merged is chosen using a scoring function passed as a parameter. Returns the resultant state partition and merge data when no more valid merges are possible.

func GRBM 

func GRBM(statePartition StatePartition) (StatePartition, MergeData)

GRBM deterministically merges possible state pairs within red-blue sets. The state pair to be merged is chosen using a scoring function passed as a parameter. Returns the resultant state partition and merge data when no more valid merges are possible.

func GeneralizedRedBlueMerging 

func GeneralizedRedBlueMerging(APTA DFA) (DFA, MergeData)

GeneralizedRedBlueMerging is a. It takes a DFA (APTA) as an argument which is used within the greedy search.

func GeneralizedRedBlueMergingFromDataset 

func GeneralizedRedBlueMergingFromDataset(dataset Dataset) (DFA, MergeData)

GeneralizedRedBlueMergingFromDataset is a. It takes a dataset as an argument which is used to generate an APTA.

func GenerateBlueSetFromRedSetWithShuffle 

func GenerateBlueSetFromRedSetWithShuffle(statePartition *StatePartition, redSet map[int]util.Void) []int

GenerateBlueSetFromRedSetWithShuffle generates the blue set given the state partition and the red set within the Red-Blue framework such as the GeneralizedRedBlueMerging function. It generates and returns the blue set in arbitrary order.

func GenerateOrderedBlueSetFromRedSet 

func GenerateOrderedBlueSetFromRedSet(statePartition *StatePartition, redSet map[int]util.Void) []int

GenerateOrderedBlueSetFromRedSet generates the blue set given the state partition and the red set within the Red-Blue framework such as the BlueFringeSearchUsingScoringFunction function. It generates and returns the blue set in canonical order.

func RPNI 

func RPNI(APTA DFA) (DFA, MergeData)

RPNI returns a DFA and merge data generated by the regular positive and negative inference (RPNI) algorithm. It takes an APTA as a parameter which is passed to the RPNISearch function.

func RPNIFromDataset 

func RPNIFromDataset(dataset Dataset) (DFA, MergeData)

RPNIFromDataset returns a DFA and merge data generated by the regular positive and negative inference (RPNI) algorithm. It takes a dataset as a parameter which is used to generate an APTA while passing it to the RPNI function.

func RPNISearch 

func RPNISearch(statePartition StatePartition) (StatePartition, MergeData)

RPNISearch deterministically merges all possible state pairs within red-blue framework. The first valid merge with respect to the rejecting examples is chosen. Returns the resultant state partition and merge data when no more valid merges are possible. Used by the regular positive and negative inference (RPNI) algorithm.

func StaminaDataset 

func StaminaDataset(dfa DFA, sparsityPercentage float64, initialStringsGenerated, maximumTestingStringInstances int) (Dataset, Dataset)

StaminaDataset returns a training and testing Dataset using the Stamina protocol given a DFA and a sparsity percentage. This process is described in http://stamina.chefbe.net/samples and in Walkinshaw, N., Lambeau, B., Damas, C., Bogdanov, K., & Dupont, P. (2012). STAMINA: a competition to encourage the development and assessment of software model inference techniques. Empirical Software Engineering, 18(4), 791–824. doi:10.1007/s10664-012-9210-3

func StaminaInstance 

func StaminaInstance(alphabetSize, targetDFASize int, sparsityPercentage float64, initialStringsGenerated, maximumTestingStringInstances int) (DFA, Dataset, Dataset)

StaminaInstance returns a random DFA using the Stamina protocol given a target size while returning a training and testing dataset built on the generated DFA given a sparsity percentage, an initial string generated value, and a maximum testing string instances value.

func UpdateOrderedRedBlueSets 

func UpdateOrderedRedBlueSets(statePartition *StatePartition, redStates []int) ([]int, []int)

UpdateOrderedRedBlueSets updates the red and blue sets given the state partition and the red set within the Red-Blue framework such as the BlueFringeSearchUsingScoringFunction function. It returns the red and blue sets in canonical order. This is used when the state partition is changed or when new states have been added to the red set.

func UpdateRedBlueSets 

func UpdateRedBlueSets(statePartition *StatePartition, redStates *[]int) []int

UpdateRedBlueSets updates the red and blue sets given the state partition and the red set within the Red-Blue framework such as the GeneralizedRedBlueMerging function. It returns the blue set and modifies the red set via its pointer. This is used when the state partition is changed or when new states have been added to the red set.

func UpdateRedBlueSetsWithShuffle 

func UpdateRedBlueSetsWithShuffle(statePartition *StatePartition, redStates *[]int) []int

UpdateRedBlueSetsWithShuffle updates the red and blue sets given the state partition and the red set within the Red-Blue framework such as the GeneralizedRedBlueMerging function. It returns the blue set and modifies the red set via its pointer. Both sets are shuffled . This is used when the state partition is changed or when new states have been added to the red set.

func UpdateWindow 

func UpdateWindow(window []int, statePartition StatePartition) []int

UpdateWindow updates a window given the state partition within a Windowed framework such as the WindowedSearchUsingScoringFunction function. It returns the new window as a slice of integers. This works by gathering the root of each block within the previous window and assigns it to the position of the first index of any block which is part of that block. This is used to avoid attempting merges more than once within a windowed search.

func WindowedEDSM 

func WindowedEDSM(APTA DFA, windowSize int, windowGrow float64) (DFA, MergeData)

WindowedEDSM is a windowed version of Evidence Driven State-Merging. It takes a DFA (APTA) as an argument which is used within the windowed search.

func WindowedEDSMFromDataset 

func WindowedEDSMFromDataset(dataset Dataset, windowSize int, windowGrow float64) (DFA, MergeData)

WindowedEDSMFromDataset is a windowed version of Evidence Driven State-Merging. It takes a dataset as an argument which is used to generate an APTA.

func WindowedSearchUsingScoringFunction 

func WindowedSearchUsingScoringFunction(statePartition StatePartition, windowSize int, windowGrow float64, scoringFunction ScoringFunction) (StatePartition, MergeData)

WindowedSearchUsingScoringFunction deterministically merges state pairs within a given window. The state pair to be merged is chosen using a scoring function passed as a parameter. Returns the resultant state partition and merge data when no more valid merges are possible.

Types

type Block 

type Block struct {
	Root        int        // Parent block of state.
	Size        int        // Size (score) of block.
	Link        int        // Index of next state within the block.
	Label       StateLabel // Label of block.
	Changed     bool       // Whether block has been changed.
	Transitions []int      // Transition Table where each element corresponds to a transition for each symbol.
}

Block struct which represents a block within a partition.

type DFA 

type DFA struct {
	States          []State // Slice of states within the DFA where the index is the State ID.
	Alphabet        []int   // Alphabet within DFA.
	StartingStateID int     // The ID of the starting state of the DFA.
	// contains filtered or unexported fields
}

DFA struct which represents a DFA.

func AbbadingoDFA 

func AbbadingoDFA(numberOfStates int, exact bool) DFA

AbbadingoDFA returns a random DFA using the Abbadingo protocol given a number of states. If exact is set to true, the resultant DFA will have the required depth as per Abbadingo protocol.

func DFAFromJSON 

func DFAFromJSON(filePath string) (DFA, bool)

DFAFromJSON returns a DFA read from a JSON file given a file path. The boolean value returned is set to true if DFA was read successfully.

func GetDFAFromStaminaFile 

func GetDFAFromStaminaFile(fileName string) DFA

GetDFAFromStaminaFile returns a DFA from a Stamina-Format File (adl).

func NewDFA 

func NewDFA() DFA

NewDFA initializes a new empty DFA.

func StaminaDFA 

func StaminaDFA(alphabetSize int, targetDFASize int) DFA

StaminaDFA returns a random DFA using the Stamina protocol given a number of states. This process is described in http://stamina.chefbe.net/machines and in Walkinshaw, N., Lambeau, B., Damas, C., Bogdanov, K., & Dupont, P. (2012). STAMINA: a competition to encourage the development and assessment of software model inference techniques. Empirical Software Engineering, 18(4), 791–824. doi:10.1007/s10664-012-9210-3

func (DFA) AcceptingStates 

func (dfa DFA) AcceptingStates() []int

AcceptingStates returns state IDs of accepting states within DFA.

func (DFA) AcceptingStatesCount 

func (dfa DFA) AcceptingStatesCount() int

AcceptingStatesCount returns the number of accepting states within DFA.

func (DFA) Accuracy 

func (dfa DFA) Accuracy(dataset Dataset) float64

Accuracy returns the DFA's Accuracy with respect to a dataset.

func (*DFA) AddSinkState 

func (dfa *DFA) AddSinkState() int

AddSinkState adds a sink state within DFA. This is used to convert a non-complete DFA to a complete DFA by adding a sink state.

func (*DFA) AddState 

func (dfa *DFA) AddState(stateLabel StateLabel) int

AddState adds a new state to the DFA with the corresponding State Label. Returns the new state's ID (index).

func (*DFA) AddSymbol 

func (dfa *DFA) AddSymbol()

AddSymbol adds a new symbol to the DFA.

func (*DFA) AddTransition 

func (dfa *DFA) AddTransition(symbol int, fromStateID int, toStateID int)

AddTransition adds a new transition for a given symbol from one state to another.

func (DFA) AllStates 

func (dfa DFA) AllStates() []int

AllStates returns all state IDs within DFA.

func (*DFA) CalculateDepthAndOrder 

func (dfa *DFA) CalculateDepthAndOrder()

CalculateDepthAndOrder computes the depth and Order for each state within DFA. This is done by traversing the DFA in a breadth-first order.

func (*DFA) ChangeRejectingStatesToUnlabelled 

func (dfa *DFA) ChangeRejectingStatesToUnlabelled()

ChangeRejectingStatesToUnlabelled changes all rejecting states within the DFA to unlabelled.

func (DFA) Clone 

func (dfa DFA) Clone() DFA

Clone returns a clone of the DFA.

func (*DFA) Depth 

func (dfa *DFA) Depth() int

Depth returns the DFA's depth which is defined as the maximum over all nodes x of the length of the shortest path from the root to x.

func (DFA) Describe 

func (dfa DFA) Describe(detail bool)

Describe prints the details of the DFA. If detail is set to true, each state and each transition will also be printed.

func (DFA) Equal 

func (dfa DFA) Equal(dfa2 DFA) bool

Equal checks whether DFA is equal to the given DFA. This function makes use of DeepEqual and if it returns false, it does not necessarily mean that the DFAs are not equal. Use SameAs() for equivalence.

func (*DFA) IndistinguishableStatePairs 

func (dfa *DFA) IndistinguishableStatePairs() []StateIDPair

IndistinguishableStatePairs returns a slice of indistinguishable state pairs within DFA. P. Linz, An Introduction to Formal Languages and Automata. Jones & Bartlett Publishers, 2011.

func (DFA) IsComplete 

func (dfa DFA) IsComplete() bool

IsComplete returns true if DFA is complete, false is returned otherwise.

func (DFA) IsTree 

func (dfa DFA) IsTree() bool

IsTree returns true if DFA is a tree, false is returned otherwise.

func (DFA) IsValidPanic 

func (dfa DFA) IsValidPanic()

IsValidPanic checks whether DFA is valid. Panics if not valid. Used for error checking.

func (DFA) IsValidSafe 

func (dfa DFA) IsValidSafe() bool

IsValidSafe checks whether DFA is valid. Returns false if not valid.

func (DFA) LabelledStates 

func (dfa DFA) LabelledStates() []int

LabelledStates returns state IDs of labelled states within DFA.

func (DFA) LabelledStatesCount 

func (dfa DFA) LabelledStatesCount() int

LabelledStatesCount returns the number of labelled states (accepting or rejecting) within DFA.

func (DFA) LeavesCount 

func (dfa DFA) LeavesCount() int

LeavesCount returns the number of leaves within DFA.

func (DFA) LoopsCount 

func (dfa DFA) LoopsCount() int

LoopsCount returns the number of loops within DFA.

func (DFA) Minimise 

func (dfa DFA) Minimise() DFA

Minimise returns a minimised version of the DFA. P. Linz, An Introduction to Formal Languages and Automata. Jones & Bartlett Publishers, 2011.

func (*DFA) OrderedStates 

func (dfa *DFA) OrderedStates() []int

OrderedStates returns the state IDs in order.

func (DFA) RejectingStates 

func (dfa DFA) RejectingStates() []int

RejectingStates returns state IDs of rejecting states within DFA.

func (DFA) RejectingStatesCount 

func (dfa DFA) RejectingStatesCount() int

RejectingStatesCount returns the number of rejecting states within DFA.

func (*DFA) RemoveNonAcceptingLeaves 

func (dfa *DFA) RemoveNonAcceptingLeaves()

RemoveNonAcceptingLeaves removes all states which are leaves within DFA and are not accepting states.

func (*DFA) RemoveState 

func (dfa *DFA) RemoveState(stateID int)

RemoveState removes a state from DFA with the corresponding State ID.

func (*DFA) RemoveTransition 

func (dfa *DFA) RemoveTransition(symbol int, fromStateID int)

RemoveTransition removes a transition for a given symbol from one state to another.

func (*DFA) RemoveUnreachableStates 

func (dfa *DFA) RemoveUnreachableStates()

RemoveUnreachableStates removes unreachable states from DFA.

func (DFA) SameAs 

func (dfa DFA) SameAs(dfa2 DFA) bool

SameAs checks whether DFA is the same as the given DFA.

func (*DFA) SetOrderAsID 

func (dfa *DFA) SetOrderAsID() DFA

SetOrderAsID returns a new DFA where the State IDs are the order of the states within the original DFA.

func (DFA) StartingState 

func (dfa DFA) StartingState() *State

StartingState returns a pointer to the starting state within the DFA.

func (DFA) StructurallyComplete 

func (dfa DFA) StructurallyComplete(dataset Dataset) bool

StructurallyComplete checks if DFA is structurally complete with respect to a Dataset.

func (DFA) SymmetricallyStructurallyComplete 

func (dfa DFA) SymmetricallyStructurallyComplete(dataset Dataset) bool

SymmetricallyStructurallyComplete checks if DFA is symmetrically structurally complete with respect to a Dataset.

func (*DFA) ToDOT 

func (dfa *DFA) ToDOT(filePath string, symbolMapping map[int]string, showOrder bool, topDown bool)

ToDOT creates a .dot file using the DOT language. This DOT file contains a representation for the given DFA which can then be used to generate a visual representation of the DFA. The symbolMapping parameter is a map which maps each symbol within the alphabet to a string. This can be set to nil, which will map each symbol with a number starting from 0. If showOrder is set to true, the canonical order of the states is shown inside the node within DFA. If topDown is set to true, the visual representation will be top down. A left to right representation is used otherwise. This function is also called from all of the functions below.

func (DFA) ToJPG 

func (dfa DFA) ToJPG(filePath string, symbolMapping map[int]string, showOrder bool, topDown bool) bool

ToJPG creates and saves a .jpg image which represents the DFA to the given file path. Please note that GraphViz must be downloaded and installed before hand from https://graphviz.org/download/. The symbolMapping parameter is a map which maps each symbol within the alphabet to a string. This can be set to nil, which will map each symbol with a number starting from 0. If showOrder is set to true, the canonical order of the states is shown inside the node within DFA. If topDown is set to true, the visual representation will be top down. A left to right representation is used otherwise. Returns true if successful or false if an error occurs.

func (DFA) ToJSON 

func (dfa DFA) ToJSON(filePath string) bool

ToJSON saves the DFA to a JSON file given a file path.

func (DFA) ToPDF 

func (dfa DFA) ToPDF(filePath string, symbolMapping map[int]string, showOrder bool, topDown bool) bool

ToPDF creates and saves a .pdf file which represents the DFA to the given file path. Please note that GraphViz must be downloaded and installed before hand from https://graphviz.org/download/. The symbolMapping parameter is a map which maps each symbol within the alphabet to a string. This can be set to nil, which will map each symbol with a number starting from 0. If showOrder is set to true, the canonical order of the states is shown inside the node within DFA. If topDown is set to true, the visual representation will be top down. A left to right representation is used otherwise. Returns true if successful or false if an error occurs.

func (DFA) ToPNG 

func (dfa DFA) ToPNG(filePath string, symbolMapping map[int]string, showOrder bool, topDown bool) bool

ToPNG creates and saves a .png image which represents the DFA to the given file path. Please note that GraphViz must be downloaded and installed before hand from https://graphviz.org/download/. The symbolMapping parameter is a map which maps each symbol within the alphabet to a string. This can be set to nil, which will map each symbol with a number starting from 0. If showOrder is set to true, the canonical order of the states is shown inside the node within DFA. If topDown is set to true, the visual representation will be top down. A left to right representation is used otherwise. Returns true if successful or false if an error occurs.

func (DFA) ToSVG 

func (dfa DFA) ToSVG(filePath string, symbolMapping map[int]string, showOrder bool, topDown bool) bool

ToSVG creates and saves a .svg file which represents the DFA to the given file path. Please note that GraphViz must be downloaded and installed before hand from https://graphviz.org/download/. The symbolMapping parameter is a map which maps each symbol within the alphabet to a string. This can be set to nil, which will map each symbol with a number starting from 0. If showOrder is set to true, the canonical order of the states is shown inside the node within DFA. If topDown is set to true, the visual representation will be top down. A left to right representation is used otherwise. Returns true if successful or false if an error occurs.

func (DFA) ToStaminaFile 

func (dfa DFA) ToStaminaFile(filePath string)

ToStaminaFile writes a given DFA to file in Stamina-Format (adl).

func (DFA) ToStatePartition 

func (dfa DFA) ToStatePartition() StatePartition

ToStatePartition converts a DFA to a State Partition.

func (DFA) TransitionsCount 

func (dfa DFA) TransitionsCount() int

TransitionsCount returns the number of transitions within DFA.

func (DFA) TransitionsCountForSymbol 

func (dfa DFA) TransitionsCountForSymbol(symbol int) int

TransitionsCountForSymbol returns the number of transitions for a given symbol within DFA.

func (DFA) UnknownStates 

func (dfa DFA) UnknownStates() []int

UnknownStates returns state IDs of unknown states within DFA.

func (DFA) UnknownStatesCount 

func (dfa DFA) UnknownStatesCount() int

UnknownStatesCount returns the number of unknown states within DFA.

func (DFA) UnreachableStates 

func (dfa DFA) UnreachableStates() []int

UnreachableStates returns the state IDs of unreachable states. Extracted from: P. Linz, An Introduction to Formal Languages and Automata. Jones & Bartlett Publishers, 2011.

type Dataset 

type Dataset []StringInstance

Dataset which is a slice of string instances.

func DatasetFromJSON 

func DatasetFromJSON(filePath string) (Dataset, bool)

DatasetFromJSON returns a dataset read from a JSON file given a file path. The boolean value returned is set to true if Dataset was read successfully.

func GetDatasetFromAbbadingoFile 

func GetDatasetFromAbbadingoFile(fileName string) Dataset

GetDatasetFromAbbadingoFile returns a Dataset from an Abbadingo-Format File.

func GetDatasetFromStaminaFile 

func GetDatasetFromStaminaFile(fileName string) Dataset

GetDatasetFromStaminaFile returns a Dataset from a Stamina-Format File.

func (Dataset) AcceptingStringInstances 

func (dataset Dataset) AcceptingStringInstances() Dataset

AcceptingStringInstances returns the accepting string instances.

func (Dataset) AcceptingStringInstancesCount 

func (dataset Dataset) AcceptingStringInstancesCount() int

AcceptingStringInstancesCount returns the number of accepting string instances within dataset.

func (Dataset) AcceptingStringInstancesRatio 

func (dataset Dataset) AcceptingStringInstancesRatio() float64

AcceptingStringInstancesRatio returns the ratio of accepting string instances to the rejecting string instances within dataset.

func (Dataset) Accuracy 

func (dataset Dataset) Accuracy(dfa DFA) float64

Accuracy returns the DFA's Accuracy with respect to the dataset.

func (Dataset) ConsistentWithDFA 

func (dataset Dataset) ConsistentWithDFA(dfa DFA) bool

ConsistentWithDFA checks whether dataset is consistent with a given DFA.

func (Dataset) ConsistentWithStatePartition 

func (dataset Dataset) ConsistentWithStatePartition(statePartition StatePartition) bool

ConsistentWithStatePartition checks whether dataset is consistent with a given StatePartition.

func (Dataset) Count 

func (dataset Dataset) Count() int

Count returns the number of string instances within dataset.

func (Dataset) GetPTA 

func (dataset Dataset) GetPTA(APTA bool) DFA

GetPTA returns an APTA/PTA (DFA) given a dataset. If APTA is set to true, an APTA is returned.

func (Dataset) RejectingStringInstances 

func (dataset Dataset) RejectingStringInstances() Dataset

RejectingStringInstances returns the rejecting string instances.

func (Dataset) RejectingStringInstancesCount 

func (dataset Dataset) RejectingStringInstancesCount() int

RejectingStringInstancesCount returns the number of accepting string instances within dataset.

func (Dataset) RejectingStringInstancesRatio 

func (dataset Dataset) RejectingStringInstancesRatio() float64

RejectingStringInstancesRatio returns the ratio of rejecting string instances to the accepting string instances within dataset.

func (Dataset) SameAs 

func (dataset Dataset) SameAs(dataset2 Dataset) bool

SameAs checks whether Dataset is the same as the given Dataset. Both datasets are sorted before checking with DeepEqual.

func (Dataset) SortDatasetByLength 

func (dataset Dataset) SortDatasetByLength() Dataset

SortDatasetByLength sorts the given dataset by length and returns it.

func (Dataset) StructurallyComplete 

func (dataset Dataset) StructurallyComplete(dfa DFA) bool

StructurallyComplete checks if Dataset is structurally complete with respect to a DFA.

func (Dataset) SymmetricallyStructurallyComplete 

func (dataset Dataset) SymmetricallyStructurallyComplete(dfa DFA) bool

SymmetricallyStructurallyComplete checks if Dataset is symmetrically structurally complete with respect to a DFA.

func (Dataset) ToAbbadingoFile 

func (dataset Dataset) ToAbbadingoFile(filePath string)

ToAbbadingoFile writes a given Dataset to file in Abbadingo-Format.

func (Dataset) ToJSON 

func (dataset Dataset) ToJSON(filePath string) bool

ToJSON saves the dataset to a JSON file given a file path.

func (Dataset) ToStaminaFile 

func (dataset Dataset) ToStaminaFile(filePath string)

ToStaminaFile writes a given Dataset to file in Stamina-Format.

type MergeData 

type MergeData struct {
	Merges               []StatePairScore // Slice of state pairs and scores of merges done.
	AttemptedMergesCount int              // The number of attempted merges.
	ValidMergesCount     int              // The number of valid attempted merges.
	Duration             time.Duration    // The duration for the search function to finish.
}

MergeData struct to store merge merge data.

func (MergeData) AttemptedMergesPerSecond 

func (mergeData MergeData) AttemptedMergesPerSecond() float64

AttemptedMergesPerSecond returns the number of attempted merges per second. Used for performance evaluation.

func (MergeData) MergesCount 

func (mergeData MergeData) MergesCount() int

MergesCount returns the number of merges done before reaching the final StatePartition.

func (MergeData) ToJSON 

func (mergeData MergeData) ToJSON(filePath string) bool

ToJSON saves the MergeData to a JSON file given a file path.

type ScoringFunction 

type ScoringFunction func(stateID1, stateID2 int, partitionBefore, partitionAfter StatePartition) float64

ScoringFunction takes two stateIDs and two state partitions as input and returns a score as a float.

type State 

type State struct {
	Label       StateLabel // State Label (Rejecting, Accepting, or Unknown).
	Transitions []int      // Transition Table where each element corresponds to a transition for each symbol.
	// contains filtered or unexported fields
}

State struct which represents a State within a DFA.

func (State) AllTransitionsExist 

func (state State) AllTransitionsExist() bool

AllTransitionsExist checks whether all transitions from a given state exist (not -1). In other words, whether the state has a transition for each of the symbols within the alphabet.

func (State) Clone 

func (state State) Clone() State

Clone returns a clone of the State.

func (State) DFA 

func (state State) DFA() *DFA

DFA returns a pointer to the DFA which contains this State.

func (*State) Depth 

func (state *State) Depth() int

Depth returns the state's depth within DFA.

func (State) InDegree 

func (state State) InDegree(stateID int) int

InDegree returns the in degree of the state.

func (State) IsAccepting 

func (state State) IsAccepting() bool

IsAccepting returns true if state label is accepting, otherwise returns false.

func (State) IsLeaf 

func (state State) IsLeaf() bool

IsLeaf checks whether given state is a leaf within DFA. In other words, whether the state has any valid transitions.

func (State) IsRejecting 

func (state State) IsRejecting() bool

IsRejecting returns true if state label is rejecting, otherwise returns false.

func (State) IsUnknown 

func (state State) IsUnknown() bool

IsUnknown returns true if state label is unknown, otherwise returns false.

func (*State) Order 

func (state *State) Order() int

Order returns the state's order within DFA.

func (State) OutDegree 

func (state State) OutDegree() int

OutDegree returns the out degree of the state..

func (State) TransitionExists 

func (state State) TransitionExists(stateID int) bool

TransitionExists checks whether a transition exists from a given state to another state, regardless of the symbol.

func (State) TransitionsCount 

func (state State) TransitionsCount(stateID int) int

TransitionsCount returns the number of transitions to given state ID.

func (State) ValidTransitions 

func (state State) ValidTransitions() []int

ValidTransitions returns all transitions from a given state that are valid (not -1). The symbolIDs of the corresponding valid transitions are returned in a slice of integers.

type StateIDPair 

type StateIDPair struct {
	// contains filtered or unexported fields
}

StateIDPair which represents a pair of states.

type StateLabel 

type StateLabel uint8

StateLabel type as an 8-bit unsigned integer.

type StatePairScore 

type StatePairScore struct {
	State1 int     // StateID for first state.
	State2 int     // StateID for second state.
	Score  float64 // Score of merge for given states.
}

StatePairScore struct to store state pairs and their merge score.

type StatePartition 

type StatePartition struct {
	Blocks               []Block // Slice of blocks.
	BlocksCount          int     // Number of blocks within partition.
	AcceptingBlocksCount int     // Number of accepting blocks within partition.
	RejectingBlocksCount int     // Number of rejecting blocks within partition.
	AlphabetSize         int     // Size of alphabet.
	StartingStateID      int     // The ID of the starting state.

	IsCopy             bool  // Whether state partition is a copy (for reverting merges).
	ChangedBlocks      []int // Slice of changed blocks.
	ChangedBlocksCount int   // Number of changed blocks within partition.
}

StatePartition struct which represents a State Partition.

func NewStatePartition 

func NewStatePartition(referenceDFA DFA) StatePartition

NewStatePartition returns an initialized State Partition.

func StatePartitionFromJSON 

func StatePartitionFromJSON(filePath string) (StatePartition, bool)

StatePartitionFromJSON returns a StatePartition read from a JSON file given a file path. The boolean value returned is set to true if DFA was read successfully.

func (*StatePartition) ChangedBlock 

func (statePartition *StatePartition) ChangedBlock(blockID int)

ChangedBlock updates the required fields to mark block as changed.

func (StatePartition) Clone 

func (statePartition StatePartition) Clone() StatePartition

Clone returns a clone of the state partition.

func (StatePartition) Copy 

func (statePartition StatePartition) Copy() StatePartition

Copy returns a copy of the state partition in 'copy' (undo) mode.

func (*StatePartition) CopyChangesFrom 

func (statePartition *StatePartition) CopyChangesFrom(copiedStatePartition *StatePartition)

CopyChangesFrom copies the changes from one state partition to another and resets the changed values within the copied state partition.

func (*StatePartition) DepthOfBlocks 

func (statePartition *StatePartition) DepthOfBlocks() map[int]int

DepthOfBlocks returns the depth of each block.

func (*StatePartition) Find 

func (statePartition *StatePartition) Find(stateID int) int

Find traverses each root element while compressing the levels to find the root element of the stateID.

func (*StatePartition) MergeStates 

func (statePartition *StatePartition) MergeStates(state1 int, state2 int) bool

MergeStates recursively merges states to merge state1 and state2. Returns false if merge results in a non-deterministic automaton. Returns true if merge was successful.

func (StatePartition) NumberOfLabelledBlocks 

func (statePartition StatePartition) NumberOfLabelledBlocks() int

NumberOfLabelledBlocks returns the number of labelled blocks (states) within state partition.

func (*StatePartition) OrderOfBlocks 

func (statePartition *StatePartition) OrderOfBlocks() map[int]int

OrderOfBlocks returns the order of each block.

func (*StatePartition) OrderedBlocks 

func (statePartition *StatePartition) OrderedBlocks() []int

OrderedBlocks returns the IDs of root blocks in order as a slice of integers.

func (StatePartition) ReturnSet 

func (statePartition StatePartition) ReturnSet(blockID int) []int

ReturnSet returns the state IDs within given block.

func (*StatePartition) RollbackChangesFrom 

func (statePartition *StatePartition) RollbackChangesFrom(originalStatePartition StatePartition)

RollbackChangesFrom reverts any changes made within state partition given the original state partition.

func (StatePartition) RootBlocks 

func (statePartition StatePartition) RootBlocks() []int

RootBlocks returns the IDs of root blocks as a slice of integers.

func (*StatePartition) StartingBlock 

func (statePartition *StatePartition) StartingBlock() int

StartingBlock returns the ID of the block which contains the starting state.

func (StatePartition) ToDOT 

func (statePartition StatePartition) ToDOT(filePath string, symbolMapping map[int]string, showOrder bool, topDown bool)

ToDOT creates a .dot file using the DOT language. This DOT file contains a representation for the given StatePartition which can then be used to generate a visual representation of the DFA represented by the State Partition. The symbolMapping parameter is a map which maps each symbol within the alphabet to a string. This can be set to nil, which will map each symbol with a number starting from 0. If showOrder is set to true, the canonical order of the states is shown inside the node within partition. If topDown is set to true, the visual representation will be top down. A left to right representation is used otherwise. This function is also called from all of the functions below.

func (StatePartition) ToJPG 

func (statePartition StatePartition) ToJPG(filePath string, symbolMapping map[int]string, showOrder bool, topDown bool) bool

ToJPG creates and saves a .jpg image which represents the state partition to the given file path. Please note that GraphViz must be downloaded and installed before hand from https://graphviz.org/download/. The symbolMapping parameter is a map which maps each symbol within the alphabet to a string. This can be set to nil, which will map each symbol with a number starting from 0. If showOrder is set to true, the canonical order of the states is shown inside the node within partition. If topDown is set to true, the visual representation will be top down. A left to right representation is used otherwise. Returns true if successful or false if an error occurs.

func (StatePartition) ToJSON 

func (statePartition StatePartition) ToJSON(filePath string) bool

ToJSON saves the StatePartition to a JSON file given a file path.

func (StatePartition) ToPDF 

func (statePartition StatePartition) ToPDF(filePath string, symbolMapping map[int]string, showOrder bool, topDown bool) bool

ToPDF creates and saves a .pdf file which represents the state partition to the given file path. Please note that GraphViz must be downloaded and installed before hand from https://graphviz.org/download/. The symbolMapping parameter is a map which maps each symbol within the alphabet to a string. This can be set to nil, which will map each symbol with a number starting from 0. If showOrder is set to true, the canonical order of the states is shown inside the node within partition. If topDown is set to true, the visual representation will be top down. A left to right representation is used otherwise. Returns true if successful or false if an error occurs.

func (StatePartition) ToPNG 

func (statePartition StatePartition) ToPNG(filePath string, symbolMapping map[int]string, showOrder bool, topDown bool) bool

ToPNG creates and saves a .png image which represents the state partition to the given file path. Please note that GraphViz must be downloaded and installed before hand from https://graphviz.org/download/. The symbolMapping parameter is a map which maps each symbol within the alphabet to a string. This can be set to nil, which will map each symbol with a number starting from 0. If showOrder is set to true, the canonical order of the states is shown inside the node within partition. If topDown is set to true, the visual representation will be top down. A left to right representation is used otherwise. Returns true if successful or false if an error occurs.

func (*StatePartition) ToQuotientDFA 

func (statePartition *StatePartition) ToQuotientDFA() DFA

ToQuotientDFA converts a State Partition to a quotient DFA and returns it.

func (*StatePartition) ToQuotientDFAWithMapping 

func (statePartition *StatePartition) ToQuotientDFAWithMapping() (DFA, map[int]int)

ToQuotientDFAWithMapping converts a State Partition to a quotient DFA and returns it. This function also returns the state partition's blocks to state mapping.

func (StatePartition) ToSVG 

func (statePartition StatePartition) ToSVG(filePath string, symbolMapping map[int]string, showOrder bool, topDown bool) bool

ToSVG creates and saves a .svg file which represents the state partition to the given file path. Please note that GraphViz must be downloaded and installed before hand from https://graphviz.org/download/. The symbolMapping parameter is a map which maps each symbol within the alphabet to a string. This can be set to nil, which will map each symbol with a number starting from 0. If showOrder is set to true, the canonical order of the states is shown inside the node within partition. If topDown is set to true, the visual representation will be top down. A left to right representation is used otherwise. Returns true if successful or false if an error occurs.

func (*StatePartition) Union 

func (statePartition *StatePartition) Union(blockID1 int, blockID2 int)

Union connects two blocks by comparing their respective size (score) values to keep the tree flat.

func (*StatePartition) WithinSameBlock 

func (statePartition *StatePartition) WithinSameBlock(stateID1 int, stateID2 int) bool

WithinSameBlock checks whether two states are within the same block.

type StringInstance 

type StringInstance struct {
	Value     []int // Slice of integers which represents the symbol values.
	Accepting bool  // Accepting label flag for StringInstance.
}

StringInstance struct which represents a string instance within a dataset.

func BinaryStringToStringInstance 

func BinaryStringToStringInstance(dfa DFA, binaryString string) StringInstance

BinaryStringToStringInstance returns a StringInstances from a binary string.

func NewStringInstanceFromAbbadingoFile 

func NewStringInstanceFromAbbadingoFile(text string, delimiter string) StringInstance

NewStringInstanceFromAbbadingoFile returns a StringInstance from a line within an Abbadingo-Format File.

func NewStringInstanceFromStaminaFile 

func NewStringInstanceFromStaminaFile(text string, delimiter string) StringInstance

NewStringInstanceFromStaminaFile returns a StringInstance from a line within a Stamina-Format File.

func (StringInstance) ConsistentWithDFA 

func (stringInstance StringInstance) ConsistentWithDFA(dfa DFA) bool

ConsistentWithDFA returns whether a string instance is consistent within a given DFA.

func (StringInstance) ConsistentWithStatePartition 

func (stringInstance StringInstance) ConsistentWithStatePartition(statePartition StatePartition) bool

ConsistentWithStatePartition returns whether a string instance is consistent within a given StatePartition.

func (StringInstance) Length 

func (stringInstance StringInstance) Length() int

Length returns the length of the string.

func (StringInstance) ParseToState 

func (stringInstance StringInstance) ParseToState(dfa DFA) (bool, int)

ParseToState returns the State ID of a given string instance within a given DFA. A boolean is also returned which returns false if string instance does not correspond to any state within DFA.

func (StringInstance) ParseToStateLabel 

func (stringInstance StringInstance) ParseToStateLabel(dfa DFA) StateLabel

ParseToStateLabel returns the State Label of a given string instance within a given DFA. If state does not exist, REJECTING is returned.

func (StringInstance) WithinDataset 

func (stringInstance StringInstance) WithinDataset(dataset Dataset) bool

WithinDataset checks whether a StringInstance is within given Dataset.

type TeamOfAutomata 

type TeamOfAutomata struct {
	Team      []DFA
	MergeData MergeData
}

TeamOfAutomata represents a team of automata within the AutomataTeams algorithm.

func AutomataTeams 

func AutomataTeams(APTA DFA, teamSize int) TeamOfAutomata

AutomataTeams creates a team of automata of size teamSize. This creates a TeamOfAutomata instance which can then be used to classify testing examples.

func AutomataTeamsFromDataset 

func AutomataTeamsFromDataset(dataset Dataset, teamSize int) TeamOfAutomata

AutomataTeamsFromDataset creates a team of automata of size teamSize. This creates a TeamOfAutomata instance which can then be used to classify testing examples. It takes a dataset as an argument which is used to generate an APTA.

func (TeamOfAutomata) Accuracy 

func (teamOfAutomata TeamOfAutomata) Accuracy(dataset Dataset, teamOfAutomataClassifierFunction TeamOfAutomataClassifierFunction) float64

Accuracy returns the TeamOfAutomata's Accuracy with respect to a dataset.

func (TeamOfAutomata) AverageNumberOfStates 

func (teamOfAutomata TeamOfAutomata) AverageNumberOfStates() int

AverageNumberOfStates returns the average number of states of DFAs within team.

func (TeamOfAutomata) BetterHalfWeightedVoteAccuracy 

func (teamOfAutomata TeamOfAutomata) BetterHalfWeightedVoteAccuracy(dataset Dataset) float64

BetterHalfWeightedVoteAccuracy returns the TeamOfAutomata's Accuracy with respect to a dataset using the better half weighted vote scoring heuristic.

func (TeamOfAutomata) FairVoteAccuracy 

func (teamOfAutomata TeamOfAutomata) FairVoteAccuracy(dataset Dataset) float64

FairVoteAccuracy returns the TeamOfAutomata's Accuracy with respect to a dataset using the fair vote scoring heuristic.

func (TeamOfAutomata) WeightedVoteAccuracy 

func (teamOfAutomata TeamOfAutomata) WeightedVoteAccuracy(dataset Dataset) float64

WeightedVoteAccuracy returns the TeamOfAutomata's Accuracy with respect to a dataset using the weighted vote scoring heuristic.

type TeamOfAutomataClassifierFunction 

type TeamOfAutomataClassifierFunction func(stringInstance StringInstance) StateLabel

TeamOfAutomataClassifierFunction takes a string instance as input and returns a state label. An example of how this function type should be used can be seen in BetterHalfWeightedVoteAccuracy.

type Transition 

type Transition struct {
	// contains filtered or unexported fields
}

Transition struct which represents a transition. Used in SymmetricallyStructurallyComplete and StructurallyComplete functions.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.