TreeAutomaton (alto 2.2-SNAPSHOT API)

java.lang.Object
- de.up.ling.irtg.automata.TreeAutomaton<State>

All Implemented Interfaces:

Intersectable<State>, Serializable

Direct Known Subclasses:

ConcreteTreeAutomaton, CondensedBottomUpIntersectionAutomaton, CondensedTreeAutomaton, GenericCondensedIntersectionAutomaton, IntersectionAutomaton, InverseHomAutomaton, NonCondensedIntersectionAutomaton, NondeletingInverseHomAutomaton, SGraphBRDecompositionAutomatonBottomUp, SGraphBRDecompositionAutomatonTopDown, SingletonAutomaton, TagStringAlgebra.TagDecompositionAutomaton, UniversalAutomaton
```
public abstract class TreeAutomaton<State>
extends Object
implements Serializable, Intersectable<State>
```
A finite tree automaton. Objects of this class can be simultaneously seen as a bottom-up or a top-down tree automaton, by querying them for rules using the methods getRulesBottomUp(int, int[]) or getRulesTopDown(int, int). The method getFinalStates() returns the set of states that must be assigned to the root of an accepted tree; that is, the final states of a bottom-up automaton or the initial states of a top-down automaton.
States and labels in the automaton are internally represented as int numbers, starting at 1. You can translate between numeric state IDs and the actual state objects (of the class State which is given as a type parameter to the class) using getStateForId(int) and getIdForState(java.lang.Object). You can translate between numeric label IDs and the actual labels (of class String) using the automaton's signature, obtained by calling getSignature() .
You can implement subclasses of TreeAutomaton to represent specific types of tree automata. These implementations may be lazy, which means that they do not initially represent all rules of the automaton explicitly. Such implementations override getRulesBottomUp(int, int[]) and getRulesTopDown(int, int) and compute the correct rules on the fly. Certain methods enforce the explicit computation of all rules in the automaton; this is expensive, and is noted in the method descriptions.

Author:

koller

See Also:

Serialized Form

Nested Class Summary

Nested Classes
Modifier and Type Class and Description

static interface TreeAutomaton.BottomUpStateVisitor

Nested Classes
Modifier and Type	Class and Description
`static interface`	`TreeAutomaton.BottomUpStateVisitor`

Field Summary

Fields
Modifier and Type Field and Description

static DebuggingWriter D

static boolean DEBUG_STORE

Fields
Modifier and Type	Field and Description
`static DebuggingWriter`	`D`
`static boolean`	`DEBUG_STORE`

Constructor Summary

Constructors
Constructor and Description

TreeAutomaton(Signature signature)

Constructors
Constructor and Description
`TreeAutomaton(Signature signature)`

Method Summary

All Methods Instance Methods Abstract Methods Concrete Methods
Modifier and Type	Method and Description
`boolean`	`accepts(Tree<String> tree)` Determines whether the automaton accepts the given tree.
`boolean`	`acceptsRaw(Tree<Integer> tree)` Determines whether the automaton accepts the given tree, using symbol IDs.
`void`	`analyze()` Prints some statistics about this automaton.
`ConcreteTreeAutomaton<State>`	`asConcreteTreeAutomaton()` Computes a concrete representation of this automaton.
`ConcreteTreeAutomaton`	`asConcreteTreeAutomatonBottomUp()` Computes a concrete representation of this automaton.
`ConcreteTreeAutomaton<String>`	`asConcreteTreeAutomatonWithStringStates()` Computes a concrete representation of this automaton, with string states.
`long`	`countTrees()` Returns the number of trees in the language of this automaton.
`Rule`	`createRule(int parent, int label, int[] children, double weight)` Creates a new rule.
`Rule`	`createRule(int parent, int label, List<Integer> children, double weight)` Creates a new rule.
`Rule`	`createRule(State parent, String label, List<State> children)` Creates a rule for this automaton.
`Rule`	`createRule(State parent, String label, List<State> children, double weight)` Creates a weighted rule for this automaton.
`Rule`	`createRule(State parent, String label, State[] children)` Creates a rule for this automaton.
`Rule`	`createRule(State parent, String label, State[] children, double weight)` Creates a weighted rule for this automaton.
`TreeAutomaton<Set<State>>`	`determinize()`
`TreeAutomaton<Set<State>>`	`determinize(List<IntSet> newStateToOldStateSet)`
`void`	`dumpToFile(String filename)`
`boolean`	`equals(Object o)` Compares two automata for equality.
`<E> Int2ObjectMap<E>`	`evaluateInSemiring(Semiring<E> semiring, RuleEvaluator<E> evaluator)` Evaluates all states of the automaton bottom-up in a semiring.
`<E> Int2ObjectMap<E>`	`evaluateInSemiring(Semiring<E> semiring, RuleEvaluator<E> evaluator, List<Integer> statesInOrder)`
`<E> Map<Integer,E>`	`evaluateInSemiringTopDown(Semiring<E> semiring, RuleEvaluatorTopDown<E> evaluator)` Evaluates all states of the automaton top-down in a semiring.
`void`	`foreachRuleBottomUpForSets(IntSet labelIds, List<IntSet> childStateSets, SignatureMapper signatureMapper, Consumer<Rule> fn)`
`void`	`foreachRuleTopDown(int parentState, Consumer<Rule> fn)` Iterates over all rules with the given parent.
`void`	`foreachStateInBottomUpOrder(TreeAutomaton.BottomUpStateVisitor visitor)`
`IntSet`	`getAllLabels()` Returns a set of label IDs that contains all the terminal symbols that occur in rules of this automaton.
`Iterable<Rule>`	`getAllRulesTopDown()`
`IntSet`	`getAllStates()` Returns the IDs of all states in this automaton.
`IntSet`	`getFinalStates()` Returns the IDs of the final states of the automaton.
`int`	`getIdForState(State state)` Returns the numeric ID for the given state.
`IntIterable`	`getLabelsTopDown(int parentState)` Returns a set that contains all terminal symbols f such that the automaton has top-down transition rules parentState -> f(...).
`long`	`getNumberOfRules()` Returns the number of rules in this automaton.
`int`	`getNumberOfSeenStates()`
`Tree<Rule>`	`getRandomRuleTree()`
`Tree<Rule>`	`getRandomRuleTreeFromInside()`
`Tree<String>`	`getRandomTree()` Generates a random tree from the language of this tree automaton.
`Tree<String>`	`getRandomTreeFromInside()`
`IntSet`	`getReachableStates()` Returns the set of all reachable states.
`abstract Iterable<Rule>`	`getRulesBottomUp(int labelId, int[] childStates)` Finds automaton rules bottom-up for a given list of child states and a given parent label.
`Iterable<Rule>`	`getRulesBottomUp(int labelId, List<Integer> childStates)` Finds automaton rules bottom-up.
`Iterable<Rule>`	`getRulesBottomUp(IntSet labelIds, List<Integer> childStates)` Finds automaton rules bottom-up for a given list of child states and a given set of parent labels.
`Iterable<Rule>`	`getRuleSet()` Returns the set of all rules of this automaton.
`Iterable<Rule>`	`getRulesForRhsState(int rhsState)`
`Iterable<Rule>`	`getRulesTopDown(int parentState)` Finds all automaton rules top-down with a given state on the left-hand side.
`abstract Iterable<Rule>`	`getRulesTopDown(int labelId, int parentState)` Finds automaton rules top-down for a given parent state and label.
`Tree<Rule>`	`getRuleTree(Tree<Integer> derivationTree)` Returns a tree of automaton rules that generates the given tree.
`Signature`	`getSignature()` Returns the signature of the automaton.
`State`	`getStateForId(int stateId)` Returns the state for the given numeric state ID.
`Interner`	`getStateInterner()` Returns the state interner for this tree automaton.
`List<Integer>`	`getStatesInBottomUpOrder()` Returns a topological ordering of the states, such that later nodes always occur above earlier nodes in any run of the automaton on a tree.
`Set<State>`	`getStoredConstantsForID(int labelID)` If this automaton has stored states for all the constants in its signature, more precisely if hasStoredConstants() returns true, then this returns the states corresponding to the constant described by the label ID in the signature.
`double`	`getWeight(Tree<String> tree)` Computes the weight of the tree, given the (weighted) tree automaton.
`double`	`getWeightRaw(Tree<Integer> tree)` Computes the weight of the tree, given the (weighted) tree automaton.
`boolean`	`hasRuleWithPrefix(int label, List<Integer> prefixOfChildren)` Returns true whenever the automaton has a bottom-up rule whose first n child states are the n child states that are passed as the prefixOfChildren argument.
`boolean`	`hasStoredConstants()` Returns true if the
`TreeAutomaton`	`homomorphism(Homomorphism hom)` Computes the image of this automaton under a homomorphism.
`Int2ObjectMap<Double>`	`inside()` Returns a map representing the inside probability of each reachable state.
`<OtherState> TreeAutomaton<Pair<State,OtherState>>`	`intersect(Intersectable<OtherState> other)` Intersects this automaton with another one.
`<OtherState> TreeAutomaton<Pair<State,OtherState>>`	`intersect(TreeAutomaton<OtherState> other, SignatureMapper mapper)`
`<OtherState> TreeAutomaton<Pair<State,OtherState>>`	`intersectBottomUp(TreeAutomaton<OtherState> other)` Intersects this automaton with another one, using a bottom-up algorithm.
`<OtherState> TreeAutomaton<Pair<State,OtherState>>`	`intersectCondensed(CondensedTreeAutomaton<OtherState> other)`
`<OtherState> TreeAutomaton<Pair<State,OtherState>>`	`intersectCondensed(CondensedTreeAutomaton<OtherState> other, PruningPolicy pp)`
`<OtherState> TreeAutomaton<Pair<State,OtherState>>`	`intersectCondensed(CondensedTreeAutomaton<OtherState> other, SignatureMapper signatureMapper)`
`<OtherState> TreeAutomaton<Pair<State,OtherState>>`	`intersectCondensedBottomUp(CondensedTreeAutomaton<OtherState> other)`
`<OtherState> TreeAutomaton<Pair<State,OtherState>>`	`intersectCondensedBottomUp(CondensedTreeAutomaton<OtherState> other, SignatureMapper signatureMapper)`
`<OtherState> TreeAutomaton<Pair<State,OtherState>>`	`intersectEarley(TreeAutomaton<OtherState> other)` Intersects this automaton with another one, using an Earley-style intersection algorithm.
`<OtherState> TreeAutomaton<Pair<State,OtherState>>`	`intersectViterbi(CondensedTreeAutomaton<OtherState> other)`
`<OtherState> TreeAutomaton<Pair<State,OtherState>>`	`intersectViterbi(CondensedTreeAutomaton<OtherState> other, SignatureMapper signatureMapper)`
`CondensedTreeAutomaton`	`inverseCondensedHomomorphism(Homomorphism hom)`
`TreeAutomaton`	`inverseHomomorphism(Homomorphism hom)` Computes the pre-image of this automaton under a homomorphism.
`abstract boolean`	`isBottomUpDeterministic()` Determines whether the automaton is deterministic if read as a bottom-up automaton.
`boolean`	`isCyclic()` Returns the set of all rules, indexed by parent label and children states.
`boolean`	`isEmpty()` Determines whether the language accepted by this automaton is empty.
`boolean`	`isStoring()` returns whether storeRule actually stores the rule or does nothing.
`Set<Tree<String>>`	`language()` Computes the tree language accepted by this automaton.
`Iterable<Tree<String>>`	`languageIterable()` Returns an Iterable over the language of this automaton.
`Iterator<Tree<String>>`	`languageIterator()` Returns an iterator over the language of this automaton.
`Iterator<Tree<Integer>>`	`languageIteratorRaw()` Returns an iterator over the language of this automaton, encoded using symbol IDs.
`Set<Tree<Integer>>`	`languageRaw()` Computes the tree language accepted by this automaton.
`void`	`makeAllRulesExplicit()` Computes all rules in this automaton and stores them in the cache.
`SiblingFinder`	`newSiblingFinder(int labelID)` This returns an object that stores and finds possible partners for a given state given a rule label.
`void`	`normalizeRuleWeights()` Modifies the weights of the rules in this automaton such that the weights of all rules with the same parent state sum to one.
`Map<Integer,Double>`	`outside(Map<Integer,Double> inside)` Returns a map representing the outside probability of each reachable state.
`boolean`	`processAllRulesBottomUp(Consumer<Rule> processingFunction)` Iterates through all rules top-down, applying processingFunction to each rule found.
`void`	`processAllRulesTopDown(Consumer<Rule> processingFunction)` Iterates through all rules top-down, applying processingFunction to each rule found.
`TreeAutomaton<State>`	`reduceTopDown()` Reduces the automaton, top-down.
`Iterable<State>`	`run(Tree<String> tree)` Runs the automaton bottom-up on the given tree and returns the set of possible states for the root.
`<TreeLabels> IntIterable`	`run(Tree<TreeLabels> node, ToIntFunction<TreeLabels> labelIdSource, ToIntFunction<Tree<TreeLabels>> subst)` Runs the automaton bottom-up on the given tree, using functions that extract symbol IDs from node labels and assign states to specific subtrees.
`IntIterable`	`runRaw(Tree<Integer> tree)` Runs the automaton bottom-up on the given tree, using symbol IDs, and returns the set of possible states for the root.
`void`	`setRulePrintingFilter(com.google.common.base.Predicate<Rule> filter)` Sets a filter for printing the automaton's rules.
`void`	`setSkipFail()` Enables the skip-fail filter for printing the automaton's rules.
`void`	`setStoring(boolean doStore)` sets whether storeRule actually stores the rule or does nothing.
`Iterator<WeightedTree>`	`sortedLanguageIterator()` Returns an iterator over the weighted language of this automaton.
`boolean`	`supportsBottomUpQueries()`
`boolean`	`supportsTopDownQueries()`
`String`	`toString()` Computes a string representation of this automaton.
`String`	`toStringBottomUp()` Computes a string representation of this automaton, bottom-up.
`boolean`	`useSiblingFinder()` Algorithms such as invhom check this function to decide whether their sibling finder variant should be used or not.
`Tree<String>`	`viterbi()` Computes the highest-weighted tree in the language of this (weighted) automaton, using the Viterbi algorithm.
`WeightedTree`	`viterbiRaw()` Computes the highest-weighted tree in the language of this (weighted) automaton, using the Viterbi algorithm.
`void`	`write(Writer writer)`

