A B C D E F G H I L M N O P Q R S T V W Z

A

Alphabet - class Alphabet.
This class implements the alphabet.
Alphabet(char, int) - Constructor for class Alphabet
Creates an alphabet of size n beginning at character letter
Alphabet(boolean[]) - Constructor for class Alphabet
Creates an alphabet from a boolean array isLetter
Alphabet(int) - Constructor for class Alphabet
Creates an alphabet of size n beginning at character a.
Alphabet(Set) - Constructor for class Alphabet
Creates an alphabet consisting in a set of characters.
Alphabet(char[]) - Constructor for class Alphabet
Creates an alphabet consisting in a set given in an array of characters.
add(String, Hashtable) - Static method in class Element
Adds an entry to the Hashtable updating the frequency if the element is already present.
add(char) - Method in class ForaxTrie
Returns the son labeled c if there is one and creates it otherwise.
add(int) - Method in class IntQueue
Adds the integer val to the queue.
add(IntList) - Method in class IntQueue
Adds the list l at the rear of the queue.
add(int, int) - Method in class PairIntQueue
Adds the pair (val, elem) to the queue.
add(PairIntList) - Method in class PairIntQueue
Adds the head of the list l to the queue.
add(char) - Method in class VariableArrayTrie
Adds an entry in the next array to allow a transition by c.
addEdge(int, char, int) - Method in class ICFA
 
addEdge(int, int, int) - Method in class ICFA
 
addEdge(int, char, int) - Method in class IDFA
Adds to the automaton an edge from p to q labeled a if it does not exist already.
addEdge(int, int, int) - Method in class IDFA
Adds to the automaton an edge from p to q labeled alphabet.toChar(a) if it does not exist already.
addEdge(int, char, int) - Method in class INFA
 
addEdge(int, int, int) - Method in class INFA
 
addEdgeFast(int, int, int) - Method in class ICFA
 
addEdgeFast(int, char, int) - Method in class IDFA
Adds to the automaton an edge from p to q labeled a.
addEdgeFast(int, int, int) - Method in class IDFA
Adds to the automaton an edge from p to q labeled alphabet.toChar(a).
addFast(int, int) - Method in class PairIntQueue
 
addStateMin(int, int, int[], IDFA, IDFA) - Static method in class EcoRMinimizer
Adds the state nn to the automaton b (the minimal automaton in construction) as the class of state p in the original automaton a.
addStateMin(int, int, int[], IDFA, IDFA) - Method in class RMinimizer
Adds the state nn to the automaton b (the minimal automaton in construction) as the class of state p in the original automaton a.
addTerminal(int) - Method in class IDFA
 
addTerminal(int) - Method in class INFA
 
addToCharSet(String, boolean[]) - Static method in class Alphabet
 
addToTrie(String) - Method in class FixedArrayTrie
Adds the word s to the trie.
addToTrie(String) - Method in class ForaxTrie
Adds the word s to the trie.
addToTrie(String) - Method in interface Trie
Adds the word s to the trie.
addToTrie(String) - Method in class VariableArrayTrie
Adds the word s to the trie.
addToTrieBis(String) - Method in class VariableArrayTrie
A variant of addToTrie().
addToTrieTer(String) - Method in class VariableArrayTrie
A variant of addToTrie().
addWord(String) - Method in class IDFA
Adds a word to the set recognized by an IDFA.
advance() - Method in class LL
Advance one character to the right on input.
advance() - Method in class SLR
Advance one character to the right on input.
advance() - Method in class ThompsonCompiler
Implements the function Advance() of Section 1.6.1.
alphabet - Static variable in class FixedArrayTrie
The alphabet used to form the strings composing the trie.
alphabet - Variable in class Grammar
The total alphabet.
alphabet - Variable in class ICFA
The alphabet.
alphabet - Variable in class IDFA
The alphabet.
alphabet - Variable in class INFA
The alphabet.
alphabet - Variable in class LL
The input alphabet;
alphabet - Variable in class SLR
The input alphabet;
append(IntQueue) - Method in class IntQueue
Concatenates the current queue and the queue s.
approximateEigenvector(NonNegativeVector, float) - Method in class NonNegativeMatrix
Returns a vector y such that My >= ra y iterating the transformation y = (1 / r(y)) M y starting with y = x with r(y) = min((My)_i / y_i) the Wielandt function.
automataProduct(LinkedNFA, LinkedNFA) - Static method in class LinkedNFA
Implements the function AutomataProduct().
automataUnion(LinkedNFA, LinkedNFA) - Static method in class LinkedNFA
Implements the function AutomataUnion().
automatonStar(LinkedNFA) - Static method in class LinkedNFA
Implements the function NFAStar().

B

