Class RMinimizer

java.lang.Object
  RMinimizer

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

• q = size of alphabet
• n = number of states
• e = number of edges.

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