Methods inherited from class java.lang.Object
getClass, hashCode, notify, notifyAll, wait, wait, wait

- Field Detail
  - DEBUG_STORE
```
public static boolean DEBUG_STORE
```
  - D
```
public static DebuggingWriter D
```
- Constructor Detail
  - TreeAutomaton
```
public TreeAutomaton(Signature signature)
```
- Method Detail
  - getIdForState
```
public int getIdForState(State state)
```
    Returns the numeric ID for the given state. If the automaton does not have a state of the given name, the method returns 0.
    
    Parameters:
    
    state -
    
    Returns:
  - getStateForId
```
public State getStateForId(int stateId)
```
    Returns the state for the given numeric state ID. If the automaton does not have a state with this ID, the method returns null.
    
    Parameters:
    
    stateId -
    
    Returns:
  - getSignature
```
public Signature getSignature()
```
    Returns the signature of the automaton.
    
    Returns:
  - isStoring
```
public boolean isStoring()
```
    returns whether storeRule actually stores the rule or does nothing.
    
    Returns:
  - setStoring
```
public void setStoring(boolean doStore)
```
    sets whether storeRule actually stores the rule or does nothing.
    
    Parameters:
    
    doStore -
  - getRulesBottomUp
```
public abstract Iterable<Rule> getRulesBottomUp(int labelId,
                                                int[] childStates)
```
    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.
    
    Parameters:
    
    labelId -
    
    childStates -
    
    Returns:
  - getRulesBottomUp
```
public Iterable<Rule> getRulesBottomUp(int labelId,
                                       List<Integer> childStates)
```
    Finds automaton rules bottom-up. This is like getRulesBottomUp(int, int[]), but with a List rather than an array of child states.
    
    Parameters:
    
    labelId -
    
    childStates -
    
    Returns:
  - getRulesBottomUp
```
public Iterable<Rule> getRulesBottomUp(IntSet labelIds,
                                       List<Integer> childStates)
```
    Finds automaton rules bottom-up for a given list of child states and a given set of parent labels. The method returns an iterable which contains all rules that have the given child states and whose label is contained in the "labelIds" set.
    
    Parameters:
    
    labelIds -
    
    childStates -
    
    Returns:
  - foreachRuleBottomUpForSets
```
public void foreachRuleBottomUpForSets(IntSet labelIds,
                                       List<IntSet> childStateSets,
                                       SignatureMapper signatureMapper,
                                       Consumer<Rule> fn)
```
  - getRulesTopDown
