de.up.ling.irtg.automata

Class IntersectionAutomaton<LeftState,RightState>

java.lang.Object

de.up.ling.irtg.automata.TreeAutomaton<Pair<LeftState,RightState>>

de.up.ling.irtg.automata.IntersectionAutomaton<LeftState,RightState>

Type Parameters:

LeftState -

RightState -

All Implemented Interfaces:

Intersectable<Pair<LeftState,RightState>>, Serializable

Direct Known Subclasses:

BestFirstIntersectionAutomaton

public class IntersectionAutomaton<LeftState,RightState>
extends TreeAutomaton<Pair<LeftState,RightState>>

This class is used to represent the intersection of two tree automata. The intersection is computed bottom up.

Author:

koller

See Also:

Serialized Form

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static interface	IntersectionAutomaton.StateDiscoveryListener Defines an interface which accepts newly discovered states during the intersection construction.

Nested classes/interfaces inherited from class de.up.ling.irtg.automata.TreeAutomaton

TreeAutomaton.BottomUpStateVisitor

Field Summary

Fields inherited from class de.up.ling.irtg.automata.TreeAutomaton

D, DEBUG_STORE

Constructor Summary

Constructors

Constructor and Description
IntersectionAutomaton(TreeAutomaton<LeftState> left, TreeAutomaton<RightState> right) Crates a new instance which represents the intersection of the two given automata.

Method Summary

Modifier and Type	Method and Description
IntSet	getFinalStates() Returns the IDs of the final states of the automaton.
int	getLeftState(int outputState) Returns the state in the left automaton for this outputState.
int	getRightState(int outputState) Returns the state in the right automaton for this outputState.
Iterable<Rule>	getRulesBottomUp(int label, int[] childStates) Finds automaton rules bottom-up for a given list of child states and a given parent label.
Iterable<Rule>	getRulesTopDown(int label, int parentState) Finds automaton rules top-down for a given parent state and label.
static IntersectionAutomaton	intersectBottomUpNaive(TreeAutomaton lhs, TreeAutomaton rhs) Helper method which creates an intersection automaton and makes all rules explicit with the default algorithm.
static IntersectionAutomaton	intersectTopDownBottomUpCKY(TreeAutomaton lhs, TreeAutomaton rhs) Helper method which creates an intersection automaton and makes all rules explicit with the CKY algorithm.
boolean	isBottomUpDeterministic() Determines whether the automaton is deterministic if read as a bottom-up automaton.
void	makeAllRulesExplicit() Computes all rules in this automaton and stores them in the cache.
void	makeAllRulesExplicitCKY() This method constructs all transitions in the automaton in a CKY style algorithm.
void	makeAllRulesExplicitCKYOld() This method constructs all transitions in the automaton in a CKY style algorithm, there is a newer version that is preferred.
void	makeAllRulesExplicitEarley() This implements an interesection algorithm in the style of the early algorithm, which predicts possible transition based on the first input automaton and then finds matching rules based on the second input automaton.
void	setStateDiscoveryListener(IntersectionAutomaton.StateDiscoveryListener listener) The listener will be informed whenever a new state is visited for the first time.

Methods inherited from class de.up.ling.irtg.automata.TreeAutomaton

accepts, acceptsRaw, analyze, asConcreteTreeAutomaton, asConcreteTreeAutomatonBottomUp, asConcreteTreeAutomatonWithStringStates, countTrees, createRule, createRule, createRule, createRule, createRule, createRule, determinize, determinize, dumpToFile, equals, evaluateInSemiring, evaluateInSemiring, evaluateInSemiringTopDown, foreachRuleBottomUpForSets, foreachRuleTopDown, foreachStateInBottomUpOrder, getAllLabels, getAllRulesTopDown, getAllStates, getIdForState, getLabelsTopDown, getNumberOfRules, getNumberOfSeenStates, getRandomRuleTree, getRandomRuleTreeFromInside, getRandomTree, getRandomTreeFromInside, getReachableStates, getRulesBottomUp, getRulesBottomUp, getRuleSet, getRulesForRhsState, getRulesTopDown, getRuleTree, getSignature, getStateForId, getStateInterner, getStatesInBottomUpOrder, getStoredConstantsForID, getWeight, getWeightRaw, hasRuleWithPrefix, hasStoredConstants, homomorphism, inside, intersect, intersect, intersectBottomUp, intersectCondensed, intersectCondensed, intersectCondensed, intersectCondensedBottomUp, intersectCondensedBottomUp, intersectEarley, intersectViterbi, intersectViterbi, inverseCondensedHomomorphism, inverseHomomorphism, isCyclic, isEmpty, isStoring, language, languageIterable, languageIterator, languageIteratorRaw, languageRaw, newSiblingFinder, normalizeRuleWeights, outside, processAllRulesBottomUp, processAllRulesTopDown, reduceTopDown, run, run, runRaw, setRulePrintingFilter, setSkipFail, setStoring, sortedLanguageIterator, supportsBottomUpQueries, supportsTopDownQueries, toString, toStringBottomUp, useSiblingFinder, viterbi, viterbiRaw, write

