header
MinimizeDFA

Tag:
Edit edit   Starstar

Program Information

Name: MinimizeDFA
Domain: Algorithm
Functionality: Transforming a given deterministic finite automaton (DFA) into an equivalent DFA that has minimum number of states based on Hopcroft’s algorithm.
Input: M=(Q,E,S,q,F) Q:A finite set of states(Type: Set) E:The input alphabet(Type: Alphabet) S:The transition function $Q \times E \longrightarrow Q$(Type: Function) q:The initial state. F:The set of final states which is the subset of Q(Type: Set)
Output: $G=(Q_g,E,S_g,q,F_g)$

Reference

 How Effectively Does Metamorphic Testing Alleviate the Oracle Problem? http://dx.doi.org/10.1109/TSE.2013.46 

MR Information

MR1------

Description:
Property:
Source input: $M_s$
Source output: $G_s$
Follow-up input: $M_f$
Follow-up output: $G_f$
Input relation: $M_f = G_s$
Output relation: $G_f = G_s$
Pattern:

MR2------

Description:
Property:
Source input: $M_s$
Source output: $G_s$
Follow-up input: $M_f$
Follow-up output: $G_f$
Input relation: $M_f$ = Adding a new state s to $M_s$,where s is duplicate to one state in $M_s$.
Output relation: $G_f = G_s$
Pattern:

MR3------

Description:
Property:
Source input: $M_s$
Source output: $G_s$
Follow-up input: $M_f$
Follow-up output: $G_f$
Input relation: $M_f$ = Adding a new state s to $M_s$,where for a state $s_i \in Q$,$\forall$ input $e_j$,if $S(s_i,e_j)$ is not equivalent to $s_i$, $S(s,e_j) = S(s_i,e_j)$; otherwise, $S(s,e_j) = s$.
Output relation: $G_f = G_s$
Pattern:

MR4------

Description:
Property:
Source input: $M_s$
Source output: $G_s$
Follow-up input: $M_f$
Follow-up output: $G_f$
Input relation: $M_f$ = Adding a new state s to $M_s$,where for a state $s_i \in Q$,$\forall$ input $e_j$,if $S(s_i,e_j)$ is not equivalent to $s_i$, $S(s,e_j) = S(s_i,e_j)$; otherwise, $S(s,e_j) = S(s_i,e_j)$ and then set $S(s_i,e_j) = s$.
Output relation: $G_f = G_s$
Pattern:

MR5------

Description:
Property:
Source input: $M_s$
Source output: $G_s$
Follow-up input: $M_f$
Follow-up output: $G_f$
Input relation: $M_f$ = Adding a new state s to $M_s$,where for a state $s_i \in Q$, $\forall$ input $e_j$,if $S(s_i,e_j)$ is not equivalent to $s_i$, $S(s,e_j) = S(s_i,e_j)$; otherwise, $S(s,e_j)$ is equal to an equivalent state of $s_$i.
Output relation: $G_f = G_s$
Pattern:

MR6------

Description:
Property:
Source input: $M_s$
Source output: $G_s$
Follow-up input: $M_f$
Follow-up output: $G_f$
Input relation: $M_f$ = Adding a new state s and a new input e to $M_s$,where $\forall$ state $s_i$ in a whole set of equivalent states, $S(s_i,e) = s$.
Output relation: $Q^f_g = Q^s_g \cup \{s\}$ $E_f = E_s$ $S^f_g = S^s_g \setminus \{transition functions related to the new input e\}$ $q_f = q_s$ $F^f_g = F^s_g$
Pattern:

MR7------

Description:
Property:
Source input: $M_s$
Source output: $G_s$
Follow-up input: $M_f$
Follow-up output: $G_f$
Input relation: $M_f$ = Adding a new state s to $M_s$,where \forall state $s_i$ in a whole set of equivalent states, for one input $e_j$,$S(s_i,e_j) = s$.
Output relation: $s \in Q^f_g$ The set of equivalent states will remain unchanged.
Pattern:

