IDFA

Package

Class

Tree

Deprecated

Index

Help

PREV CLASS NEXT CLASS

FRAMES NO FRAMES

SUMMARY: NESTED | FIELD | CONSTR | METHOD

DETAIL: FIELD | CONSTR | METHOD

Class IDFA

java.lang.Object
  IDFA

public class IDFA
extends java.lang.Object

This class implements incomplete deterministic automata. The edges going out of a state are implemented in a Queue (class PairIntQueue). The automaton itself is an array of Queues. The space used by this implementation is O(n + k + e) for a deterministic automaton on k letters, n states and e edges, instead of O(k n) for the class DFA. This representation is preferable when k is large.

Field Summary
`Alphabet`	`alphabet` The alphabet.
`PairIntQueue[]`	`edges` The set of edges going out of a state.
`int`	`initial` The initial state.
`int`	`nbStates` The number of states.
`java.util.Set`	`terminal` The array of terminal states.

Constructor Summary
`IDFA()`
`IDFA(IDFA b)`
`IDFA(int nn)`
`IDFA(int nn, Alphabet a)`
`IDFA(int nn, int q)`

Method Summary
`void`	`addEdge(int p, char a, int q)` Adds to the automaton an edge from `p` to `q` labeled `a` if it does not exist already.
`void`	`addEdge(int p, int a, int q)` Adds to the automaton an edge from `p` to `q` labeled `alphabet.toChar(a)` if it does not exist already.
`void`	`addEdgeFast(int p, char a, int q)` Adds to the automaton an edge from `p` to `q` labeled `a`.
`void`	`addEdgeFast(int p, int a, int q)` Adds to the automaton an edge from `p` to `q` labeled `alphabet.toChar(a)`.
`void`	`addTerminal(int p)`
`IDFA`	`addWord(java.lang.String s)` Adds a word to the set recognized by an IDFA.
`IDFA`	`ecoMinimize()` Minimization in linear time using Revuz algorithm.
`void`	`ecoQuotient(int[] c)`
`int`	`enumerate(boolean[] b)` A call to `enumerate(isOn)` returns the number of states of the trimmed automaton.
`static IDFA`	`ex()`
`boolean`	`explore(int p, int[] mark)` A classical depth-first search.
`static IDFA`	`fromFile(java.lang.String name)`
`int[]`	`heigths()` Returns the array of heigths.
`int`	`heigthsRecursive(int p, int[] rgs)` A recursive method to compute the array of heigths from a state `p`.
`boolean`	`isAcyclic()` True if the automaton is a DAWG, i.e. if the graph of the automaton is acyclic.
`void`	`isOnPath(int p, boolean[] isOn)` Tests wheter the states are on a successful path of the automaton.
`boolean`	`isTerminal(int p)`
`static void`	`main(java.lang.String[] args)`
`IDFA`	`mergeLeaves()`
`IDFA`	`minimize(Minimizer m)`
`IDFA`	`mixMinimize()`
`int[]`	`nbByHeigth(int[] h)` Returns the array of numbers of states by heigth.
`int`	`next(int p, char c)` Returns the state `next(p,c)`.
`void`	`orderEdges()` Sorts the outgoing edges in alphabetic order.
`static IDFA`	`product(IDFA a, IDFA b)` Computes the direct product of the IDFA `a` and `b`.
`IDFA`	`quotient(int[] c)`
`IDFA`	`quotient(Partition part)`
`IDFA`	`randomFMinimize()`
`void`	`removeEdge(int p, char c)`
`int[]`	`renumber(boolean[] b)` Gives the new names of the states after eliminating those such that `b[i] = false`
`ICFA`	`reverse()` Computes the codeterministic automaton (ICFA) obtained by reversing the edges of a deterministic automaton (IDFA).
`void`	`show(java.lang.String nom)`
`java.lang.String`	`toString()`
`IDFA`	`trim()` Computes the trimmed automaton equivalent to a given acyclic automaton.
`int[]`	`width()` Computes the width (or outdegree) of each state.

Methods inherited from class java.lang.Object

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

Field Detail

nbStates

public int nbStates

The number of states.

edges

public PairIntQueue[] edges

The set of edges going out of a state.

initial

public int initial

The initial state.

terminal

public java.util.Set terminal

The array of terminal states. State p is terminal if terminal[p] = 1.

alphabet

public Alphabet alphabet

The alphabet.

Constructor Detail

IDFA

public IDFA()

IDFA

public IDFA(int nn)

IDFA

public IDFA(int nn,
            Alphabet a)

IDFA

public IDFA(int nn,
            int q)

IDFA

public IDFA(IDFA b)

Method Detail

product

public static IDFA product(IDFA a,
                           IDFA b)

Computes the direct product of the IDFA a and b. Both IDFA share the same alphabet.

isAcyclic

public boolean isAcyclic()

True if the automaton is a DAWG, i.e. if the graph of the automaton is acyclic.