Methods inherited from class java.lang.Object

getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

IntersectionAutomaton

public IntersectionAutomaton(TreeAutomaton<LeftState> left,
                             TreeAutomaton<RightState> right)

Crates a new instance which represents the intersection of the two given automata.

Parameters:

left -

right -

Method Detail

setStateDiscoveryListener

public void setStateDiscoveryListener(IntersectionAutomaton.StateDiscoveryListener listener)

The listener will be informed whenever a new state is visited for the first time.

Parameters:

listener -

getLeftState

public int getLeftState(int outputState)

Returns the state in the left automaton for this outputState. The outputState is the int-ID of some state in the intersection automaton. It represents a pair (p,q) of a state p in the left automaton and a state q in the right automaton. This method returns the int-ID of p.

Parameters:

outputState -

Returns:

getRightState

public int getRightState(int outputState)

Returns the state in the right automaton for this outputState. The outputState is the int-ID of some state in the intersection automaton. It represents a pair (p,q) of a state p in the left automaton and a state q in the right automaton. This method returns the int-ID of q.

Parameters:

outputState -

Returns:

isBottomUpDeterministic

public boolean isBottomUpDeterministic()

Description copied from class: TreeAutomaton

Determines whether the automaton is deterministic if read as a bottom-up automaton.

Specified by:

isBottomUpDeterministic in class TreeAutomaton<Pair<LeftState,RightState>>

Returns:

makeAllRulesExplicitCKY

public void makeAllRulesExplicitCKY()

This method constructs all transitions in the automaton in a CKY style algorithm. This attempts to combine pairs of states that have been found bottom up into new rules.

makeAllRulesExplicitCKYOld

public void makeAllRulesExplicitCKYOld()

This method constructs all transitions in the automaton in a CKY style algorithm, there is a newer version that is preferred. This attempts to combine pairs of states that have been found bottom up into new rules.

makeAllRulesExplicit

public void makeAllRulesExplicit()

Description copied from class: TreeAutomaton

Computes all rules in this automaton and stores them in the cache. This only makes a difference for lazy automata, in which rules are only computed by need. After calling this function, it is guaranteed that all rules are in the cache.

Overrides:

makeAllRulesExplicit in class TreeAutomaton<Pair<LeftState,RightState>>

getFinalStates

public IntSet getFinalStates()

Description copied from class: TreeAutomaton

Returns the IDs of the final states of the automaton.

Overrides:

getFinalStates in class TreeAutomaton<Pair<LeftState,RightState>>

Returns:

getRulesBottomUp

public Iterable<Rule> getRulesBottomUp(int label,
                                       int[] childStates)

Description copied from class: TreeAutomaton

Finds automaton rules bottom-up for a given list of child states and a given parent label. The method returns a collection of rules that can be used to assign a state to the parent node. The parent label is a numeric symbol ID, which represents a terminal symbol according to the automaton's signature.

Specified by:

getRulesBottomUp in class TreeAutomaton<Pair<LeftState,RightState>>

Returns:

getRulesTopDown

public Iterable<Rule> getRulesTopDown(int label,
                                      int parentState)

Description copied from class: TreeAutomaton

Finds automaton rules top-down for a given parent state and label. The method returns a collection of rules that can be used to assign states to the children. The parent label is a numeric symbol ID, which represents a terminal symbol according to the automaton's signature.

Note that not every method of TreeAutomaton is safely available in your implementation of getRulesTopDown. Most notably, you can't use the default implementation of TreeAutomaton.getAllStates(), because that method makes all rules of the automaton explicit and calls TreeAutomaton.getRulesTopDown(int, int) in the process, leading to an infinite recursion.

Specified by:

getRulesTopDown in class TreeAutomaton<Pair<LeftState,RightState>>

Returns:

makeAllRulesExplicitEarley

public void makeAllRulesExplicitEarley()

This implements an interesection algorithm in the style of the early algorithm, which predicts possible transition based on the first input automaton and then finds matching rules based on the second input automaton.

intersectBottomUpNaive

public static IntersectionAutomaton intersectBottomUpNaive(TreeAutomaton lhs,
                                                           TreeAutomaton rhs)

Helper method which creates an intersection automaton and makes all rules explicit with the default algorithm.

Parameters:

lhs -

rhs -

Returns:

intersectTopDownBottomUpCKY

public static IntersectionAutomaton intersectTopDownBottomUpCKY(TreeAutomaton lhs,
                                                                TreeAutomaton rhs)

Helper method which creates an intersection automaton and makes all rules explicit with the CKY algorithm.

Parameters:

lhs -

rhs -

Returns: