KripkeStructures (Averest)

KripkeStructures Module

Namespace: TeachingTools
Assembly: TeachingToolsLib.dll

This module implements functions for checking (bi)simulation relations of labeled transition systems (Kripke structures). It also computes quotients and products of Kripke structures.

Types

Type	Description
KripkeStructure	This denotes the type of a Kripke structure. States are unsigned integers, and the labels are then given by a simple array of sets of strings, and the transition relation is a list of pairs of states (integers). Finally,the initial states are given as a set of states.

Functions and values

Function or value	Description
`BisimulationQuotientsTool qscoll` Full Usage: `BisimulationQuotientsTool qscoll` Parameters: qscoll : `NameValueCollection`	This function is meant to be called from cgi; it expects two Kripke structures given as name value pairs in the qscoll argument where the names are Kripke1 and Kripke2. The values are parsed by function ParseKripkeStructure, and then the various simulation and bisimulation relations are computed in addition to the quotient structures to minimize the given Kripke structures. qscoll : `NameValueCollection`
`CheckBisimulation ostr prefix1 K1 prefix2 K2` Full Usage: `CheckBisimulation ostr prefix1 K1 prefix2 K2` Parameters: ostr : `TextWriter` prefix1 : `string` K1 : `KripkeStructure` prefix2 : `string` K2 : `KripkeStructure` Returns: `bool * (int * int) list`	check whether K1 and K2 are bisimilar ostr : `TextWriter` prefix1 : `string` K1 : `KripkeStructure` prefix2 : `string` K2 : `KripkeStructure` Returns: `bool * (int * int) list`
`CheckSimulation ostr prefix1 K1 prefix2 K2` Full Usage: `CheckSimulation ostr prefix1 K1 prefix2 K2` Parameters: ostr : `TextWriter` prefix1 : `string` K1 : `KripkeStructure` prefix2 : `string` K2 : `KripkeStructure` Returns: `bool * (int * int) list`	check whether K2 simulates K1 ostr : `TextWriter` prefix1 : `string` K1 : `KripkeStructure` prefix2 : `string` K2 : `KripkeStructure` Returns: `bool * (int * int) list`
`CheckUniqueLabels k` Full Usage: `CheckUniqueLabels k` Parameters: k : `KripkeStructure` Returns: `bool`	Check whether each state has a unique label (this is required for making a symbolic representation of the Kripke structure). k : `KripkeStructure` Returns: `bool`
`ComputeProduct k1 k2` Full Usage: `ComputeProduct k1 k2` Parameters: k1 : `KripkeStructure` k2 : `KripkeStructure` Returns: `KripkeStructure`	compute a product structure of given Kripke structures k1 : `KripkeStructure` k2 : `KripkeStructure` Returns: `KripkeStructure`
`ComputeQuotient k sigma` Full Usage: `ComputeQuotient k sigma` Parameters: k : `KripkeStructure` sigma : `(int * int) list` Returns: `KripkeStructure`	compute a quotient structure by a given equivalence relation; the states are those states of an equivalence class with minimal index k : `KripkeStructure` sigma : `(int * int) list` Returns: `KripkeStructure`
`Kripke2Dot ostr statePrefix k` Full Usage: `Kripke2Dot ostr statePrefix k` Parameters: ostr : `TextWriter` statePrefix : `string` k : `KripkeStructure`	write Kripke structure to a dot file ostr : `TextWriter` statePrefix : `string` k : `KripkeStructure`
`MkInitialRel k1 k2` Full Usage: `MkInitialRel k1 k2` Parameters: k1 : `KripkeStructure` k2 : `KripkeStructure` Returns: `(int * int) list`	construct all pairs of states of the two structures having the same labels k1 : `KripkeStructure` k2 : `KripkeStructure` Returns: `(int * int) list`
`ParseKripkeStructure s` Full Usage: `ParseKripkeStructure s` Parameters: s : `string` Returns: `KripkeStructure`	parsing a Kripke structure from a string; the syntax is explained by the following example: vars a,b,c,d; init 0,1; labels 0:a,b; 1:b; 2:b,c; 3:c; 4:d; 5:c; transitions 0->1; 0->2; 1->3; 1->4; 2->5; 3->3; 4->4; 5->5; s : `string` Returns: `KripkeStructure`
`StateSet2String statePrefix s` Full Usage: `StateSet2String statePrefix s` Parameters: statePrefix : `string` s : `Set<int>` Returns: `string`	statePrefix : `string` s : `Set<int>` Returns: `string`
`mkSymbolicRepresentation k` Full Usage: `mkSymbolicRepresentation k` Parameters: k : `KripkeStructure` Returns: `string`	generate a symbolic description of the Kripke structure in DNF k : `KripkeStructure` Returns: `string`
`printSimDiagrams ostr prefix1 k1 prefix2 k2` Full Usage: `printSimDiagrams ostr prefix1 k1 prefix2 k2` Parameters: ostr : `TextWriter` prefix1 : `string` k1 : `KripkeStructure` prefix2 : `string` k2 : `KripkeStructure`	prints the diagrams for iterating the simulation relations ostr : `TextWriter` prefix1 : `string` k1 : `KripkeStructure` prefix2 : `string` k2 : `KripkeStructure`