A B C D E F G H I L M N Q R S T V W X Y

A

a - Variable in class DPTable

The currently remembered characters from the top input string.

addSuccessors(State, int) - Method in class StateTable

Find all states that can be reached from this state by reading a single minimal match pair of the form T_c,pad, for -h<pad<h, and write the transitions to the file.

aLen - Variable in class DPTable

The length of the input string remembered in a; note that aLen is less than the size of the array a.

appendPair(int, int) - Method in class DPTable

Append the minimal match pair T_c,l to the strings a and b, and update the lcs table; see the overview of the code for the definition of T_c,l.

B

b - Variable in class DPTable

The currently remembered characters from the bottom input string.

bLen - Variable in class DPTable

The length of the input string remembered in b

build(int) - Method in class StateTable

Build the state table for history h, and write it to the file.

C

computeEntryFromRecurrence(int, int) - Method in class DPTable

Compute the entry lcs[i][j] based on the values in a[i], b[j], lcs[i-1][j-1], lcs[i-1][j], and lcs[i][j-1].

D

DATADIRECTORY - Static variable in class StateTable

The path to the directory in which the transition table is to be stored.

decodeHorzDiffs(int, int, int) - Method in class DPTable

Decode a bitstring into horizontal differences in a table.

decodeString(int, int[]) - Method in class DPTable

Interpreting x as an h-bit integer, place the successive bits into a[1],a[2],...,a[h].

decodeVertDiffs(int, int, int) - Method in class DPTable

Decode a bitstring into vertical differences in a table.

dequeue() - Method in class StateTable

Remove and return the next element from the queue.

DPTable - Class in <Unnamed>

Class DPTable maintains a representation of the state of a dynamic programming table for the lcs problem.

DPTable(State) - Constructor for class DPTable

Decode the four integers comprising State s into a table.

dumpEigen(double) - Method in class GenFn

Dump the current approximation to the eigenvector to the file eigen<h>.bin.

dx - Variable in class State

The encoding of the last h differences in the last column of the limited-history lcs table.

dy - Variable in class State

The encoding of the last h differences in the last row of the limited-history lcs table.

E

encode() - Method in class DPTable

Encode the last h entries in strings a and b, and the last h vertical and horizontal differences in lcs, into a State four-tuple.

encodeHorzDiffs(int, int) - Method in class DPTable

Encode horizontal differences from the table into a short.

encodeVertDiffs(int, int) - Method in class DPTable

Encode vertical differences from the table into a short.

enqueue(StateTable.Element) - Method in class StateTable

Append e to the queue.

equals(State) - Method in class State

Test whether all four components of this state are equal to the corresponding components of state t.

error(String) - Static method in class DPTable

Print an error message and terminate.

F

findOrAdd(State) - Method in class StateTable

Search for state s; if not found insert into the hash table and append it to the queue; in any case return its state number.

G

GenFn - Class in <Unnamed>

Class GenFn computes approximations to a function λ(z) to be used in Theorem 3.3, for a specified transition function file, and then computes the corresponding bounds on γ.

GenFn(String) - Constructor for class GenFn

Initialize the structure to compute λ values corresponding to the transition function represented in file filename.

H

h - Variable in class DPTable

The value of the history parameter

h - Variable in class GenFn

The history length.

h - Static variable in class State

The history length.

h - Variable in class StateTable

The value of the history parameter.

hashLink - Variable in class StateTable.Element

The next node in the hash chain.

hashTable - Variable in class StateTable

A hash table of states.

hashTableSize - Static variable in class StateTable

The number of slots in the hash table.

hashValue() - Method in class State

Return a hash value for this state.

I

isCanonical() - Method in class DPTable

Return true if backtracking canonically from lcs[aLen][bLen] leads to lcs[h][h].

iterate() - Method in class GenFn

Carry out one iteration: multiply A_z and v, and rescale.

L

lambda(double) - Method in class GenFn

Compute a numerical approximation to the λ(z) in Theorem 3.3, using the machine encoded in the file filename.

lcs - Variable in class DPTable

The currently remembered portion of the lcs table.

logbase(double, double, double, int) - Static method in class GenFn