```
public abstract Iterable<Rule> getRulesTopDown(int labelId,
                                               int parentState)
```
    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 getAllStates(), because that method makes all rules of the automaton explicit and calls getRulesTopDown(int, int) in the process, leading to an infinite recursion.
    
    Parameters:
    
    labelId -
    
    parentState -
    
    Returns:
  - getRulesTopDown
```
public Iterable<Rule> getRulesTopDown(int parentState)
```
    Finds all automaton rules top-down with a given state on the left-hand side. The method uses getRulesTopDown to collect all rules for this state and any label that is returned by getLabelsTopDown. The method necessarily enforces the computation of all top-down rules for the given parentState, but does no further copying of rules beyond this. Due to the way the top-down index data structures are implemented, this method is significantly faster if the tree automaton is explicit.
    
    Parameters:
    
    parentState -
    
    Returns:
  - foreachRuleTopDown
```
public void foreachRuleTopDown(int parentState,
                               Consumer<Rule> fn)
```
    Iterates over all rules with the given parent. The consumer fn is applied to each rule. Because construction of iterables and iterators is avoided, this iteration can be a bit faster than iterating over getRulesTopDown(int). Due to the way the top-down index data structures are implemented, this method is significantly faster if the tree automaton is explicit.
    
    Parameters:
    
    parentState -
    
    fn -
  - isBottomUpDeterministic
```
public abstract boolean isBottomUpDeterministic()
```
    Determines whether the automaton is deterministic if read as a bottom-up automaton.
    
    Returns:
  - getLabelsTopDown
```
public IntIterable getLabelsTopDown(int parentState)
```
    Returns a set that contains all terminal symbols f such that the automaton has top-down transition rules parentState -> f(...). The set returned by this method may contain symbol IDs for which such a transition does not actually exist; it is only guaranteed that all symbols for which transitions exist are also in the set.
    The default implementation in TreeAutomaton distinguishes two cases. If the automaton is fully explicit, the method returns those labels for which the parent has (explicit) rules. Otherwise, the method returns all label IDs in the signature.
    Subclasses (especially lazy automata) may replace this with more specific implementations.
    
    Parameters:
    
    parentState -
    
    Returns:
  - getAllLabels
```
public IntSet getAllLabels()
```
    Returns a set of label IDs that contains all the terminal symbols that occur in rules of this automaton. The default implementation simply returns the set of all symbols in the signature. Derived classes are encouraged to overwrite this with a tighter upper bound.
    
    Returns:
  - hasRuleWithPrefix
```
public boolean hasRuleWithPrefix(int label,
                                 List<Integer> prefixOfChildren)
```
    Returns true whenever the automaton has a bottom-up rule whose first n child states are the n child states that are passed as the prefixOfChildren argument. It is not required that the method returns false if the automaton does _not_ have such a rule; i.e., the method may overestimate the existence of rules. The default implementation always returns true. Derived automaton classes for which an efficient, more precise test is available may override this method appropriately.
    
    Parameters:
    
    label -
    
    prefixOfChildren -
    
    Returns:
  - getFinalStates
```
public IntSet getFinalStates()
```
    Returns the IDs of the final states of the automaton.
    
    Returns:
  - getAllStates
```
public IntSet getAllStates()
```
    Returns the IDs of all states in this automaton. If the automaton is a lazy implementation, it is required to make all rules explicit before returning, to the extent that it is necessary to list all states. This may be slow.
    
    Returns:
  - getRulesForRhsState
```
public Iterable<Rule> getRulesForRhsState(int rhsState)
```
  - getRuleSet
```
public Iterable<Rule> getRuleSet()
```
    Returns the set of all rules of this automaton. This is done by concatenating iterators over the explicit bottom-up rules. Note that this necessarily _computes_ the set of all rules, which may be expensive for lazy automata.
    Note that this method calls makeAllRulesExplicit() to enumerate all rules, and then returns the set of all rules in the rule store. You can therefore break its functionality if you override makeAllRulesExplicit carelessly.
    
    Returns:
  - getAllRulesTopDown
```
public Iterable<Rule> getAllRulesTopDown()
```
  - hasStoredConstants
```
public boolean hasStoredConstants()
```
    Returns true if the
    
    Returns:
  - getStoredConstantsForID
```
public Set<State> getStoredConstantsForID(int labelID)
```
    If this automaton has stored states for all the constants in its signature, more precisely if hasStoredConstants() returns true, then this returns the states corresponding to the constant described by the label ID in the signature.
    
    Parameters:
    
    labelID -
    
    Returns:
  - isCyclic
```
public boolean isCyclic()
```
    Returns the set of all rules, indexed by parent label and children states.
    
    Returns:
  - countTrees
```
public long countTrees()
```
    Returns the number of trees in the language of this automaton. Note that this is faster than computing the entire language. The method only works if the automaton is acyclic, and only returns correct results if the automaton is bottom-up deterministic.
    
    Returns:
  - inside
```
public Int2ObjectMap<Double> inside()
```
    Returns a map representing the inside probability of each reachable state.
    
    Returns:
  - outside
```
public Map<Integer,Double> outside(Map<Integer,Double> inside)
```
    Returns a map representing the outside probability of each reachable state.
    
    Parameters:
    
    inside - a map representing the inside probability of each state.
    
    Returns:
  - viterbi
```
public Tree<String> viterbi()
```
    Computes the highest-weighted tree in the language of this (weighted) automaton, using the Viterbi algorithm. If the language is empty, return null.
    
    Returns:
  - viterbiRaw
```
public WeightedTree viterbiRaw()
```
    Computes the highest-weighted tree in the language of this (weighted) automaton, using the Viterbi algorithm. If the language is empty, return null. Unlike viterbi(), this method returns a tree whose nodes are labeled with label IDs, as opposed to the labels (Strings) themselves. It also returns the weight of the top-ranked tree.
    
    Returns:
  - languageRaw
