cz.cuni.mff.ksi.jinfer.twostep.processing.automatonmergingstate.conditiontesting.khcontext
Class KHContext<T>

java.lang.Object
  cz.cuni.mff.ksi.jinfer.twostep.processing.automatonmergingstate.conditiontesting.khcontext.KHContext<T>

All Implemented Interfaces:

MergeConditionTester<T>

public class KHContext<T>
extends Object
implements MergeConditionTester<T>

k,h-context equivalence criterion implementation. It first finds all contexts of two states, then compares each pair. Returns list of alternative merge lists of pairs. Not using k-grams algorithm.

Constructor Summary

KHContext(int k, int h)
Setting k,h.

Method Summary

List<List<List<State<T>>>>

getMergableStates(Automaton<T> automaton) If states are equivalent given a condition, should return a list of list of list of states.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

KHContext

public KHContext(int k,
                 int h)

Setting k,h. It has to be k >= h, or exception thrown (cannot merge more than k states on path, when only k of them were examined).

Parameters:

k -

h -

Method Detail

getMergableStates

public List<List<List<State<T>>>> getMergableStates(Automaton<T> automaton)
                                             throws InterruptedException

Description copied from interface: MergeConditionTester

If states are equivalent given a condition, should return a list of list of list of states.

First list: represents merge alternatives - that is, calling procedure can decide which alternative from the first list it will implement and merge states specified in

Second list: which contains merge sequences (lists). Merge sequence is list of states that are to be merged into one state. All merge sequences in this list have to be processed and appropriate states merged.

For example 2,1-context tester will find states A and B have same context and have to be merged. It creates a List{A, B} - that is merge sequence (all states in sequence will be merged into one of them). But as 2,1-context method requires, also one preceeding states in context have to be merged, say states C and D. So it will create List{C, D}, merge sequence. Then, to enforce the states are merged in order C+D, then A+B, a second list:

List{List{C,D}, List{A,B}} is created. That is a complete merge alternative. If tester founds another alternative, with different contexts, it creates another alternative, say List{List{E,F}, List{A,B}}. And returns List{alternatives}.

Each merge sequence will be merged so, that second state is removed and first state remains in automaton.

Automaton can withstand request for merging a state, that has been already removed in previous merge (thorough whole automata lifetime).

For example this alternative is legal: List>: {{1, 2}, {2, 3}, {3, 4}} Will merge state 2 into state 1. Then state 3 to state 2 - state 2 is already removed, but automaton is clever and knows what to do, so it merges state 3 to state 1. Then it merges state 4 to state 1 too.

When called later, it is legal to return: List>: [57, 2] State 2 doesn't exist anymore and automaton is clever enough to merge state 57 into state 1.

Specified by:

getMergableStates in interface MergeConditionTester<T>

Parameters:

automaton - whole automaton on which we work

Returns:

list of alternatives as describe above

Throws:

InterruptedException