Compute and print an integer value p such that log_bx≤p/denom, attempting to make p as small as possible so that the round-off error verification described in Section 3.2.2 can be performed.

M

main(String[]) - Static method in class DPTable

Perform some tests of the methods.

main(String[]) - Static method in class GenFn

The main program is used with the command
GenFn <filename> <z0> <z1> <zdelta>
For each z in the range z0 to z1, with a step size of zdelta, it computes lambda(z) and the resulting upper bound on γ, using the transition function stored in ./data/filename.

main(String[]) - Static method in class State

Set the verbose flags to true and then perform several tests.

main(String[]) - Static method in class StateTable

Build and write out the table of transitions and states.

maxRatio - Variable in class GenFn

The maximum ratio by which any component of v increases this iteration.

minRatio - Variable in class GenFn

The minimum ratio by which any component of v increases this iteration.

N

number - Variable in class StateTable.Element

The number assigned to this state.

numberOfAcceptingStates - Variable in class GenFn

The number of states, not including the rejecting state

numberOfAcceptingStates - Variable in class StateTable

The number of distinct reachable accepting states found so far.

Q

queueHead - Variable in class StateTable

The head of the queue.

queueLink - Variable in class StateTable.Element

The next node in the queue.

queueTail - Variable in class StateTable

The tail of the queue.

R

REDUCE - Static variable in class State

Control whether the reduction based on the symmetry between <x,y,dx,dy> and <complement(x),complement(y),dx,dy> is used.

reduce() - Method in class State

Reduce this state to a canonical form for the equivalence between <x,y,dx,dy> and <complement(x),complement(y),dx,dy>

S

show() - Method in class DPTable

Display the current contents of a, b, and the lcs table.

sortedStates - Variable in class StateTable

A call to sortStates will set this to an array containing state number i in sortedStates[i]; position 0 in the array is unused.

sortStates() - Method in class StateTable

Set sortedStates to an array in which the element indexed by i is state number i; the 0th array position is unused.

State - Class in <Unnamed>

Instances of class State hold the four (short) integers x,y,dx,dy representing a state of the automaton described in Section 3.2.

State() - Constructor for class State

Create a new uninitialized state.

State(int, int, int, int) - Constructor for class State

Create a new state and initialize its components from the parameters.

state - Variable in class StateTable.Element

The state represent by this node.

StateTable - Class in <Unnamed>

Class StateTable gives a representation of the set of reachable states with a given history length.

StateTable() - Constructor for class StateTable

Create and initialize a new StateTable class.

StateTable.Element - Class in <Unnamed>

Class Element represents a node in a linked list of states; two links are provided, queueLink and hashLink, so that the node can be used both in the representation of the BFS queue and in the representation of a chain in the hash table.

StateTable.Element(State) - Constructor for class StateTable.Element

Create a new node containing (non-null) state s.

suffix(int[], int) - Method in class DPTable

Return the integer represented in binary by the sequence of bits a[aLen-h+1],a[aLen-h+2],...,a[aLen].

T

TOLERANCE - Static variable in class GenFn

The factor controlling how close the ratios between elements of two successive vectors must be before we stop iterating.

toString() - Method in class State

Produce a string representing this state (in hexadecimal).

transition(int, int) - Method in class State

Return the new state resulting from this state upon reading a minimal match pair.

V

v - Variable in class GenFn

The last approximation to an eigenvector of A_z; see Section 3.1 in the paper.

verbose - Static variable in class DPTable

Set this value to true to obtain verbose output

verbose - Static variable in class State

Control whether verbose output is produced.

verbose - Static variable in class StateTable

Set this to true for verbose output.

verbosity - Static variable in class GenFn

This controls the level of output.

vNew - Variable in class GenFn

The next approximation to an eigenvector of A_z.

W

wmuz - Variable in class GenFn

wmuz is computed in method lambda by wmuz[h+i] = w_μ,z(T_c,i), where w_μ,z is as defined in Section 3.1, and μ and T_c,i are as defined in the overview of the code.

X

x - Variable in class State

The encoding of the last h bits of the upper input string.

Y

y - Variable in class State

The encoding of the last h bits of the lower input string.

A B C D E F G H I L M N Q R S T V W X Y