Class EcoRMinimizer

java.lang.Object
  EcoRMinimizer

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

• n = number of states
• e = number of edges.

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.