Class EcoRMinimizer

java.lang.Object
  extended byEcoRMinimizer

public class EcoRMinimizer
extends java.lang.Object

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

Revuz algorithm. A weak version (not of the right complexity concerning the alphabet) but less demanding on memory space.


Constructor Summary
EcoRMinimizer()
           
 
Method Summary
static 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.
static 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.
static void computeSignatures(int[] som, int[][] sig, int[] num, IntQueue shl, IDFA a)
          Computes the array of signatures of a list shl of states.
static boolean equalsig(int[] a, int[] b)
          Returns true if the arrays a and b are equal.
static IntQueue[] letterPositions(IntQueue[] pdl, int J, int K)
          Returns the array of lists of letters at a position.
static IDFA minimize(IDFA a)
          The method called to minimize an acyclic trim automaton.
static IntQueue[] positionLetters(int[][] s, int J)
          Returns the array list of positions of letters.
static IntQueue radixSort(int[][] s, int J)
          Lexicographic sort of the array s.
static int renumberStates(int[] e, int[][] sil, int nn, int[] num, IDFA a, IDFA b)
          Adds states to the minimal automaton in construction b.
static 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
 

Constructor Detail

EcoRMinimizer

public EcoRMinimizer()
Method Detail

radixSort

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

Parameters:
s - a K by N array.

bucketSort

public static 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 static IntQueue[] positionLetters(int[][] s,
                                         int J)
Returns the array list of positions of letters.

Parameters:
s - the array of signatures.
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 static 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 static 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 static 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 static 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 static boolean equalsig(int[] a,
                               int[] b)
Returns true if the arrays a and b are equal.


triParHauteur

public static 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 static IDFA minimize(IDFA a)
The method called to minimize an acyclic trim automaton.