Class RMinimizer

java.lang.Object
  extended byRMinimizer
All Implemented Interfaces:
Minimizer

public class RMinimizer
extends java.lang.Object
implements Minimizer

Minimization of an acyclic trim automaton in linear time. This algorithm, due to D. Revuz, minimizes an acyclic automaton in time O(q + n + e), where

Revuz algorithm.


Field Summary
static int[] g2l
          An array used for conversion from global to local of names in signatures.
static int[] l2g
          An array used for conversion from local to global of names in signatures.
static boolean verbose
           
 
Constructor Summary
RMinimizer()
           
 
Method Summary
 int addStateMin(int p, int nn, int[] num, IDFA a, IDFA b)
          Adds the state nn to the automaton b (the minimal automaton in construction) as the class of state p in the original automaton a.
 IntQueue bucketSort(int k, IntQueue[] bucket, IntQueue[] lap, int[][] s, IntQueue d)
          Realizes the bucket sort of the queue of integers d according to the value of column k in the array of signatures s.
 void computeSignatures(int[] som, int[][] sig, int[] num, IntQueue shl, IDFA a)
          Computes the array of signatures of a list shl of states.
 boolean equalsig(int[] a, int[] b)
          Returns true if the arrays a and b are equal.
 int g2l(int[][] sig, int[][] sil)
          Transforms the global arry of signatures into a local one.
 IntQueue[] letterPositions(IntQueue[] pdl, int J, int K)
          Returns the array of lists of letters at a position.
 DFA minimize(DFA a)
           
 DFT minimize(DFT a)
           
 IDFA minimize(IDFA a)
          The method called to minimize an acyclic trim automaton.
 IntQueue[] positionLetters(int[][] s, int J)
          Returns the array list of positions of letters.
 IntQueue radixSort(int[][] s, int J)
          Lexicographic sort of the array s.
 int renumberStates(int[] e, int[][] sil, int nn, int[] num, IDFA a, IDFA b)
          Adds states to the minimal automaton in construction b.
 void resetg2l(int J)
          Reinitializes the arrays g2l and l2g
 IntQueue[] triParHauteur(int[] h, IDFA a)
          Returns the array sh of queues such that sh[r] is the queue of states at heigth r.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

verbose

public static boolean verbose

g2l

public static int[] g2l
An array used for conversion from global to local of names in signatures.


l2g

public static int[] l2g
An array used for conversion from local to global of names in signatures.

Constructor Detail

RMinimizer

public RMinimizer()
Method Detail

g2l

public int g2l(int[][] sig,
               int[][] sil)
Transforms the global arry of signatures into a local one.

Parameters:
sig - the global array of signatures of size N by K>/code>.
sil - the local array of signatures.
Returns:
the number of distinct letters appearing.

resetg2l

public void resetg2l(int J)
Reinitializes the arrays g2l and l2g


radixSort

public IntQueue radixSort(int[][] s,
                          int J)
Lexicographic sort of the array s. Complexity O(NK).

Parameters:
J - the number of letters appearing (they run from 0 to J - 1). We have J <= N K.
s - a K by N array.

bucketSort

public IntQueue bucketSort(int k,
                           IntQueue[] bucket,
                           IntQueue[] lap,
                           int[][] s,
                           IntQueue d)
Realizes the bucket sort of the queue of integers d according to the value of column k in the array of signatures s.

Parameters:
k - the column index
bucket - the array of buckets
lap - the array of lists of letters by position
s - the array of signatures
d - the list to be sorted
Returns:
the sorted list.

positionLetters

public IntQueue[] positionLetters(int[][] s,
                                  int J)
Returns the array list of positions of letters.

Parameters:
s - the array of signatures.
J - the size of the returned array.
Returns:
the array pdl of lists of positions of letters. pdl[c] is the list of indices k such that s[n][k] = c for some index n.

letterPositions

public IntQueue[] letterPositions(IntQueue[] pdl,
                                  int J,
                                  int K)
Returns the array of lists of letters at a position.

Parameters:
pdl - the array of lists of positions of letters.
J - the size of pdl.
K - the size of the result.
Returns:
the array lap of lists of letters at a position. lap[k] is the list of letters c such that s[n][k] = c for some index n.

addStateMin

public int addStateMin(int p,
                       int nn,
                       int[] num,
                       IDFA a,
                       IDFA b)
Adds the state nn to the automaton b (the minimal automaton in construction) as the class of state p in the original automaton a.

Parameters:
p - a state of a.
nn - a state of b
num - the array of class numbers
Returns:
nn + 1.

renumberStates

public int renumberStates(int[] e,
                          int[][] sil,
                          int nn,
                          int[] num,
                          IDFA a,
                          IDFA b)
Adds states to the minimal automaton in construction b.

Parameters:
e - the array of states of a
sil - the array of signatures
nn - the current number of states of b
num - the array of class numbers
Returns:
the current number of states of b.

computeSignatures

public void computeSignatures(int[] som,
                              int[][] sig,
                              int[] num,
                              IntQueue shl,
                              IDFA a)
Computes the array of signatures of a list shl of states.

Parameters:
som - the array of names of states. som[i] is the name of the i-th state.
sig - the array of signatures.
num - the array of class numbers
shl - the list of states

equalsig

public boolean equalsig(int[] a,
                        int[] b)
Returns true if the arrays a and b are equal.


triParHauteur

public IntQueue[] triParHauteur(int[] h,
                                IDFA a)
Returns the array sh of queues such that sh[r] is the queue of states at heigth r.

Parameters:
h - the array of heigths
Returns:
the array of lists of states at given heigth.

minimize

public IDFA minimize(IDFA a)
              throws java.lang.Exception
The method called to minimize an acyclic trim automaton.

Specified by:
minimize in interface Minimizer
Throws:
java.lang.Exception

minimize

public DFA minimize(DFA a)
             throws java.lang.Exception
Specified by:
minimize in interface Minimizer
Throws:
java.lang.Exception

minimize

public DFT minimize(DFT a)
             throws java.lang.Exception
Specified by:
minimize in interface Minimizer
Throws:
java.lang.Exception