```
public Set<Tree<Integer>> languageRaw()
```
    Computes the tree language accepted by this automaton. The nodes in these trees are labeled with numeric symbol IDs. Notice that if the language is infinite, this method will not terminate. Get a languageIterator() in this case, in order to enumerate as many trees as you want.
    
    Returns:
  - language
```
public Set<Tree<String>> language()
```
    Computes the tree language accepted by this automaton. Notice that if the language is infinite, this method will not terminate. Get a languageIterator() in this case, in order to enumerate as many trees as you want.
    
    Returns:
  - getRandomTree
```
public Tree<String> getRandomTree()
```
    Generates a random tree from the language of this tree automaton. The probability of a tree is the product of the probabilities of the rules that were used to build it. The probability for the rule A -> f(B1,...,Bn) is the weight of that rule, divided by the sum of all weights for rules with left-hand side A. If the automaton has multiple final states, one of these is chosen with uniform probability.
    
    Returns:
  - getRandomRuleTree
```
public Tree<Rule> getRandomRuleTree()
```
  - getRandomRuleTreeFromInside
```
public Tree<Rule> getRandomRuleTreeFromInside()
```
  - getRandomTreeFromInside
```
public Tree<String> getRandomTreeFromInside()
```
  - setRulePrintingFilter
```
public void setRulePrintingFilter(com.google.common.base.Predicate<Rule> filter)
```
    Sets a filter for printing the automaton's rules. This filter is being used in the toString() method to decide which rules are included in the string representation for the automaton. You can use this to suppress the presentation of rules you don't care about.
    
    Parameters:
    
    filter -
  - setSkipFail
```
public void setSkipFail()
```
    Enables the skip-fail filter for printing the automaton's rules. This suppresses all rules involving the state q_FAIL_ (from InverseHomAutomaton) when toString() is computed for this automaton.
  - equals
```
public boolean equals(Object o)
```
    Compares two automata for equality. Two automata are equal if they have the same rules and the same final states. All label and state IDs are resolved to the actual labels and states for this comparison.
    The implementation of this method is currently very slow, and should only be used for small automata (e.g. in unit tests).
    
    Overrides:
    
    equals in class Object
    
    Parameters:
    
    o -
    
    Returns:
  - toString
```
public String toString()
```
    Computes a string representation of this automaton. This method elaborates the rules of the automaton in a top-down fashion, starting with the final states and working from parents to children. TODO *** this is no longer true!
    
    Overrides:
    
    toString in class Object
    
    Returns:
  - write
```
public void write(Writer writer)
           throws Exception
```
    Throws:
    
    Exception
  - toStringBottomUp
```
public String toStringBottomUp()
```
    Computes a string representation of this automaton, bottom-up. This method elaborates the rules of the automaton in a bottom-up fashion, starting from the rules for the zero-place terminal symbols and working from children to parents. It may be useful as an alternative to toString() when debugging lazy automata.
    
    Returns:
  - makeAllRulesExplicit
```
public void makeAllRulesExplicit()
```
    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.
  - asConcreteTreeAutomaton
```
public ConcreteTreeAutomaton<State> asConcreteTreeAutomaton()
```
    Computes a concrete representation of this automaton. The method returns a ConcreteTreeAutomaton that is equals to the given automaton. The method enumerates the rules of the automaton top-down, so it will only work if getRulesTopDown(int, int) is implemented.
    
    Returns:
  - asConcreteTreeAutomatonWithStringStates
```
public ConcreteTreeAutomaton<String> asConcreteTreeAutomatonWithStringStates()
```
    Computes a concrete representation of this automaton, with string states. The method returns a ConcreteTreeAutomaton that looks exactly like the given automaton when printed with toString() (except perhaps for reordering of rules), but all state objects (of class State) are replaced by their string representations. Thus the states of the returned automaton are always strings. This is mostly useful for testing, when automata with string states are read from string literals.
    
    Returns:
  - asConcreteTreeAutomatonBottomUp
```
public ConcreteTreeAutomaton asConcreteTreeAutomatonBottomUp()
```
    Computes a concrete representation of this automaton. The method returns a ConcreteTreeAutomaton that is equals to the given automaton. The method enumerates the rules of the automaton bottom-up.
    
    Returns:
  - intersect
```
public <OtherState> TreeAutomaton<Pair<State,OtherState>> intersect(Intersectable<OtherState> other)
```
    Intersects this automaton with another one. This is a default implementation, which currently performs bottom-up intersection.
    
    Type Parameters:
    
    OtherState - the state type of the other automaton.
    
    Parameters:
    
    other - the other automaton.
    
    Returns:
    
    an automaton representing the intersected language.
  - intersect
```
public <OtherState> TreeAutomaton<Pair<State,OtherState>> intersect(TreeAutomaton<OtherState> other,
                                                                    SignatureMapper mapper)
```
  - intersectBottomUp
```
public <OtherState> TreeAutomaton<Pair<State,OtherState>> intersectBottomUp(TreeAutomaton<OtherState> other)
```
    Intersects this automaton with another one, using a bottom-up algorithm. This intersection algorithm queries both automata for rules bottom-up.
    
    Type Parameters:
    
    OtherState -
    
    Parameters:
    
    other -
    
    Returns:
  - intersectCondensed
```
public <OtherState> TreeAutomaton<Pair<State,OtherState>> intersectCondensed(CondensedTreeAutomaton<OtherState> other,
                                                                             SignatureMapper signatureMapper)
```
  - intersectCondensed
```
public <OtherState> TreeAutomaton<Pair<State,OtherState>> intersectCondensed(CondensedTreeAutomaton<OtherState> other)
```
  - intersectCondensed