explore

public boolean explore(int p,
                       int[] mark)

A classical depth-first search. Complexity O(m) where m is the number of edges.

Parameters:: p - the starting state.; mark - an array of marks interpreted as 0 = unmarked 1 = active 2 = terminated.
Returns:: true if the graph reachable from state p>/code> is acyclic.





isOnPath
public void isOnPath(int p,
                     boolean[] isOn)

Tests wheter the states are on a successful path of the automaton.
       Uses a depth first search from state p to fill the boolean
       array isOn.


Parameters:
p - a state
isOn - A boolean array with isOn[p] = true if
       there is a path to a terminal state from state p.





renumber
public int[] renumber(boolean[] b)

Gives the new names of the states after eliminating those
       such that b[i] = false



Returns:
the integer array index where 
       index[i] = n if i is the nth
       index such that b[i] = true.





enumerate
public int enumerate(boolean[] b)

A call to enumerate(isOn) returns the number 
       of states of the trimmed automaton.


Parameters:
b - a boolean array
Returns:
the number of indices i such that
       b[i] = true.





trim
public IDFA trim()

Computes the trimmed automaton equivalent to a given acyclic
       automaton.








addEdge
public void addEdge(int p,
                    char a,
                    int q)

Adds to the automaton an edge from p to q 
       labeled a if it does not exist already. Complexity
       O(k n) for an IDFA with k
       letters and n states.








addEdge
public void addEdge(int p,
                    int a,
                    int q)

Adds to the automaton an edge from p to q 
       labeled alphabet.toChar(a) if it does not exist already. Complexity
       O(k n) for an IDFA with k
       letters and n states.








addEdgeFast
public void addEdgeFast(int p,
                        char a,
                        int q)

Adds to the automaton an edge from p to q 
       labeled a. Complexity
       O(1).








addEdgeFast
public void addEdgeFast(int p,
                        int a,
                        int q)

Adds to the automaton an edge from p to q 
       labeled alphabet.toChar(a). Complexity
       O(1).








orderEdges
public void orderEdges()

Sorts the outgoing edges in alphabetic order.
       Complexity  O(u+n+e)








width
public int[] width()

Computes the width (or outdegree) of each state.
       Complexity O(n + e).



Returns:
the array wid of widths. The value of 
       wid[p]
       is the number of edges going out of p.





heigthsRecursive
public int heigthsRecursive(int p,
                            int[] rgs)

A recursive method to compute the array of heigths from a state 
       p.


Parameters:
p - the start state.





heigths
public int[] heigths()

Returns the array of heigths. The heigth of a state p 
       is the maximal
       length of a path starting at p.



Returns:
the array heigth of heigths.





nbByHeigth
public int[] nbByHeigth(int[] h)

Returns the array of numbers of states by heigth.


Parameters:
h - the array of heigths
Returns:
the array hh of numbers of states by heigth. 
       One has hh[p]=k if there are k 
       states at heigth k.





mergeLeaves
public IDFA mergeLeaves()








randomFMinimize
public IDFA randomFMinimize()








mixMinimize
public IDFA mixMinimize()
                 throws java.lang.Exception



Throws:
java.lang.Exception





ecoMinimize
public IDFA ecoMinimize()
                 throws java.lang.Exception

Minimization in linear time using Revuz algorithm.



Throws:
java.lang.Exception





minimize
public IDFA minimize(Minimizer m)
              throws java.lang.Exception



Throws:
java.lang.Exception





removeEdge
public void removeEdge(int p,
                       char c)








next
public int next(int p,
                char c)

Returns the state next(p,c).








addWord
public IDFA addWord(java.lang.String s)

Adds a word to the set recognized by an IDFA.








reverse
public ICFA reverse()

Computes the codeterministic automaton (ICFA) obtained by reversing the edges
       of a deterministic automaton (IDFA). Complexity O(e)
       on an IDFA with e edges.








main
public static void main(java.lang.String[] args)
                 throws java.lang.Exception



Throws:
java.lang.Exception





ecoQuotient
public void ecoQuotient(int[] c)








isTerminal
public boolean isTerminal(int p)








addTerminal
public void addTerminal(int p)








quotient
public IDFA quotient(int[] c)








quotient
public IDFA quotient(Partition part)








toString
public java.lang.String toString()








show
public void show(java.lang.String nom)








ex
public static IDFA ex()








fromFile
public static IDFA fromFile(java.lang.String name)
                     throws java.io.IOException,
                            java.lang.Exception



Throws:
java.io.IOException
java.lang.Exception














 
  
            Package 
    Class 
      Tree 
      Deprecated 
      Index 
      Help 
  









 PREV CLASS 
 NEXT CLASS

  FRAMES   
 NO FRAMES   
 






  SUMMARY: NESTED | FIELD | CONSTR | METHOD

DETAIL: FIELD | CONSTR | METHOD