edu.stanford.nlp.fsm
Class FastExactAutomatonMinimizer

java.lang.Object
  edu.stanford.nlp.fsm.FastExactAutomatonMinimizer

All Implemented Interfaces:

AutomatonMinimizer

public class FastExactAutomatonMinimizer
extends Object
implements AutomatonMinimizer

Minimization in n log n a la Hopcroft.

Author:

Dan Klein (klein@cs.stanford.edu)

Constructor Summary

FastExactAutomatonMinimizer()

Method Summary

protected void	addSplit(edu.stanford.nlp.fsm.FastExactAutomatonMinimizer.Split split)
protected void	addSplits(edu.stanford.nlp.fsm.FastExactAutomatonMinimizer.Block block)
protected TransducerGraph	buildMinimizedFA()
protected Collection	difference(Collection block, Collection members)
protected edu.stanford.nlp.fsm.FastExactAutomatonMinimizer.Block	getBlock(Object o)
protected Collection	getInverseArcs(Object member)
protected Collection	getInverseArcs(Object member, Object symbol)
protected Collection	getInverseImages(edu.stanford.nlp.fsm.FastExactAutomatonMinimizer.Split split)
protected edu.stanford.nlp.fsm.FastExactAutomatonMinimizer.Split	getSplit()
protected Collection	getSymbols()
protected TransducerGraph	getUnminimizedFA()
protected boolean	hasSplit()
static void	main(String[] args)
protected void	makeBlock(Collection members)
protected void	makeInitialBlocks()
protected void	minimize()
TransducerGraph	minimizeFA(TransducerGraph unminimizedFA)
protected Object	projectNode(Object node)
protected void	removeAll(Collection block, Collection members)
protected Map	sortIntoBlocks(Collection nodes)

Methods inherited from class java.lang.Object

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

Constructor Detail

FastExactAutomatonMinimizer

public FastExactAutomatonMinimizer()

Method Detail

getUnminimizedFA

protected TransducerGraph getUnminimizedFA()

getSymbols

protected Collection getSymbols()

minimizeFA

public TransducerGraph minimizeFA(TransducerGraph unminimizedFA)

Specified by:

minimizeFA in interface AutomatonMinimizer

buildMinimizedFA

protected TransducerGraph buildMinimizedFA()

projectNode

protected Object projectNode(Object node)

hasSplit

protected boolean hasSplit()

getSplit

protected edu.stanford.nlp.fsm.FastExactAutomatonMinimizer.Split getSplit()

addSplit

protected void addSplit(edu.stanford.nlp.fsm.FastExactAutomatonMinimizer.Split split)

sortIntoBlocks

protected Map sortIntoBlocks(Collection nodes)

makeBlock

protected void makeBlock(Collection members)

addSplits

protected void addSplits(edu.stanford.nlp.fsm.FastExactAutomatonMinimizer.Block block)

removeAll

protected void removeAll(Collection block,
                         Collection members)

difference

protected Collection difference(Collection block,
                                Collection members)

getBlock

protected edu.stanford.nlp.fsm.FastExactAutomatonMinimizer.Block getBlock(Object o)

getInverseImages

protected Collection getInverseImages(edu.stanford.nlp.fsm.FastExactAutomatonMinimizer.Split split)

getInverseArcs

protected Collection getInverseArcs(Object member,
                                    Object symbol)

getInverseArcs

protected Collection getInverseArcs(Object member)

makeInitialBlocks

protected void makeInitialBlocks()

minimize

protected void minimize()

main

public static void main(String[] args)