```
public <OtherState> TreeAutomaton<Pair<State,OtherState>> intersectCondensed(CondensedTreeAutomaton<OtherState> other,
                                                                             PruningPolicy pp)
```
  - intersectCondensedBottomUp
```
public <OtherState> TreeAutomaton<Pair<State,OtherState>> intersectCondensedBottomUp(CondensedTreeAutomaton<OtherState> other,
                                                                                     SignatureMapper signatureMapper)
```
  - intersectCondensedBottomUp
```
public <OtherState> TreeAutomaton<Pair<State,OtherState>> intersectCondensedBottomUp(CondensedTreeAutomaton<OtherState> other)
```
  - intersectViterbi
```
public <OtherState> TreeAutomaton<Pair<State,OtherState>> intersectViterbi(CondensedTreeAutomaton<OtherState> other,
                                                                           SignatureMapper signatureMapper)
```
  - intersectViterbi
```
public <OtherState> TreeAutomaton<Pair<State,OtherState>> intersectViterbi(CondensedTreeAutomaton<OtherState> other)
```
  - intersectEarley
```
public <OtherState> TreeAutomaton<Pair<State,OtherState>> intersectEarley(TreeAutomaton<OtherState> other)
```
    Intersects this automaton with another one, using an Earley-style intersection algorithm. This intersection algorithm queries this automaton for rules top-down (= Predict steps) and the other automaton bottom-up (= Complete steps).
    
    Type Parameters:
    
    OtherState -
    
    Parameters:
    
    other -
    
    Returns:
  - inverseHomomorphism
```
public TreeAutomaton inverseHomomorphism(Homomorphism hom)
```
    Computes the pre-image of this automaton under a homomorphism.
    
    Parameters:
    
    hom - the homomorphism.
    
    Returns:
    
    an automaton representing the homomorphic pre-image.
  - inverseCondensedHomomorphism
```
public CondensedTreeAutomaton inverseCondensedHomomorphism(Homomorphism hom)
```
  - homomorphism
```
public TreeAutomaton homomorphism(Homomorphism hom)
```
    Computes the image of this automaton under a homomorphism. This will only work if the homomorphism is linear.
    
    Parameters:
    
    hom -
    
    Returns:
  - acceptsRaw
```
public boolean acceptsRaw(Tree<Integer> tree)
```
    Determines whether the automaton accepts the given tree, using symbol IDs. The nodes of the tree are assumed to be labeled with numeric symbol IDs, which represent terminal symbols according to the automaton's signature.
    
    Parameters:
    
    tree -
    
    Returns:
  - accepts
```
public boolean accepts(Tree<String> tree)
```
    Determines whether the automaton accepts the given tree. The tree nodes are assumed to be labeled with strings specifying the terminal symbols.
    
    Parameters:
    
    tree -
    
    Returns:
  - getRuleTree
```
public Tree<Rule> getRuleTree(Tree<Integer> derivationTree)
                       throws Exception
```
    Returns a tree of automaton rules that generates the given tree. This method assumes that the automaton can only accept the tree in a single way; this is true, for instance, if the automaton is a parse chart and the tree is a derivation tree. If this is not the case, the method throws an exception with some debugging information. If the automaton does not accept the tree at all, the method returns null.
    
    Parameters:
    
    derivationTree -
    
    Returns:
    
    Throws:
    
    Exception
  - run
```
public Iterable<State> run(Tree<String> tree)
```
    Runs the automaton bottom-up on the given tree and returns the set of possible states for the root. The nodes of the tree are assumed to be labeled with strings specifying the terminal symbols.
    
    Parameters:
    
    tree -
    
    Returns:
  - runRaw
```
public IntIterable runRaw(Tree<Integer> tree)
```
    Runs the automaton bottom-up on the given tree, using symbol IDs, and returns the set of possible states for the root. The nodes of the tree are assumed to be labeled with numeric symbol IDs, which represent terminal symbols according to the automaton's signature.
    
    Parameters:
    
    tree -
    
    Returns:
  - run
```
public <TreeLabels> IntIterable run(Tree<TreeLabels> node,
                                    ToIntFunction<TreeLabels> labelIdSource,
                                    ToIntFunction<Tree<TreeLabels>> subst)
```
    Runs the automaton bottom-up on the given tree, using functions that extract symbol IDs from node labels and assign states to specific subtrees. The method returns the set of states that can be assigned to the root of the tree.
    The node labels of the tree are assumed to be of an arbitrary class, specified by the type parameter "TreeLabels". The "labelIdSource" argument specifies a function that maps objects of class TreeLabels to symbol IDs, which represent node labels according to the automaton's signature.
    The "subst" argument maps nodes of the tree to states. It is called for each node of the tree, bottom-up. If the subst function returns 0, the state for the node is computed from the automaton's rules and the label and child states of the node in the usual way. If subst returns non-zero for a certain node, the return value is directly assigned as the state of that node. This mechanism can be used, for instance, to assign states to variable nodes.
    
    Type Parameters:
    
    TreeLabels -
    
    Parameters:
    
    node -
    
    subst -
    
    Returns:
  - getWeightRaw
```
public double getWeightRaw(Tree<Integer> tree)
```
    Computes the weight of the tree, given the (weighted) tree automaton. The weight is the sum of the weights of all runs with which the automaton can accept the tree; the weight of a run is the product of the weights of the rules it uses. If the automaton does not accept the tree, the method returns a weight of zero.
    The labels of the nodes of the tree are assumed to be numeric symbol IDs, which specify node labels according to the automaton's signature.
    
    Parameters:
    
    tree -
    
    Returns:
  - getWeight