BMinimizer - class BMinimizer.
This class implements the minimization of deterministic finite automata by double reverse (Brzozowski's algorithm).
BMinimizer() - Constructor for class BMinimizer
 
Buffer - class Buffer.
This class implements operations on k-tuples needed for the computation of the entropy of a text.
Buffer(Reader, int) - Constructor for class Buffer
Initializes a buffer composed of the k first characters of a text.
border(String) - Static method in class ElementaryAlgorithms
Implements the algorithm Border(x) of Section 1.2.2.
borderSharp(String) - Static method in class ElementaryAlgorithms
Implements the algorithm BorderSharp(x) of Problem 1.2.1.
bucketSort(int, IntQueue[], IntQueue[], int[][], IntQueue) - Static method in class EcoRMinimizer
Realizes the bucket sort of the queue of integers d according to the value of column k in the array of signatures s.
bucketSort(int, IntQueue[], IntQueue[], int[][], IntQueue) - Method in class RMinimizer
Realizes the bucket sort of the queue of integers d according to the value of column k in the array of signatures s.

C

CompileExpression - class CompileExpression.
Compiles a regular expression into a finite automaton by one of the possible methods implementing the interface ExpressionCompiler Usage: java CompileExpression Method Option expression The only method presently available is T (Thomson's algorithm using ThompsonCompiler).
CompileExpression() - Constructor for class CompileExpression
 
cancel() - Method in class LL
Cancels the current character with the top of stack.
circularMin(String) - Static method in class ElementaryAlgorithms
Implements the algorithm CircularMin() of Section 1.2.5.
circularRightShift() - Static method in class NFT
The circular right shift.
clone() - Method in class Partition
 
closure(HalfEdge, boolean[]) - Method in class NFA
Returns the set of states which can be reached from p by an epsilon path.
closure(Set) - Method in class NFA
Implements the closure of the set of states s.
closure(HalfEdge, boolean[]) - Method in class NFT
Returns the list of binary half-edges of the form p followed by a path with input epsilon.
closure(Set) - Method in class NFT
idem from the half edges of the set s
compareTo(Object) - Method in class HalfEdge
Overrides the method Object.compareTo.
compose(DFT, DFT) - Static method in class DFT
Returns the composition of the DFT a and b.
compose(NFT, NFT) - Static method in class NFT
Returns the composition of the NFT s and t, which are supposed to be literal.
computeSignatures(int[], int[][], int[], IntQueue, IDFA) - Static method in class EcoRMinimizer
Computes the array of signatures of a list shl of states.
computeSignatures(int[], int[][], int[], IntQueue, IDFA) - Method in class RMinimizer
Computes the array of signatures of a list shl of states.
concat(IntQueue) - Method in class IntQueue
A variant of append().
convert(Alphabet, short) - Method in class Alphabet
Converts the short integer i to its value in the alphabet a.
copy(int, IDFA) - Method in class VariableArrayTrie
 
copy(int, DFA) - Method in class VariableArrayTrie
 
copybis(IDFA) - Method in class VariableArrayTrie
 
copybis(DFA) - Method in class VariableArrayTrie
 
count(Hashtable, float[]) - Static method in class Element
Returns in s the frequencies of the words appearing in the table table.
count(LinkedList, int) - Method in class NFA
Returns the number of states of the result of the determinization algorithm without constructing the automaton.
current() - Method in class LL
Returns the current token of the input.
current() - Method in class SLR
Returns the current token of the input.
current() - Method in class ThompsonCompiler
Implements the function Current() of Section 1.6.1.

D

DFA - class DFA.
This class implements deterministic complete finite automata.
DFA(int, int) - Constructor for class DFA
creates a DFA with n states and k letters.
DFA(int, Alphabet) - Constructor for class DFA
creates a DFA with n states and alphabet a.
DFT - class DFT.
This class implements sequential (or deterministic) finite-state transducers.
DFT(int, int) - Constructor for class DFT
creates a DFT with n states and k letters.
DFT(int, Alphabet) - Constructor for class DFT
creates a DFT with n states and alphabet a.
DListInt - class DListInt.
Doubly linked lists of integers.
DListInt(int) - Constructor for class DListInt
Creates a cell containing p.
DListInt(int, DListInt) - Constructor for class DListInt
Inserts p in front.
Dyck() - Static method in class Grammar
The Dyck grammar:
S -> (S)S | "".
derive - Variable in class Grammar
The set of rules with given left symbol.
dominantEigenvalue(NonNegativeVector, float) - Method in class NonNegativeMatrix
Returns an approximate value of rho_M, the maximal eigenvalue of the matrix M.

E

ETF() - Static method in class Grammar
The ETF grammar :
E -> E + T
T -> T * F
F -> (E) | char .
ETFPrime() - Static method in class Grammar
The modified version of the ETF grammar which is LL(1) :
E -> Te
e -> +Te | ""
T -> Ft
t -> *Ft | ""
F -> (E) | char .
EcoRMinimizer - class EcoRMinimizer.
Minimization of an acyclic trim automaton in linear time.
EcoRMinimizer() - Constructor for class EcoRMinimizer
 
Element - class Element.
This class implements operations on the hashtable of kuples of a text as a preparation to the computation of its entropy.
Element(String, float) - Constructor for class Element
Creates an Element composed of a string and a float (its frequency).
ElementaryAlgorithms - class ElementaryAlgorithms.
This class implements the elementary algorithms on words of Section 1.2.
ElementaryAlgorithms() - Constructor for class ElementaryAlgorithms
 
Entropy - class Entropy.
Computation of the order k entropy of a text.
Entropy() - Constructor for class Entropy
 
ExpressionCompiler - interface ExpressionCompiler.
The interface to classes that compile a rational expression into an automaton (of class NFA)
ecoMinimize() - Method in class IDFA
Minimization in linear time using Revuz algorithm.
ecoQuotient(int[]) - Method in class IDFA
 
edges - Variable in class ICFA
The set of edges going out of a state.
edges - Variable in class IDFA
The set of edges going out of a state.
edges - Variable in class INFA
The set of edges going out of a state.
endOfInput() - Method in class LL
True if the input has been read completely.
english() - Static method in class Alphabet
The english alphabet.
entropy(int, float[], int) - Static method in class Entropy
Returns -(1/k)Sigma s[i]log(s[i]).
enum(int) - Method in class VariableArrayTrie
Numbers the nodes of a trie through an initilization of the field num.
enumerate(boolean[]) - Method in class IDFA
A call to enumerate(isOn) returns the number of states of the trimmed automaton.
epsilon - Variable in class Grammar
The erasable symbols.
epsilon() - Method in class Grammar
Implements Epsilon().
epsilon() - Static method in class NFT
An NFT realizing \e \times a^*.
equals(Object) - Method in class HalfEdge
Overrides the method Object.hashCode.
equals(IntList) - Method in class IntList
 
equalsig(int[], int[]) - Static method in class EcoRMinimizer
Returns true if the arrays a and b are equal.
equalsig(int[], int[]) - Method in class RMinimizer
Returns true if the arrays a and b are equal.
equiv(IDFA, int, int) - Static method in class FMinimizer
 
equiv(DFA, int, int, int[]) - Method in class NMinimizer
Tests whether two states p,q are equivalent in the sense that p=q mod c and p.a=q.a mod c for every letter a .
equiv(IDFA, int, int, int[]) - Method in class NMinimizer
 
equiv(DFA, int, int, int[]) - Method in class NbisMinimizer
Tests whether two states p,q are equivalent in the sense that p=q mod c and p.a=q.a mod c for every letter a .
equiv(IDFA, int, int, int[]) - Method in class NbisMinimizer
 
evalExp() - Method in class ThompsonCompiler
Implements the function EvalExp() of Section 1.6.1.
evalFact() - Method in class ThompsonCompiler
Implements the function EvalFact() of Section 1.6.1.
evalTerm() - Method in class ThompsonCompiler
Implements the function EvalTerm() of Section 1.6.1.
ex() - Static method in class ICFA
 
ex() - Static method in class IDFA
 
ex() - Static method in class INFA
 
explore(LinkedList, int, IDFA) - Method in class ICFA
Implements the function Explore(t, s, b) of Section 1.3.3 which returns the list of sets of half edges realizing the determinization of the NFA.
explore(int, int[]) - Method in class IDFA
A classical depth-first search.
explore(LinkedList, int, IDFA) - Method in class INFA
Implements the function Explore(t, s, b) which returns the list of sets of half edges realizing the determinization of the NFA.
explore(LinkedList, int, DFA) - Method in class NFA
Implements the function Explore(t, s, b) of Section 1.3.3 which returns the list of sets of half edges realizing the determinization of the NFA.
explore(LinkedList, int, DFT) - Method in class NFT
Implements the function Explore(t, s, b) which returns the list of sets of half edges realizing the determinization of the NFT.
explore2(HashMap, Set, int, IDFA) - Method in class ICFA
The same as explore but with an implementation of the set of states of the resulting DFA via a HashMap.
explore2(HashMap, Set, int, DFA) - Method in class NFA
The same as explore but with an implementation of the set of states of the resulting DFA via a HashMap.
exploreBis(LinkedList, Set, int, IDFA) - Method in class ICFA
The same as explore but with a transmission of the index of the set s in the list t.
exploreFirstChild(short, boolean[]) - Method in class Grammar
Explores the graph of First.
exploreSibling(short, boolean[]) - Method in class Grammar
Explores the graph of Follow().
expression - Variable in class LL
The expression to analyze.
expression - Variable in class SLR
The expression to analyze.

F

FMinimizer - class FMinimizer.
 
FMinimizer() - Constructor for class FMinimizer
 
FixedArrayTrie - class FixedArrayTrie.
An implementation of tries with linked lists.
FixedArrayTrie() - Constructor for class FixedArrayTrie
 
ForaxTrie - class ForaxTrie.
Implements Tries with ordered lists of sons for each node.
fibonacci() - Static method in class NFT
The literal NFT realizing the Fibonacci morphism a->ab, b->a.
first(short[]) - Method in class Grammar
Extends the function First() to Strings.
firstChild(short) - Method in class Grammar
Implements the fuction FirstChild().
follow(short) - Method in class Grammar
Implements the function Follow().
french() - Static method in class Alphabet
The french alphabet.
fromExpression(String) - Static method in class Alphabet
Returns the alphabet composed of the letters appearing in the expression exp (used to create an alphabet from a regular expression).
fromFile(String) - Static method in class Alphabet
Returns the alphabet composed of all the characters appearing in the file name.
fromFile(String) - Method in class FixedArrayTrie
Builds a trie representing the list of strings read from a file line by line.
fromFile(String) - Method in class ForaxTrie
Builds a trie representing the list of strings read from a file line by line.
fromFile(String) - Static method in class Grammar
 
fromFile(String) - Static method in class IDFA
 
fromFile(String) - Method in interface Trie
Builds a trie representing the list of strings read from a file line by line.
fromFile(String) - Method in class VariableArrayTrie
Builds a trie representing the list of strings read from a file line by line.
fromFile(String) - Static method in class ZLdecode
 
fromFile(String) - Static method in class ZLencode
 
fromFileBis(String) - Method in class VariableArrayTrie
Builds a trie representing the list of the reverse of strings read from a file line by line.
fusion(IDFA) - Static method in class FMinimizer
Returns the smallest partition pi of states such that pi < t
fusionRandom(IDFA) - Static method in class FMinimizer
 

G

G - Variable in class LL
The current context-free grammar.
G - Variable in class SLR
The current context-free grammar.
Grammar - class Grammar.
This class implements context-free grammars.
Grammar(int) - Constructor for class Grammar
Creates a grammar with n symbols.
g2l - Static variable in class RMinimizer
An array used for conversion from global to local of names in signatures.
g2l(int[][], int[][]) - Method in class RMinimizer
Transforms the global arry of signatures into a local one.
getFirst() - Method in class PairIntList
Returns the first element of the first pair.
getSecond() - Method in class PairIntList
Returns the second element of the first pair.
golden() - Static method in class NonNegativeMatrix
The classical 2 by 2 matrix of the golden mean system.

H

HalfEdge - class HalfEdge.
This class implements half-edges which are either unary, i.e. a state or binary, i.e. a pair formed by a word and a state or ternary, i.e. triples of two words (input and output) and a state.
HalfEdge(int) - Constructor for class HalfEdge
Creates a unary half-edge.
HalfEdge(String, int) - Constructor for class HalfEdge
Creates a binary half-edge.
HalfEdge(String, String, int) - Constructor for class HalfEdge
Creates a ternary half-egde.
HopcroftMinimizer - class HopcroftMinimizer.
A class implementing Hopcroft's minimization algorithm to minimize a DFA.
HopcroftMinimizer() - Constructor for class HopcroftMinimizer
 
hashCode() - Method in class HalfEdge
Overrides the method Object.hashCode.
head - Variable in class Buffer
The last character of word.
head() - Method in class PairIntList
Returns the first element of the list.
heigths() - Method in class IDFA
Returns the array of heigths.
heigthsRecursive(int, int[]) - Method in class IDFA
A recursive method to compute the array of heigths from a state p.

I

ICFA - class ICFA.
This class implements incomplete codeterministic finite automata (ICFA).
ICFA() - Constructor for class ICFA
 
ICFA(int) - Constructor for class ICFA
 
ICFA(int, Alphabet) - Constructor for class ICFA
 
IDFA - class IDFA.
This class implements incomplete deterministic automata.
IDFA() - Constructor for class IDFA
 
IDFA(int) - Constructor for class IDFA
 
IDFA(int, Alphabet) - Constructor for class IDFA
 
IDFA(int, int) - Constructor for class IDFA
 
IDFA(IDFA) - Constructor for class IDFA
 
INFA - class INFA.
This class implements incomplete nondeterministic finite automata (without epsilon transitions).
INFA() - Constructor for class INFA
 
INFA(int) - Constructor for class INFA
 
INFA(int, Alphabet) - Constructor for class INFA
 
InfoDFA - class InfoDFA.
An extension of the class DFA allowing to store an information in a state as an integer and to identify a state as being the sink (used for LR analysis).
InfoDFA(int, Alphabet) - Constructor for class InfoDFA
 
InfoNFA - class InfoNFA.
An extension of the class NFA in which the states carry an information which is an integer (used for LR analysis)..
InfoNFA(int) - Constructor for class InfoNFA
 
InfoNFA(int, Alphabet) - Constructor for class InfoNFA
Creates an NFA with n states on the alphabet a.
IntList - class IntList.
This class implements linked lists of integers.
IntQueue - class IntQueue.
This class implements queues of integers as linked lists from the class IntList.
IntQueue() - Constructor for class IntQueue
 
index(char) - Method in class VariableArrayTrie
Returns the index of a node with label c if there is one and -1 otherwise.
info - Variable in class InfoNFA
 
init(Reader, int, int, float[]) - Static method in class Entropy
 
init(String[]) - Static method in class ZLdecode
Initializes the dictionnary.
initAlphabet() - Method in class Grammar
Initializes alphabet, variables and terminals.
initClass() - Method in class DFT
 
initGrammar() - Method in class Grammar
Computes derive, alphabet and epsilon.
initPartition() - Method in class DFT
 
initial - Variable in class Grammar
The initial production.
initial - Variable in class ICFA
The initial set of states.
initial - Variable in class IDFA
The initial state.
initial - Variable in class INFA
The set of initial states.
insert(DListInt) - Method in class DListInt
Inserts the cell head in front of the list.
intersection(int[], String[]) - Static method in class DFT
returns the partition intersection of table and label.
intersection(int[], int[]) - Static method in class DFT
Returns the partition intersection of table1 and table2.
isAcyclic() - Method in class IDFA
True if the automaton is a DAWG, i.e. if the graph of the automaton is acyclic.
isEmpty() - Method in class IntQueue
Returns true if the queue is empty.
isEmpty() - Method in class PairIntQueue
Returns true if the queue is empty, which means that front is null
isIn(char) - Method in class Alphabet
Returns true if the character c is in the alphabet.
isIn(int, int) - Method in class PairIntQueue
Returns true if the pair (val, elem) is in the queue.
isInTrie(String) - Method in class FixedArrayTrie
Returns true if the trie contains s.
isInTrie(String) - Method in class ForaxTrie
Returns true if the trie contains s.
isInTrie(String) - Method in interface Trie
Returns true if the trie contains s.
isInTrie(String) - Method in class VariableArrayTrie
Implements the function IsInTrie() of Section 1.3.1.
isLeaf() - Method in class FixedArrayTrie
Returns true if the node p is a leaf of the trie.
isLeaf() - Method in class ForaxTrie
Returns true if the node p is a leaf of the trie.
isLeaf() - Method in interface Trie
Returns true if the node p is a leaf of the trie.
isLeaf() - Method in class VariableArrayTrie
Returns true if the node p is a leaf of the trie.
isOnPath(int, boolean[]) - Method in class IDFA
Tests wheter the states are on a successful path of the automaton.
isSubword(String, String) - Static method in class ElementaryAlgorithms
Implements the algorithm IsSubword() of Section 1.2.4.
isTerminal(int) - Method in class IDFA
 
isTerminal(int) - Method in class INFA
 

L

LL - class LL.
Implements the LL(1) top-down analysis.
LL(String, Grammar) - Constructor for class LL
Creates the LLTable and initializes the stack.
LLTable() - Method in class LL
The LL(1) table analysis.
LRAutomaton() - Method in class SLR
Computes the LR(0) automaton.
LRReduceTable - Variable in class SLR
 
LRReduceTable(InfoDFA) - Method in class SLR
 
LRShiftTable - Variable in class SLR
The shift table.
LRShiftTable(InfoDFA) - Method in class SLR
Computes the SLR(0) shift table.
LinkedNFA - class LinkedNFA.
Implementation of Thomson's algorithm to perform the operations of union, product and star on automata.
LinkedNFA() - Constructor for class LinkedNFA
Creates a one-state NFA recognizing epsilon.
LinkedNFA(char) - Constructor for class LinkedNFA
Implements BuildAutomaton(a).
LinkedNFA(State, State) - Constructor for class LinkedNFA
Implements NewAutomaton(i,t).
LmaxOutput() - Method in class NFT
The maximal length of outputs in an NFT.
l2g - Static variable in class RMinimizer
An array used for conversion from local to global of names in signatures.
lLParse() - Method in class LL
Parses the input expression using the LL(1) analysis alpgorithm.
label - Variable in class State
The Label of the first outgoing edge.
label - Variable in class VariableArrayTrie
 
lastVal() - Method in class IntQueue
Returns the last element of the queue.
lcp(String, String) - Static method in class DFT
Returns the longest common prefix of the strings s and t.
lcp() - Method in class DFT
Returns the vector of longest common prefixes of an DFT.
lcs(String, String) - Static method in class ElementaryAlgorithms
Implements the algorithm LCS()() of Section 1.2.4.
lcsLength(String, String) - Static method in class ElementaryAlgorithms
Computes the length of a longest common subword of x and y.
lcsLengthArray(String, String) - Static method in class ElementaryAlgorithms
Implements the algorithm LcsLengthArray() of Section 1.2.4.
leftAction(NonNegativeVector) - Method in class NonNegativeMatrix
Returns the result of the action of the matrix on the comlumn vector x.
letterPositions(IntQueue[], int, int) - Static method in class EcoRMinimizer
Returns the array of lists of letters at a position.
letterPositions(IntQueue[], int, int) - Method in class RMinimizer
Returns the array of lists of letters at a position.
lgProductions - Variable in class Grammar
The sum of lengths of productions .
longestCommonPrefix(String, String) - Static method in class ElementaryAlgorithms
Implements the algorithm LongestCommonPrefix() of Section 1.2.1.
longestCommonPrefix(Set) - Static method in class NFT
Returns the longest common prefix of the half-edges forming the set s.
longestPrefixInTrie(String, int) - Method in class FixedArrayTrie
Computes the pair composed of the length of the longest prefix of s[j..n-1] in the trie and the vertex reached by this prefix.
longestPrefixInTrie(String, int) - Method in class ForaxTrie
Computes the pair composed of the length of the longest prefix of s[j..n-1] in the trie and the vertex reached by this prefix.
longestPrefixInTrie(String, int) - Method in interface Trie
Computes the pair composed of the length of the longest prefix of s[j..n-1] in the trie and the vertex reached by this prefix.
longestPrefixInTrie(String, int) - Method in class VariableArrayTrie
Computes the pair composed of the length of the longest prefix of s[j..n-1] in the trie and the vertex reached by this prefix.
lyndonFact(String) - Static method in class ElementaryAlgorithms
Returns the Lyndon factorization of the word x in the form (fact1)(fact2)...
lyndonFactorization(String) - Static method in class ElementaryAlgorithms
Implements the function LyndonFactorization() of Section 1.2.5.
lyndonFactorizationR(String, int) - Static method in class ElementaryAlgorithms
The same as lyndonFactorization concerning x[k..]

M

MinAutomaton - class MinAutomaton.
This class implements a command computing the minimal automaton of a set of words given in a text file using one of several possible minimization algorithms.
MinAutomaton() - Constructor for class MinAutomaton
 
Minimizer - interface Minimizer.
 
main(String[]) - Static method in class Alphabet
 
main(String[]) - Static method in class BMinimizer
 
main(String[]) - Static method in class CompileExpression
 
main(String[]) - Static method in class DFA
 
main(String[]) - Static method in class DFT
 
main(String[]) - Static method in class Element
 
main(String[]) - Static method in class ElementaryAlgorithms
 
main(String[]) - Static method in class Entropy
 
main(String[]) - Static method in class FixedArrayTrie
 
main(String[]) - Static method in class ForaxTrie
 
main(String[]) - Static method in class Grammar
 
main(String[]) - Static method in class HopcroftMinimizer
 
main(String[]) - Static method in class ICFA
 
main(String[]) - Static method in class IDFA
 
main(String[]) - Static method in class INFA
 
main(String[]) - Static method in class IntList
 
main(String[]) - Static method in class LL
 
main(String[]) - Static method in class LinkedNFA
 
main(String[]) - Static method in class MinAutomaton
 
main(String[]) - Static method in class NFA
 
main(String[]) - Static method in class NFT
 
main(String[]) - Static method in class NonNegativeMatrix
 
main(String[]) - Static method in class PairInt
 
main(String[]) - Static method in class PairIntList
 
main(String[]) - Static method in class PairIntQueue
 
main(String[]) - Static method in class SLR
 
main(String[]) - Static method in class VariableArrayTrie
 
main(String[]) - Static method in class ZLdecode
 
main(String[]) - Static method in class ZLencode
 
mark - Variable in class State
A marker used for the exploration.
mergeLeaves() - Method in class IDFA
 
minConjugate(String) - Static method in class ElementaryAlgorithms
Returns the least conjugate of x.
minimize(DFA) - Method in class BMinimizer
 
minimize(DFT) - Method in class BMinimizer
 
minimize(IDFA) - Method in class BMinimizer
Returns the minimal automaton deterministic recognizing the reverse of the words recognized by a.
minimize(DFA, Minimizer) - Static method in class DFA
Minimizes the automaton using the method m.
minimize(Minimizer) - Method in class DFA
 
minimize(DFT, Minimizer) - Static method in class DFT
Minimizes the DFT using the method m.
minimize(IDFA) - Static method in class EcoRMinimizer
The method called to minimize an acyclic trim automaton.
minimize(DFA) - Method in class FMinimizer
 
minimize(DFT) - Method in class FMinimizer
 
minimize(IDFA) - Method in class FMinimizer
 
minimize(DFA) - Method in class HopcroftMinimizer
Returns the minimal DFA equivalent to a computed by Hopcroft's algorithm.
minimize(DFT) - Method in class HopcroftMinimizer
Returns the minimal DFT equivalent to a normalized DFT a computed by Hopcroft's algorithm.
minimize(IDFA) - Method in class HopcroftMinimizer
 
minimize(Minimizer) - Method in class IDFA
 
minimize(DFA) - Method in interface Minimizer
 
minimize(DFT) - Method in interface Minimizer
 
minimize(IDFA) - Method in interface Minimizer
 
minimize(DFA) - Method in class NMinimizer
Returns the minimal automaton of a.
minimize(DFT) - Method in class NMinimizer
Returns the minimal DFT of a.
minimize(IDFA) - Method in class NMinimizer
 
minimize(DFA) - Method in class NbisMinimizer
Returns the minimal automaton of a.
minimize(DFT) - Method in class NbisMinimizer
Returns the minimal DFT of a.
minimize(IDFA) - Method in class NbisMinimizer
 
minimize(IDFA) - Method in class RMinimizer
The method called to minimize an acyclic trim automaton.
minimize(DFA) - Method in class RMinimizer
 
minimize(DFT) - Method in class RMinimizer
 
minimizeBis(IDFA) - Method in class BMinimizer
Returns the minimal automaton equivalent to a.
mixMinimize() - Method in class IDFA
 

N

NFA - class NFA.
This class implements nondeterministic finite automata.
NFA(int) - Constructor for class NFA
Creates an NFA with n states.
NFA(int, int) - Constructor for class NFA
Creates an NFA with n states and k letters.
NFA(int, Alphabet) - Constructor for class NFA
Creates an NFA with n states on the alphabet a.
NFT - class NFT.
This class implements nondeterministic finite-state transducers (NFT).
NFT(int) - Constructor for class NFT
Creates an NFT n with states.
NFT(int, int) - Constructor for class NFT
Creates an NFT with n states and k letters.
NFT(int, Alphabet) - Constructor for class NFT
Creates an NFT with n states on the alphabet a.
NMinimizer - class NMinimizer.
This class implements a naive version of the Moore minimization algorithm in O(n^3).
NMinimizer() - Constructor for class NMinimizer
 
NbisMinimizer - class NbisMinimizer.
This class implements a naive version of the Moore minimization algorithm in O(n^3).
NbisMinimizer() - Constructor for class NbisMinimizer
 
NonNegativeMatrix - class NonNegativeMatrix.
This class implements algorithms on nonnegative matrices.
NonNegativeMatrix(int) - Constructor for class NonNegativeMatrix
Creates an n times n matrix.
NonNegativeVector - class NonNegativeVector.
This class implements nonnegative real vectors.
NonNegativeVector(int) - Constructor for class NonNegativeVector
Creates an n vector with float coordinates.
naiveStringMatching(String, String) - Static method in class ElementaryAlgorithms
Implements the algorithm NaiveStringMatching(x,y) of Section 1.2.3.
nbByHeigth(int[]) - Method in class IDFA
Returns the array of numbers of states by heigth.
nbLetters - Variable in class ICFA
 
nbLetters - Variable in class INFA
 
nbProductions - Variable in class Grammar
The number of productions.
nbStates - Variable in class ICFA
The number of states.
nbStates - Variable in class IDFA
The number of states.
nbStates - Variable in class INFA
The number of states.
next(Reader, int) - Method in class Buffer
Shifts one character to the right the sliding window.
next(int, String) - Method in class DFA
returns the state reached from state p after reading the word w.
next - Variable in class FixedArrayTrie
The array of sons of the node.
next(char) - Method in class ForaxTrie
Returns the son of label c if it exists and null otherwise.
next(Set) - Method in class ICFA
Computes a set transition in an ICFA as an array of sets indexed by the letters.
next(int, char) - Method in class IDFA
Returns the state next(p,c).
next(Set) - Method in class INFA
Computes a set transition in an INFA.
next(Set, int) - Method in class NFA
Computes a set transition in a literal NFA.
next(Set, int) - Method in class NFT
Computes a set transition in an input literal NFT.
next - Variable in class VariableArrayTrie
 
next(char) - Method in class VariableArrayTrie
Returns the node Next(c) if it exists and null otherwise.
normalize() - Method in class DFT
Normalizes the DFT, pushing the output to the left.
normalize(Set) - Method in class NFT
Erases the lCP of all strings in a set of binary half-edges.
num - Variable in class VariableArrayTrie
 

O

orderEdges() - Method in class IDFA
Sorts the outgoing edges in alphabetic order.
output(String) - Method in class DFT
Returns the output corresponding to the input s.
output(Set) - Method in class NFT
Returns the string w such that (w,t) is in the set s for some terminal state t.

P

PairInt - class PairInt.
Ths class is used to handle pairs of integers, usually interpreted as half-edges (letter, state) in an automaton..
PairIntList - class PairIntList.
This class implements linked lists of pairs of integers.
PairIntList(PairInt, PairIntList) - Constructor for class PairIntList
Conversions PairInt <--> PairIntList
PairIntQueue - class PairIntQueue.
This class implements queues of pairs of integers as linked lists from the class PairIntList.
PairIntQueue() - Constructor for class PairIntQueue
 
Partition - class Partition.
This class implements partitions of the set of integers 0,...
Partition(int) - Constructor for class Partition
Creates the partition with one class (with name 0) of 0,...
Partition(int[]) - Constructor for class Partition
Creates a partition according to the class names given in the array .
PartitionS - class PartitionS.
A weak version of the class Partition.
PartitionS(int) - Constructor for class PartitionS
 
Production - class Production.
The objects of this class are productions of context-free grammars.
Production(char, String) - Constructor for class Production
Creates a production c -> s with left side c and right side s.
partition(DFA, Partition) - Method in class NMinimizer
Computes the Nerode partition from the initial partition p.
partition(IDFA, Partition) - Method in class NMinimizer
 
partition(IDFA, int[]) - Method in class NMinimizer
 
partition(DFA, Partition) - Method in class NbisMinimizer
Computes the Nerode partition from the initial partition p.
partition(IDFA, Partition) - Method in class NbisMinimizer
 
partition(IDFA, int[]) - Method in class NbisMinimizer
 
position - Variable in class LL
The current index.
position - Variable in class SLR
The current index.
positionLetters(int[][], int) - Static method in class EcoRMinimizer
Returns the array list of positions of letters.
positionLetters(int[][], int) - Method in class RMinimizer
Returns the array list of positions of letters.
print(PrintStream) - Method in class ForaxTrie
 
product(IDFA, IDFA) - Static method in class IDFA
Computes the direct product of the IDFA a and b.
productionsArray - Variable in class Grammar
The array of grammar productions.
push(int) - Method in class LL
Pop the left side of production n and push the right side .
push(short) - Method in class SLR
Push the character c on the stack.

Q

quotient(int[]) - Method in class DFA
Returns the quotient of the DFA by the partition c
quotient(Partition) - Method in class DFA
 
quotient(int[]) - Method in class IDFA
 
quotient(Partition) - Method in class IDFA
 
quotientDFT(int[]) - Method in class DFT
Returns the quotient of the DFT by the partition c
quotientDFT(Partition) - Method in class DFT
 

R

RMinimizer - class RMinimizer.
Minimization of an acyclic trim automaton in linear time.
RMinimizer() - Constructor for class RMinimizer
 
radixSort(int[][], int) - Static method in class EcoRMinimizer
Lexicographic sort of the array s.
radixSort(int[][], int) - Method in class RMinimizer
Lexicographic sort of the array s.
randomFMinimize() - Method in class IDFA
 
refine(String[]) - Method in class DFT
Realizes the iteration m=Um+v with operations in the semiring (lcp,.,0,\e) where m is a vector of strings, U the matrix of outputs and v the vector of terminal outputs.
refine(DFA, Partition) - Method in class NMinimizer
Refines the partition c.
refine(IDFA, int[]) - Method in class NMinimizer
 
refine(IDFA, Partition) - Method in class NMinimizer
 
refine(DFA, Partition) - Method in class NbisMinimizer
Refines the partition c.
refine(IDFA, int[]) - Method in class NbisMinimizer
 
refine(IDFA, Partition) - Method in class NbisMinimizer
 
remove(DListInt) - Method in class DListInt
Removes the cell head in front of the list and returns it.
remove() - Method in class IntQueue
Removes the first element of the queue.
remove() - Method in class PairIntQueue
Removes the first element of the queue.
remove(int) - Method in class VariableArrayTrie
Removes the entry of index k of the array next.
removeAll() - Method in class IntQueue
Empties the queue.
removeEdge(int, char) - Method in class IDFA
 
removeFromTrie(String) - Method in class FixedArrayTrie
Removes the string s from the trie.
removeFromTrie(String) - Method in class ForaxTrie
Removes the string s from the trie.
removeFromTrie(String) - Method in interface Trie
removes the string s from the trie.
removeFromTrie(String) - Method in class VariableArrayTrie
Removes the string s from the trie.
removeHead() - Method in class PairIntQueue
Returns the first element of the queue and removes it.
removeVal() - Method in class IntQueue
Returns the penultimate value.
renumber(boolean[]) - Method in class IDFA
Gives the new names of the states after eliminating those such that b[i] = false
renumber() - Method in class State
Renumbers the states of a NFA.
renumberStates(int[], int[][], int, int[], IDFA, IDFA) - Static method in class EcoRMinimizer
Adds states to the minimal automaton in construction b.
renumberStates(int[], int[][], int, int[], IDFA, IDFA) - Method in class RMinimizer
Adds states to the minimal automaton in construction b.
reset() - Method in class State
Resets the mark field.
resetg2l(int) - Method in class RMinimizer
Reinitializes the arrays g2l and l2g
reverse() - Method in class ICFA
Computes the deterministic automaton (IDFA) obtained by reversing the edges of a codeterministic automaton (ICFA).
reverse() - Method in class IDFA
Computes the codeterministic automaton (ICFA) obtained by reversing the edges of a deterministic automaton (IDFA).

S

SLR - class SLR.
This class implements the SLR(0) method for syntax analysis.
State - class State.
Implementation of NFA by linked lists adapted to Thomson's algorithm.
State() - Constructor for class State
Creates a new state using a name from LinkedNFA.
saka1() - Static method in class NFT
A determinisable NFT.
saka2() - Static method in class NFT
A determinisable NFT.
saka3() - Static method in class NFT
A nondeterminisable NFT.
saka4() - Static method in class NFT
A nondeterminisable NFT.
scalarProduct(NonNegativeVector) - Method in class NonNegativeVector
Computes the scalar product of the vector with the vector y.
scale(float) - Method in class NonNegativeVector
Divides all coordinates of the vector by the factor r.
seizeAll(IntQueue) - Method in class IntQueue
Adds all the elements of the queue s and empties s.
show(Hashtable, int) - Static method in class Element
Prints the list of elements of the table table whith frequency at least theshold.
show(String) - Method in class IDFA
 
show(String) - Method in class IntList
 
show(String) - Method in class IntQueue
 
show(PairInt, String) - Static method in class PairInt
 
show(String) - Method in class PairInt
 
show(Alphabet) - Method in class PairIntList
 
show(String, Alphabet) - Method in class PairIntList
 
show(String, Alphabet) - Method in class PairIntQueue
 
show(Alphabet) - Method in class PairIntQueue
 
showAI(String, Alphabet) - Method in class PairInt
 
showAI(Alphabet) - Method in class PairInt
 
showAI(PairIntList, Alphabet) - Static method in class PairIntList
 
showAI(String, Alphabet) - Method in class PairIntList
 
showAI(String, Alphabet) - Method in class PairIntQueue
 
showAI(Alphabet) - Method in class PairIntQueue
 
showIA(String, Alphabet) - Method in class PairInt
 
showIA(Alphabet) - Method in class PairInt
 
showII(String) - Method in class PairIntList
 
showII() - Method in class PairIntList
 
showWithoutln(String) - Method in class PairInt
 
showWithoutln(String, Alphabet) - Method in class PairIntList
 
sibling(short) - Method in class Grammar
Implements the function Sibling().
size() - Method in class IntQueue
Returns the size of the queue.
size() - Method in class VariableArrayTrie
Returns the number of nodes of the trie.
stabilize(DFA, Partition) - Method in class HopcroftMinimizer
This method computes the partition refining partition which is compatible whith the DFA a.
stack - Variable in class LL
The stack used to store the LR states.
stack - Variable in class SLR
The stack used to store the LR states.
star(int, String) - Method in class DFT
Returns the output from state q under input w (without regard to terminal states and a possible terminal output).

T

ThompsonCompiler - class ThompsonCompiler.
Compiles a rational expression into an automaton of the class NFA by Thompson's algorithm.
ThompsonCompiler() - Constructor for class ThompsonCompiler
 
Trie - interface Trie.
Interface for the implementation of the Trie data structure.
terminal - Variable in class FixedArrayTrie
True if the node is terminal.
terminal - Variable in class ICFA
The terminal state.
terminal - Variable in class IDFA
The array of terminal states.
terminal - Variable in class INFA
The set of terminal states.
terminal - Variable in class InfoNFA
 
terminal - Variable in class VariableArrayTrie
 
terminals - Variable in class Grammar
The terminals.
to1 - Variable in class State
The ends of the outgoing edges.
to2 - Variable in class State
The ends of the outgoing edges.
toChar(Set) - Method in class Alphabet
Converts to characters the elements of the set of Short s.
toDFA() - Method in class NFA
Implements the determinization algorithm.
toDFA(Alphabet) - Method in class VariableArrayTrie
 
toDFA2() - Method in class NFA
The same as toDFA but with an implementation of the set of states of the resulting DFA via a HashMap.
toDFA3() - Method in class NFA
Implements the determinization algorithm.
toDFAbis(Alphabet) - Method in class VariableArrayTrie
 
toDFT() - Method in class NFT
Returns the determinization of the NFA.
toDawg() - Method in class ForaxTrie
 
toDawg() - Method in class VariableArrayTrie
 
toFile(String, String) - Static method in class ZLdecode
 
toFile(String, String) - Static method in class ZLencode
 
toIDFA(int) - Method in class ICFA
Implements the determinization algorithm.
toIDFA(int) - Method in class INFA
Implements the determinization algorithm.
toIDFA(Alphabet) - Method in class VariableArrayTrie
 
toIDFA2(int) - Method in class ICFA
The same as toIDFA but with an implementation of the set of states of the resulting IDFA via a HashMap.
toIDFAbis(Alphabet) - Method in class VariableArrayTrie
Creates an IDFA from a trie.
toInfoDFA() - Method in class InfoNFA
Implements the determinization algorithm.
toLinkedNFA() - Method in class ThompsonCompiler
 
toNFA(String) - Method in interface ExpressionCompiler
The function that returns an automaton recognizing the language described by the input expression.
toNFA(Alphabet) - Method in class LinkedNFA
Converts a LinkedNFA into an NFA.
toNFA(NFA, State) - Method in class LinkedNFA
The recursive call to run toNFA.
toNFA(String) - Method in class ThompsonCompiler
Compiles the expression into a nondeterministic finite automaton.
toShort(char) - Method in class Alphabet
Translates the character c to a short integer using the array charToShort.
toShort(String) - Method in class Alphabet
Translates the String w to Short using the method toShort().
toString() - Method in class Alphabet
 
toString() - Method in class DFA
 
toString() - Method in class DFT
 
toString() - Method in class DListInt
Returns the list ended with a dot.
toString() - Method in class Element
 
toString() - Method in class FixedArrayTrie
 
toString() - Method in class ForaxTrie
 
toString() - Method in class Grammar
 
toString() - Method in class HalfEdge
Overrides the method toString
toString() - Method in class ICFA
 
toString() - Method in class IDFA
 
toString() - Method in class INFA
 
toString() - Method in class IntList
 
toString() - Method in class IntQueue
 
toString() - Method in class LinkedNFA
 
toString() - Method in class NFA
 
toString() - Method in class NonNegativeVector
 
toString() - Method in class PairInt
 
toString() - Method in class Partition
returns the partition with each class on a line.
toString() - Method in class Production
 
toString() - Method in class State
 
toString() - Method in class VariableArrayTrie
 
toString(int, int) - Static method in class ZLencode
 
tooLong(Set) - Method in class NFT
Returns true if the label of a half-edge in the set l exceeds the bound 2 * LmaxOutput() * n * n.
transfer(int, int, int) - Method in class Partition
Transfers q from the class src to the class dest.
transfer(DListInt, int, int) - Method in class Partition
Transfers the elements of the list list from the class src to the class dest.
transfer(IntList, int, int) - Method in class Partition
 
triParHauteur(int[], IDFA) - Static method in class EcoRMinimizer
Returns the array sh of queues such that sh[r] is the queue of states at heigth r.
triParHauteur(int[], IDFA) - Method in class RMinimizer
Returns the array sh of queues such that sh[r] is the queue of states at heigth r.
trim() - Method in class IDFA
Computes the trimmed automaton equivalent to a given acyclic automaton.

V

VariableArrayTrie - class VariableArrayTrie.
An implementation of tries with arrays of variable size.
VariableArrayTrie(char) - Constructor for class VariableArrayTrie
Creates a node with label c.
variables - Variable in class Grammar
The variables.
verbose - Static variable in class BMinimizer
 
verbose - Static variable in class FMinimizer
 
verbose - Static variable in class HopcroftMinimizer
A boolean flag allowing to set a verbose mode.
verbose - Static variable in class NMinimizer
 
verbose - Static variable in class NbisMinimizer
 
verbose - Static variable in class RMinimizer
 

W

width() - Method in class IDFA
Computes the width (or outdegree) of each state.
word - Variable in class Buffer
 

Z

ZLdecode - class ZLdecode.
This class implements the decoding part of the Ziv-Lempel text compression algorithm.
ZLdecode() - Constructor for class ZLdecode
 
ZLdecoding(String) - Static method in class ZLdecode
Implements ZLdecoding().
ZLencode - class ZLencode.
This class implements the encoding part of the Ziv-Lempel text compression algorithm.
ZLencode() - Constructor for class ZLencode
 
ZLencoding(Alphabet, String) - Static method in class ZLencode
Implements ZLcoding().

A B C D E F G H I L M N O P Q R S T V W Z