MR8------

Description:
Property:
Source input: $M_s$
Source output: $G_s$
Follow-up input: $M_f$
Follow-up output: $G_f$
Input relation: $M_f$ = Adding a new state s to $M_s$, where s does not have any incoming or outgoing transition with the existing states.
Output relation: $Q^f_g=Q^s_g \cup \{s\}$ $E_f=E_s$ $S^f_g=S^s_g$ $q_f=q_s$ $F^f_g=F^s_g$
Pattern:

MR9------

Description:
Property:
Source input: $M_s$
Source output: $G_s$
Follow-up input: $M_f$
Follow-up output: $G_f$
Input relation: $M_f$ = In $M_s$, for a state $s_i$ and an input $e_j$,if $S(s_i,e_j)$ is equivalent/non-equivalent to $s_i$, change the transition such that $S(s_i,e_j)$ is non-equivalent/equivalent to $s_i$.
Output relation: $s_i$ will become non-equivalent to its previous equivalent states.
Pattern:

MR10------

Description:
Property:
Source input: $M_s$
Source output: $G_s$
Follow-up input: $M_f$
Follow-up output: $G_f$
Input relation: $M_f$ = In $M_s$, for a state $s_i$ that has at least two incoming transitions from other states, add a new state s, where s has the same outgoing transitions as $s_i$, but some previous incoming transitions will be transferred to s, while other incoming transitions remain unchanged.
Output relation: $G_f = G_s$
Pattern:

MR11------

Description:
Property:
Source input: $M_s$
Source output: $G_s$
Follow-up input: $M_f$
Follow-up output: $G_f$
Input relation: $M_f$ = Adding a new state s to $M_s$, where for a state $s_i \in Q$, \forall input $e_j$, if $S(s_i,e_j)$ is not equivalent to $s_i$,$S(s,e_j)$ = $S(s_i,e_j)$;otherwise, $S(s,e_j) = s_i$.
Output relation: $G_f = G_s$
Pattern:

MR12------

Description:
Property:
Source input: $M_s$
Source output: $G_s$
Follow-up input: $M_f$
Follow-up output: $G_f$
Input relation: $M_f$ = Adding a new state s to $M_s$, where for a state $s_i \in Q$, \forall input $e_j$, if $S(s_i,e_j)$ is equal to an equivalent state of $S(s_i,e_j)$;otherwise, $S(s,e_j) = s_i$.
Output relation: $G_f = G_s$
Pattern:

MR13------

Description:
Property:
Source input: $M_s$
Source output: $G_s$
Follow-up input: $M_f$
Follow-up output: $G_f$
Input relation: $M_f$ = Swapping two equivalent states $s_i$ and $s_j$ of $M_s$.
Output relation: $G_f = G_s$
Pattern:

MR14------

Description:
Property:
Source input: $M_s$
Source output: $G_s$
Follow-up input: $M_f$
Follow-up output: $G_f$
Input relation: $M_f$ = Deleting an outgoing transition of a state $s_i$ in $M_s$.
Output relation: $s_i$ will become non-equivalent to its previous equivalent states.
Pattern:

MR15------

Description:
Property:
Source input: $M_s$
Source output: $G_s$
Follow-up input: $M_f$
Follow-up output: $G_f$
Input relation: $M_f$ = Changing the order of inputs in $M_s$.
Output relation: $G_f$ is equal to the minimal DFA that is constructed by changing the order of inputs in $G_s$ in the same way.
Pattern:

MR16------

Description:
Property:
Source input: $M_s$
Source output: $G_s$
Follow-up input: $M_f$
Follow-up output: $G_f$
Input relation: $M_f$ = Adding a new state s and a new input e to $M_s$, where among a whole set of equivalent states, for one state $s_i$, $S(s_i,e) = s$, while for all other states $s_j$,$S(s_j,e) = S(s_j,e_{1})$.
Output relation: $s_i$ will become non-equivalent to its previous equivalent states. The new state will appear in $G_f$.
Pattern:
Insert title here