```
public double getWeight(Tree<String> tree)
```
    Computes the weight of the tree, given the (weighted) tree automaton. The weight is the sum of the weights of all runs with which the automaton can accept the tree; the weight of a run is the product of the weights of the rules it uses. If the automaton does not accept the tree, the method returns a weight of zero.
    The method also returns a weight of zero if the tree is null.
    The labels of the nodes of the tree are assumed to be strings.
    
    Parameters:
    
    tree -
    
    Returns:
  - reduceTopDown
```
public TreeAutomaton<State> reduceTopDown()
```
    Reduces the automaton, top-down. This means that all states and rules that are not reachable by recursively expanding a final state, top-down, are removed. The method returns a new automaton with the same signature as this one. The method only works if the automaton is acyclic.
    
    Returns:
  - getReachableStates
```
public IntSet getReachableStates()
```
    Returns the set of all reachable states. A state is called reachable if it can be visited through recursively expanding a final state top-down using the rules of this automaton.
    
    Returns:
  - foreachStateInBottomUpOrder
```
public void foreachStateInBottomUpOrder(TreeAutomaton.BottomUpStateVisitor visitor)
```
  - evaluateInSemiring
```
public <E> Int2ObjectMap<E> evaluateInSemiring(Semiring<E> semiring,
                                               RuleEvaluator<E> evaluator,
                                               List<Integer> statesInOrder)
```
  - evaluateInSemiring
```
public <E> Int2ObjectMap<E> evaluateInSemiring(Semiring<E> semiring,
                                               RuleEvaluator<E> evaluator)
```
    Evaluates all states of the automaton bottom-up in a semiring. The evaluation of a state is the semiring sum of semiring zero plus the evaluations of all rules in which it is the parent. The evaluation of a rule is the semiring product of the evaluations of its child states, times the evaluation of the rule itself. The evaluation of a rule is determined by the RuleEvaluator argument. This method only works if the automaton is acyclic, so states can be processed in a well-defined bottom-up order. Only reachable states are assigned a value.
    
    Type Parameters:
    
    E -
    
    Parameters:
    
    semiring -
    
    evaluator -
    
    Returns:
    
    a map assigning values in the semiring to all reachable states.
  - evaluateInSemiringTopDown
```
public <E> Map<Integer,E> evaluateInSemiringTopDown(Semiring<E> semiring,
                                                    RuleEvaluatorTopDown<E> evaluator)
```
    Evaluates all states of the automaton top-down in a semiring. The evaluation of a state is the semiring sum of semiring zero plus the evaluations of all rules in which it is the parent. The evaluation of a rule is the semiring product of the evaluations of its child states, times the evaluation of the rule itself. The evaluation of a rule is determined by the RuleEvaluator argument. This method only works if the automaton is acyclic, so states can be processed in a well-defined top-down order. Only reachable states are assigned a value.
    
    Type Parameters:
    
    E -
    
    Parameters:
    
    semiring -
    
    evaluator -
    
    Returns:
    
    a map assigning values in the semiring to all reachable states.
  - getStatesInBottomUpOrder
```
public List<Integer> getStatesInBottomUpOrder()
```
    Returns a topological ordering of the states, such that later nodes always occur above earlier nodes in any run of the automaton on a tree. Note that only states that are reachable top-down from the final states are included in the list that is returned.
    
    Returns:
  - languageIterable
```
public Iterable<Tree<String>> languageIterable()
```
    Returns an Iterable over the language of this automaton. This allows iterating over the trees in the language using for( Tree tree : automaton.languageIterable() ). This also works if the language is infinite. If the automaton is weighted, the trees are iterated in descending order of weights.
    
    Returns:
  - languageIteratorRaw
```
public Iterator<Tree<Integer>> languageIteratorRaw()
```
    Returns an iterator over the language of this automaton, encoded using symbol IDs. The nodes of the trees are labeled with numeric symbol IDs, which encode node labels according to the automaton's signature. This also works if the language is infinite. If the automaton is weighted, the trees are iterated in descending order of weights.
    
    Returns:
  - isEmpty
```
public boolean isEmpty()
```
    Determines whether the language accepted by this automaton is empty.
    
    Returns:
  - languageIterator
```
public Iterator<Tree<String>> languageIterator()
```
    Returns an iterator over the language of this automaton. This also works if the language is infinite. If the automaton is weighted, the trees are iterated in descending order of weights. Therefore, to compute the k-best trees, you can simply enumerate the first k elements of this iterator.
    
    Returns:
  - sortedLanguageIterator
```
public Iterator<WeightedTree> sortedLanguageIterator()
```
    Returns an iterator over the weighted language of this automaton. The iterator enumerates weighted trees, which are pairs of trees with their weights, in descending order of weights. The tree in this pair has node labels which are numeric symbol IDs, which represent node labels according to the automaton's signature. They can be resolved to string-labeled trees using Signature.resolve(de.up.ling.tree.Tree).
    
    Returns:
  - getNumberOfRules
```
public long getNumberOfRules()
```
    Returns the number of rules in this automaton. The default implementation iterates over all rules, and can thus be quite slow.
    
    Returns:
  - analyze
```
public void analyze()
```
    Prints some statistics about this automaton.
  - createRule
```
public Rule createRule(int parent,
                       int label,
                       int[] children,
                       double weight)
```
    Creates a new rule. Note that this method only creates the rule object; it does not add it to the automaton. For a more convenient (if slightly less efficient) alternative, consider #createRule(java.lang.Object, java.lang.String, State[], double).
    
    Parameters:
    
    parent -
    
    label -
    
    children -
    
    weight -
    
    Returns:
  - createRule
```
public Rule createRule(int parent,
                       int label,
                       List<Integer> children,
                       double weight)
```
    Creates a new rule. Note that this method only creates the rule object; it does not add it to the automaton. For a more convenient (if slightly less efficient) alternative, consider createRule(java.lang.Object, java.lang.String, java.util.List, double).
    
    Parameters:
    
    parent -
    
    label -
    
    children -
    
    weight -
    
    Returns:
  - createRule
