de.ls5.jlearn.util
Class AutomatonMinimizer

java.lang.Object
  de.ls5.jlearn.util.AutomatonMinimizer

public class AutomatonMinimizer
extends Object

implements a minimizing algorithm resembling Marie-pierre Béal and Maxime Crochemore: "Minimizing incomplete automata", 2008.

Author:

fh

Constructor Summary

AutomatonMinimizer()

Method Summary

static Automaton

minimize(Automaton in) minimize automaton.

Methods inherited from class java.lang.Object

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

Constructor Detail

AutomatonMinimizer

public AutomatonMinimizer()

Method Detail

minimize

public static Automaton minimize(Automaton in)

minimize automaton. Following the approach from Marie-pierre Béal and Maxime Crochemore: "Minimizing incomplete automata", 2008. also incomplete automata can be minimized. The implemented version automatically supports FSA as well as Mealy machines. The original algorithms minimizes automata in time in O(m log(n)), where m is the number of transitions and n the number of states. The version implemented here deviates from the original wrt. the weak sort implementation, which may break the performance characteristics.

Returns:

minimized automaton