```
public Rule createRule(State parent,
                       String label,
                       State[] children,
                       double weight)
```
    Creates a weighted rule for this automaton. If the terminal symbol in the rule is not already known in the automaton's signature, it is added to the signature using the number of children as the arity.
    
    Parameters:
    
    parent - the rule's parent state
    
    label - the terminal symbol used in the rule
    
    children - the child states, from left to right (as an array)
    
    weight - the rule weight
    
    Returns:
  - createRule
```
public Rule createRule(State parent,
                       String label,
                       List<State> children,
                       double weight)
```
    Creates a weighted rule for this automaton. If the terminal symbol in the rule is not already known in the automaton's signature, it is added to the signature using the number of children as the arity.
    
    Parameters:
    
    parent - the rule's parent state
    
    label - the terminal symbol used in the rule
    
    children - the child states, from left to right (as a list)
    
    weight - the rule weight
    
    Returns:
  - createRule
```
public Rule createRule(State parent,
                       String label,
                       State[] children)
```
    Creates a rule for this automaton. If the terminal symbol in the rule is not already known in the automaton's signature, it is added to the signature using the number of children as the arity. The rule creates an unweighted rule by calling #createRule(java.lang.Object, java.lang.String, State[], double) with a weight of 1.
    
    Parameters:
    
    parent - the rule's parent state
    
    label - the terminal symbol used in the rule
    
    children - the child states, from left to right (as an array)
    
    Returns:
  - createRule
```
public Rule createRule(State parent,
                       String label,
                       List<State> children)
```
    Creates a rule for this automaton. If the terminal symbol in the rule is not already known in the automaton's signature, it is added to the signature using the number of children as the arity. The rule creates an unweighted rule by calling createRule(java.lang.Object, java.lang.String, java.util.List, double) with a weight of 1.
    
    Parameters:
    
    parent - the rule's parent state
    
    label - the terminal symbol used in the rule
    
    children - the child states, from left to right (as a list)
    
    Returns:
  - normalizeRuleWeights
```
public void normalizeRuleWeights()
```
    Modifies the weights of the rules in this automaton such that the weights of all rules with the same parent state sum to one. Note that this requires computing all the rules, which may be expensive for lazy automata.
  - getStateInterner
```
public Interner getStateInterner()
```
    Returns the state interner for this tree automaton. You should only use this method if you know what you're doing.
    
    Returns:
  - supportsTopDownQueries
```
public boolean supportsTopDownQueries()
```
  - supportsBottomUpQueries
```
public boolean supportsBottomUpQueries()
```
  - determinize
```
public TreeAutomaton<Set<State>> determinize(List<IntSet> newStateToOldStateSet)
```
  - determinize
```
public TreeAutomaton<Set<State>> determinize()
```
  - processAllRulesTopDown
```
public void processAllRulesTopDown(Consumer<Rule> processingFunction)
```
    Iterates through all rules top-down, applying processingFunction to each rule found.
    
    Parameters:
    
    processingFunction -
  - processAllRulesBottomUp
```
public boolean processAllRulesBottomUp(Consumer<Rule> processingFunction)
```
    Iterates through all rules top-down, applying processingFunction to each rule found. Returns true if a final state was found.
    
    Parameters:
    
    processingFunction -
    
    Returns:
  - getNumberOfSeenStates
```
public int getNumberOfSeenStates()
```
  - newSiblingFinder
```
public SiblingFinder newSiblingFinder(int labelID)
```
    This returns an object that stores and finds possible partners for a given state given a rule label. (see i.e. automata.condensed.PMFactoryRestrictive.) Default implementation returns all previously entered potential siblings, override and use automaton-specific indexing for faster parsing.
    
    Parameters:
    
    labelID -
    
    Returns:
  - useSiblingFinder
```
public boolean useSiblingFinder()
```
    Algorithms such as invhom check this function to decide whether their sibling finder variant should be used or not. Override this to return true, if your automaton has a non-trivial sibling finder implementation you want to use.
    
    Returns:
  - dumpToFile
```
public void dumpToFile(String filename)
                throws IOException
```
    Throws:
    
    IOException

Class TreeAutomaton<State>

Nested Class Summary

Field Summary

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Field Detail

DEBUG_STORE

D

Constructor Detail

TreeAutomaton

Method Detail

getIdForState

getStateForId

getSignature

isStoring

setStoring

getRulesBottomUp

getRulesBottomUp

getRulesBottomUp

foreachRuleBottomUpForSets

getRulesTopDown

getRulesTopDown

foreachRuleTopDown

isBottomUpDeterministic

getLabelsTopDown

getAllLabels

hasRuleWithPrefix

getFinalStates

getAllStates

getRulesForRhsState

getRuleSet

getAllRulesTopDown

hasStoredConstants

getStoredConstantsForID

isCyclic

countTrees

inside

outside

viterbi

viterbiRaw

languageRaw

language

getRandomTree

getRandomRuleTree

getRandomRuleTreeFromInside

getRandomTreeFromInside

setRulePrintingFilter

setSkipFail

equals

toString

write

toStringBottomUp

makeAllRulesExplicit

asConcreteTreeAutomaton

asConcreteTreeAutomatonWithStringStates

asConcreteTreeAutomatonBottomUp

intersect

intersect

intersectBottomUp

intersectCondensed

intersectCondensed

intersectCondensed

intersectCondensedBottomUp

intersectCondensedBottomUp

intersectViterbi

intersectViterbi

intersectEarley

inverseHomomorphism

inverseCondensedHomomorphism

homomorphism

acceptsRaw

accepts

getRuleTree

run

runRaw

run

getWeightRaw

getWeight

reduceTopDown