text:
|Publication number
|Publication type
|Application number
|Publication date
|5 Jun 2001
|Filing date
|2 Oct 1998
|Priority date
|21 Jan 1997
|Fee status
|Also published as
|Publication number
|Mehryar Mohri, Fernando Carlos Neves Pereira, Michael Dennis Riley
|Original Assignee
|At&T Corporation
|Export Citation
|BiBTeX, EndNote, RefMan
|Patent Citations (2), Non-Patent Citations (3), Referenced by (88), Classifications (8), Legal Events (4)
|External Links: USPTO, USPTO Assignment, Espacenet
This is a Continuation application Ser. No. 08/781,368 filed Jan. 21, 1997, now abandoned. The entire disclosure of the prior application is hereby incorporated by reference herein in its entirety.
This invention relates to pattern recognition systems. More particularly, the invention relates to determinization and minimization in natural language processing.
Finite-state machines have been used in many areas of computational linguistics. Their use can be justified by both linguistic and computational arguments. Linguistically, finite automata, which are directed graphs having states and transitions, are convenient since they allow one to describe easily most of the relevant local phenomena encountered in the empirical study of language. They often provide a compact representation of lexical rules or idioms and clich�s which appears as natural to linguists. Graphic tools also allow one to visualize and modify automata. This helps in correcting and completing a grammar. Other more general phenomena such as parsing context-free grammars can also be dealt with using finite-state machines. Moreover, the underlying mechanisms in most of the methods used in parsing are related to automata.
From the computational point of view, the use of finite-state machines is mainly motivated by considerations of time and space efficiency. Time efficiency is usually achieved by using deterministic algorithms that reduce redundancy in the automata. The output of deterministic machines depends, in general linearly, only on the input size and can therefore be considered as optimal from this point of view. Space efficiency is achieved with classical minimization algorithms that collapse some nodes in the determinized automata in a reverse determinizing manner. Applications such as compiler construction have shown deterministic finite-state automata to be very efficient in practice. Finite-state automata also constitute now a rich chapter of theoretical computer science.
Their recent applications in natural language processing which range from the construction of lexical analyzers and the compilation of morphological and phonological rules to speech processing show the practical efficiency of finite-state machines in many areas.
Both time and space concerns are important when dealing with language. Indeed, one of the trends which clearly come out of new studies of language is a large increase in the size of data. Lexical approaches have shown to be the most appropriate in many areas of computational linguistics ranging from large-scale dictionaries in morphology to large lexical grammars in syntax. The effect of the size increase on time and space efficiency is probably the main computational problem one needs to face in language processing.
The use of finite-state machines in natural language processing is certainly not new. Indeed, sequential finite-state transducers are now used in all areas of computational linguistics. Limitations of the corresponding techniques, however, are very often pointed out more than their advantages. This might be explained by the lack of description of recent works in computer science manuals.
It is therefore an object of this invention to provide a pattern recognition system that applies determinization means to achieve time efficiency and minimization means to achieve space efficiency.
It is a more particular object of this invention to provide the speech recognition system that allows pruning of the automata by determinization without loss of information and better control of the result while taking account the word content represented by weights applied to automata.
It is another object of this invention to provide the speech recognition system that also allows pruning of the automata by minimization without loss of information while using equivalent functions as determinization.
It is yet another object of this invention to provide the speech recognition system that further allows testing of given automata to determine whether it can be determinized by a determinizability test.
These and other objects of the invention are accomplished in accordance with the principles of the present invention by providing a system and method for optimal reduction of redundancy and size of a weighted and labeled graph. The system and method of the present invention presents labeling the graph by assigning contents to arcs in the graph, evaluating weights of each path between states by examining relationship between the labels, assigning the weight to each arc and determinizing the graph by removing redundant arcs with the same weights. The system and method may further provide the step of minimizing the graph by collapsing a portion of the states in the graph in a reverse determinizing manner.
In another aspect of the invention, the system and method of the present invention may be applied for use in a language processing. Such system and method presents receiving speech signals, converting the speech signals into word sequences, evaluating the probability that each word sequence would be spoken, interpreting the word sequences in terms of the graph having its arcs labeled with the word sequences and its path weighted with the evaluated probabilities and determinizing the graph by removing redundant word sequences in the graph during the interpretation. The system and method may further present minimizing the graph by collapsing a portion of the states in a reverse determirnizing manner during the interpretation.
Further features of the present invention, its nature and various advantages will be more apparent from the accompanying drawings and the following detailed description of the preferred embodiments.
FIG. 1 is a simplified block diagram of illustrative apparatus which can be operated in accordance with this invention.
FIGS. 2a-b (collectively referred to as FIG. 2) are a flow chart of steps for carrying out an illustrative embodiment of the methods of this invention.
FIG. 3 is a graph of illustrative subsequential string to weight transducer.
FIG. 4 is an algorithm for determinization of a transducer γ1 representing a power series on the semiring.
FIG. 5 is a graph of illustrative transducer μ1 representing a power series defined on {R+∪{∞}, min, +}.
FIG. 6 is a graph of illustrative transducer μ2 obtained by power series determinization of μ1.
FIGS. 7-9 are graphs of illustrative minimization process where β1 represents a subsequential string to weight transducer, γ1 represents a transducer obtained from β1 by extraction and δ1 represents a minimal transducer obtained from γ2 by automata minimization.
FIG. 10 is a graph of illustrative subsequential transducer X that is not bisubsequential.
FIG. 11 is a graph of illustrative transducer β2 obtained by reversing β1.
FIG. 12 is a graph of illustrative transducer β3 obtained by determinization of β2.
FIG. 13 is a graph of illustrative transducer β4 obtained by minimization of β3.
FIG. 14 is a graph of illustrative word lattice W1 for the utterance "which flights leave Detroit and arrive at Saint-Petersburg around nine a.m.?"
FIG. 15 is a graph of equivalent word lattice W2 obtained by determinization of W1.
FIG. 16 is a graph of equivalent word lattice W3 obtained by minimization from W2.
FIG. 17 is a table of illustrative word lattices in the ATIS task.
FIG. 18 is a table of illustrative deterministic word lattices in the NAB task.
The following detailed description presents the description of a system and method for recognizing speech signals, theoretical basis, and algorithmatic tools employed to analyze the complexity of language. It will, however, be apparent to those skilled in the art that the methodology of the invention is broadly applicable to a variety of other pattern recognition systems for optimal reduction of redundancy and size of a weighted and label graph.
1. Overview
In the illustrative embodiment of speech recognition system shown in FIG. 1, speech signals are fed into microphone/acoustic analyzer 100, where it is analyzed into acoustic features. The speech signals are then passed to decoder 102 which requests a state and its outgoing transitions. Network cache 110 is first examined to see if that information has already been computed and stored in its memory (such memory being initially empty).
If so, that information from network cache 110 is returned to decoder 102. Otherwise, network cache 110 passes the request onto context-dependency transducer 112. Thereafter, decoder 102 analyzes the speech signals by utilizing-the following transducers: context-dependency transducer 112, lexicon/pronunciation transducer 114 and grammar transducer 116.
Word lattice processor 104 then requests the transitions or paths leaving each state or node to formulate a graph and explores the paths and prunes out the unpromising ones (based on their acoustic and grammar match scores). This process is repeated until the final network states are reached. Best/n-best transcriber 106 then chooses the best scoring path and display device 108 displays the outcome of the recognition hypothesis.
Some components of the speech recognition system in FIG. 1 may be a microprocessor or digital signal processor ("DSP") hardware, such as the AT&T DSP 16 or DSP 32C, read-only memory "ROM" for storing software performing the operations discussed below, and random access memory ("RAM") for storing results. Very large scale integration ("VLSI") hardware embodiments, as well as a custom VLSI circuity in combination with a general purpose DSP circuit, may also be provided.
In FIG. 2, a flow chart illustrating the operations of the speech recognition system of FIG. 1 is depicted. In this illustrative example, the flow chart begins at step 200. Microphone/acoustic analyzer 100 detects audio signals at step 202 and captures their acoustic measurements at step 204. Decoder 102 (FIG. 1) receives this acoustic observation and generates context-dependency units in accordance with the appropriate context environment. For example, the context-dependency units are determined to fit naturally between their previous phone and their subsequent phone.
Context-dependency transducer 112 (FIG. 1) receives these context-dependency units from decoder 110 to generate phonetic units at step 208. Lexicon/pronunciation transducer 114 (FIG. 1) subsequently receives these phonetic units from context-dependency transducer 112 and generates words at step 210. Grammar transducer 116 (FIG. 1) finally receives these words from lexicon/pronunciation transducer 110 and generates word sequences or sentences at step 212.
Decoder 102 (FIG. 1) and word lattice processor 104 (FIG. 1) in conjunction interpret these sentences and formulate a lattice which is a weighted and directed graph at step 214. Word lattice processor 104 (FIG. 1) assigns the estimated probability that word sequences would be spoken in constructing the paths in the lattice. The lattice, thus, have nodes labeled with the word sequences and paths weighted with the probabilities. For example, the word lattice processor 104 (FIG. 1) may be connected to a database containing the probabilities of word sequences that were used in a particular literature such as Wall Street Journal so that the speech recognition system would be more effective in recognizing the speech of economists or financiers.
Word lattice processor 104 (FIG. 1) then examines the lattice to test determinizability at step 216. The determinizability determines whether the lattice is suitable for certain processing such as determinization or minimization to efficiently reshape the lattice.
If the lattice passes the determinizability test, word lattice processor 1041 (FIG. 1) applies determinization in step 218 which removes redundant paths from the lattice. The theoretical basis and related algorithms for determinization will be discussed in a greater detail herein below.
Word lattice processor 104 (FIG. 1) may further apply minimization in step 220 so as to collapse lattice nodes that have the same possible combination. The theoretical basis and related algorithms for minimization will also be discussed in a greater detail herein below.
Best/n-best transcriber 106 (FIG. 1) thereafter may extract the best possible transcription at step 220. Alternatively, best/n-best transcriber 106 may extract a number of best transcriptions and reduce them to one or n transcription(s).
Display device 108 (FIG. 1) finally displays the resulted transcriptions at step 224. A viewer, therefore, may see the text of the speech being automatically typed on a monitor of display device 108 (FIG. 1). The flow chart ends in step 226.
Next several sections provide definition and algorithms that were used in determinization step 218, determinizability step 216 and minimization step 218. Thereafter, there is description of practical application of these algorithms.
2. Definition
In the following, string to weight transducers are introduced for their use in natural language processing. However, it would be apparent to those skilled in the art that the methodology of this invention is broadly applicable to a variety of other transducers including string to string transducers.
This section also considers subsequential power series in the tropical semiring that includes the functions associated with subsequential string to weight transducers. Most power series defined on the tropical semiring considered in practice are subsequential.
The string to weight transducers are used in various domains such as language modeling, representation of a word or phonetic lattice, etc. They are used in the following way: one reads and follows a path corresponding to a given input string and outputs a number obtained by combining the weight outputs along this path. In most applications of natural language processing, the weights are simply added along a path, since output label weights are interpreted as negative logarithms of probabilities. In case the transducer is not deterministic or sequential, one proceeds in the same way for all the paths corresponding to the input: string and then collect all numbers obtained this way. In natural language processing and especially in speech processing, only the minimum of these numbers is kept as being relevant information. We are interested here in the use of such transducers in many applications to natural language processing involving a Hidden Markov Model ("HMM") that represents possible sequences of acoustic observations in realizations of the elementary speech units such as phones. In all such applications, one searches for the best path. This is related to the Viterbi approximation often used in speech recognition.
Specifically, the use of an efficient string to weight transducers called subsequential transducer is examined. Subsequential string to weight transducers are also called weighted automata, or weighted acceptors, or probabilistic automata, or distance automata. Not all transducers are subsequential but we define algorithms which allow one to determinize these transducers whenever possible. More precisely, we shall say that a string to weight transducer is subsequential when it is deterministic and when it is provided with a final weight function, and an initial weight. These weights are added to those encountered along a path corresponding to a given string.
Referring to FIG. 3, for instance, when used with the input string "ab.," the transducer outputs: 5+1+2+3=11, 5 being the initial and 3 being the final weight. More formally a subsequential transducer τ=(V, i, F, A, δ, σ, λ, ρ) is an 8-tuple, where V is the set of its states, i is the initial state of VF is the set of final states of V, A is the input alphabet of V, δ is the state transition function which maps V�A to V, σ is the output which maps V�A to +, λ is the initial weight and ρ is the final weight function mapping F to +. Unless otherwise specified, the output weights are positive real numbers.
String to weight transducers clearly realize functions mapping A* to +. A* is a sequential or p-subsequential function, i.e., a function which can be represented by a sequential or p-subsequential transducer. Since the operations we need to consider are addition and min, and since + ∪{∞}, min, +) is a semiring, we can call these functions formal power series according to the terminology used in formal languages theory. A semiring is essentially a ring which lacks negation, that is in which the first operation does not necessarily admit inverse. , +, �), and (N∪{∞}, min, +) are other examples of semiring. We shall also adopt the notations used in this field. The image by a formal power series S of a string w is denoted by (S, w) and is also called the coefficient of w in S. The notation S=Σ(S, w) w is often used to define a power series by its coefficients. The support of S, supp(S), is the language defined by
The fundamental theorem of Sch�tzenberger, analogous of the Kleene's theorem for formal languages states that a formal power series S is rational if it is recognizable, that is realizable by a transducer with initial weights and final weights. The semiring + ∪{∞}, min, +) is often distinguished from other semirings since it is involved in many optimization problems. It is called the tropical semiring which is the terminology used in principle to denote the semiring of natural integers (N∪{∞}, min, +) involved in optimization problems. Thus the functions we consider here are more precisely rational power series defined on the tropical semiring.
3. Determinization
This section introduces a theorem helping to characterize subsequential power series independently from the transducer representing them. It includes an algorithm to determinize a transducer representing a power series admitting this operation.
A distance d(u,v) on the string A* can be defined by:
where we denote by uΛv the longest common prefix of two words u and v in A*, and |s| denotes the length of the string s. The definition we gave for subsequential power series depends on the notion of transducers representing them. The following theorem gives a characterization of subsequential power series which is independent of a transducer realizing them. This is an extension of the characterization theorem of Choffrut for string to string functions.
Let S be a formal rational series defined on the semiring (+∪{∞}, min, +), S is subsequential if and only if it has bounded variation. For example, assume that S is subsequential. Let τ=(V, i, F, A, δ, σ, λ, ρ) be a subsequential transducer. δ denotes the transition function associated with τ, σ denotes its output function, λ and ρ denote the initial and final weight functions, q and q′ are states of V, and a is an input symbol of the alphabet A. Let L be the maximum of the lengths of all output labels of τ:
and R the upper bound of all output differences at final states:
and define M as M=L+R. Let (u1, u2) be words, or more generally, strings, in (A*)2. By definition of the distance d, there exists u ε A* that is a common perfix string to the strings u1 and u2 such that:
where v1 and v2 are the remaining portions of u1 and u2, respectively, after the common prefix string u, and d(u1, u2) is the distance from u1 and u2.
we have
Notice that if u1≠u2, R≦R�d(u1, u2). Thus
This proves that S is M-Lipschitzian and a fortiori that it has bounded variation. This also implies in particular that the subsequential power series over the tropical semiring define continuous functions for the topology induced by the distance d on A*.
Conversely, suppose that S has bounded variation. Since S is rational, it is recognizable and therefore there exists a transducer τ1=(V1, i1, F1, A, δ1, σ1, λ1, ρ1) recognizing S. Here, τ1 might be non-deterministic. Therefore, the transition function δ1 maps V1�A to 2v1, and the output function σ1 maps V1�A�V1 to +. The output of a transition from a state q to a next state q′ labeled with a, where a is a symbol of the alphabet A, is therefore denoted by σ1 (q, a, q′). Also λ1 is a function since τ1 might have several initial states. We shall assume that τ1 is trim and it has no non-accessible state or non-coaccessible state. Non-accessible states are those unreachable from initial states and non-coaccessible states those which admit no path to a final state. Any rational function can be represented by a trim transducer simply by removing these useless states from a transducer representing it.
The following is an algorithm to construct from the non-deterministic transducer τ1 representing S, an equivalent deterministic transducer τ2=(V2, i2, F2, A, δ2, σ2, λ1, ρ2,). The algorithm extends to the case of transducers which output weights our determinization algorithm for string to string transducers representing p-subsequential functions as described in an article by one of the inventors (Mohri, "On some applications of finite-state automata theory to natural language processing," Technical Report ICM 94-22, Institut Gespard Monge, 1994) which is incorporated herein by reference.
FIG. 4 presents this algorithm. It describes the algorithm in the general case of a semiring (S,⊕,⊙,0,1) on which the transducer τ1 is defined, where ⊕ is a summining operation, ⊙ is a multiplying operation, "0" is the identity value for the summing operation and "1" is the identity value for the multiplying operation. Indeed, the algorithm described here applies as well to transducers representing power series defined on many other semirings. In particular, it can be verified that (A*∪{∞},Λ,�,∞,ε), where Λ denotes the longest common prefix operation, � denotes the concatenation, ε is the empty set, and ∞ denotes a new element such that for any string w ε (A*∪{∞}), wΛ∞=∞Λw=w and w�∞=∞�w=∞, also defines a left semiring. Considering this semiring in the algorithm of FIG. 4 gives the determinization for subsequentiable string to string transducers. The algorithm also applies to other semirings such as (++, �) for instance. Since the cross product of two semirings also defines a semiring, this algorithm also applies to the cross product of (A*∪{∞},Λ,�,∞,ε) and (+∪{∞}, min, +). This allows one to directly determinize transducers with both weight and string outputs admitting determinization. Thus, for the purpose of the algorithm we consider here, one can replace ⊕ by min. and ⊙ by + in the algorithm of FIG. 4. That is λ2 −1 should also be interpreted as −λ, and [σ2(q2,a)]−1 as −σ2(q2, a). The sets, Γ(q2,a), γ(q2,a) and ν(q2,a) and γ(q2,a) used in the algorithm are defined by:
The algorithm is similar to the powerset construction used for the determinization of non-deterministic automata. However, since the output of two transitions bearing the same input label might differ, here one can only output the minimum of these outputs in the resulting transducer and therefore needs to keep track of the remaining weight.
Subsets are thus formed of pairs of state and weight. Notice that several transitions might reach here the same state with a priori different remaining weights. Since one is only interested in the best path corresponding to the minimum weight, one can keep the minimum of these possible distinct weights for a given state element of a subset (line 11 of the algorithm of FIG. 4).
The algorithm is also illustrated by FIGS. 5-6. Notice that the input ab admits several outputs in u1: {1+1=2, 1+3=4, 3+3=6, 3+5=8}. Only one of these outputs (2, the smallest one) is kept in the determinized transducer μ2 since in the tropical semiring one is only interested in the minimum outputs for any given string. Most power series defined on the tropical semiring considered in practice are subsequential.
FIG. 5 shows a non-determiaistic finite-state transducer u1. As shown in FIG. 5, the non-deterministic finite-state transducer ul has four states, a start state 0, an intermediate state 2, and final states 1 and 3. In particular, given an input "a" received at the start state 0, the non-deterministic finite-state transducer u1 can move from the start state 0 to the final state 1 with weight 3 or to the intermediate state 2 with weight 1. Similarly, if an input "b" is received at the start state 0, the non-deterministic finite-state transducer ul will move from the start state to the final state 1 with weight 1 or to the intermediate state 2 with weight 4. Similarly, at the final state 1, when the input "b" is received, the non-deterministic finite-state transducer u1 will move from the final state 1 to the final state 3 with a weight of either 3 or 5. Likewise, at the intermediate state 2, when the input "b" is received, the non-deteiministic finite-state transducer u1 will move from the intermediate state 2 to the final state 3 with a weight of either 1 or 3. Thus, the finite-state transducer u1 is non-deterministic, because at least one state, and in this case, at states 0, 1, and 2, for a given input, there is more than one path which can be taken from that state to either different states or on different paths to the same state.
FIG. 4 is a pseudocode outlining the determinization process, where τ1 is the input non-deterministic finite-state transducer and τ2 is the output deterministic finite-state transducer. The non-deterministic finite-state transducer u1 shown in FIG. 5 is one example of such a non-deterministic finite-state transducer τ1, while the deterministic finite-state transducer u2 shown in FIG. 6 is one example of such a non-deterministic finite-state transducer τ2.
In particular, starting in step 1, the final state set F2 of the deterministic finite-state transducer τ2 to be generated is set to the empty set. Then, in steps 2 and 3, the set of initial states I1 of the non-deterministic finite-state transducer τ1 and the minimum weight λ2 of weights λ1, of the initial states i are used to create a single initial state i2 of the deterministic finite-state transducer τ2. As shown in the corresponding initial state 0 of FIG. 6, this single initial state i2 will have one (or more) substates, each indicating the original state i of the non-deterministic finite-state transducer τ1 and the difference between the weight of that original state i and the minimum weight λ2.
Next, in step 4, the single initial state i2 of the deterministic finite-state transducer τ2 is pushed on top of a queue Q. At this point, the queue Q contains only the single initial state i2 of the deterministic finite-state transducer τ2. In steps 5 and 6, while the queue Q is not empty, the top state on the queue Q is popped as the current state q2 of the de-terministic finite-state transducer τ2. Next, in state 7, the current state q2 is checked to determine if it contains a substate (q, x) that was a final state of the non-deterministic finite-state transducer τ1. If so, in step 8, the current state q2 is added to the set of final states F2 of the deterministic finite-state transducer τ2. Then, in step 9, the final output weight ρ associated with the current state q2 is the minimum of the sum, for each substate q of the current state q2, of the remainder x of that substate q and the final output weight p associated with that substate q.
In step 10, the set of transition labels a of all transitions from all substates of the current state is determined. For example, when the current state is state 0 of FIG. 5, the set of transition labels a includes "a, b". Similarly, when the current state is state 1 or state 2, the set of transition labels a includes "b∞. In step 10, each transition label a of the set of transition labels is selected in turn as the current label. Next, in steps 11 and 12, a new possible state of the deterministic finite-state transducer τ2 is created based on the states of the non-deterministic finite-state transducer τ1 reachable from all of the substates of the current state q2 based on the current transition label. Thus, when 0 is the current state and "a" is the current transition label, the new possible state includes the substates 1 and 2. Similarly, when the current state is the state 1′ of FIG. 6, the new state includes only the final state 3. In addition, creating the new possible state includes generating a new transition (δ2(q,a)) from the current state q2 to the new state, determining the weight (σ2(q,a)) of that new transition and determining the remainders x associated with each of the substates q of the possible new state.
In step 13, the new possible state is checked to determine if it is identical to some previously determinized state in the deterministic finite-state transducer τ2 being created. That is, in step 13, the new state is checked to determine if it is the same state as some old state. To be the same state, the transitions and the substates q of the new state must be identical to the transitions and the substates q of the old state, and the remainders on each of the substates q must be same as the remainders on each of the corresponding substates q of the old state. In step 14, if the new state is truly new, in that it is not identical to some old state, the new state is pushed onto the queue Q.
Steps 10-14 are repeated for each transition label a until the set of transition labels is empty. If the set of transitions is empty, then all of the transitions from all of the substates q of the current state q2 have been determinized and no further analysis of the current state q2 is necessary. In step 15 the current state q2 is removed from the queue Q. Steps 6-15 are then repeated until the queue Q is empty.
In steps 11 and 12, a possible new state is created based on the substates q, if any, of the current state q2 using the current transition label a. In step I1, thf weight σ2(q2,a) of the current transition label a is determined as the minimum, for each transition between a substate q of the current state q2 and a next state q′ having the current transition laibel a, of the weight σ1, of that transition plus the remainder x of the current substate q.
Applying the determinization method outlined in FIG. 4 to, the non-deterministic finite-state transducer u1 shown in FIG. 5 generates the deterministic finite-state transducer u2 shown in FIG. 6. First, the start state 0′ of the deterministic finite-state transducer u2 is pushed onto a stack queue Q. While the queue Q is not empty, the top state of the queue Q is popped from the queue Q. From the initial state 0 of the non-deterministic finite-state transducer u, shown in FIG. 5, the states 1 and 2 can be reached using the input symbol "a". Thus, a new state 1′=[(1,x), (2,x)] reachable from the current state 0′ (=[(0,0)]) of the deterministic finite-state transducer u2 with the input symbol "a" is established with a new transition t1′,a,ρ,1′]. The weight ρ for the new transition t1′ is the minimum weight of the transitions labeled "a" from the start state 0 to either of the reachable states 1 or 2, plus any remainder that may be assigned to a corresponding substate of the current state 0′. Because the current state 0′ is a start state, there is no remainder. Similarly, because the non-deterministic finite-state transducer u1 shown in FIG. 5 has only a single start state, there is only one substate of the current state 0′.
As shown in FIG. 5, the transition labeled "a" from the start state 0 to the state 2 has the minimum weight, 1. Thus, the weight ρ for the transition t1′ is 1. Because the weight assigned to the new transition t1′ does not capture the full weight of the other a-labeled transition from the start state 0 to the state 1, each of the substates 1 and 2 of the new state 1′ are assigned remainders x. In particular, the remainder for the substate 1 is 2, while the remainder for the substate 2 is zero. Thus, the new state 1′ is rewritten as [(1,2),(2,0)].
Additionally, because state 1 is a final state, any state of the deterministic finite-state transducer u2 will be a final state, and will have an output value. As indicated above, the minimum output weight for an input of "ab" is 2. This weight is output from state 1′, as shown in FIG. 6.
Similarly, from the start state 0 in the original non-deterministic finite-state transducer u1 shown in FIG. 5, states 1 and 2 can also be reached from the current state 0′ using the input symbol "b". Another new state 2′ is formed, and a new transition t.2 is formed from the current state 0′ to the new state 2′. The new transition t2′ is again assigned a weight which is equal to the minimum weight of the b-labeled transitions from the current state 0′ to the substates of the new state 2′. Likewise, each of the substates of the new state 2′ are assigned remainder weights. This is also shown in FIG. 6.
Because each of the new states 1′ and 2′ is not identical to any other previously determinized, or old, state, each of the new states 1′ and 2′ are added to the queue Q. Because all of the transitions from the current state 0′ have now been analyzed and determinized, the new state 1′ is popped from the queue Q. In particular, the current state 1′ has two substates 1 and 2. Each of these substates 1 and 2 in the original non-deterministic finite-state transducer u1 shown in FIG. 5 has multiple exiting transitions, but each such transition is labeled with the same label "b". Furthermore, each of these transitions moves to the final state 3. Thus, in the non-deterministic finite-state transducer u1 shown in FIG. 5, the final state 3 can be reached from both the substates 1 and 2 of the current state 1′ using the input symbol "be". In addition, there are two such b-labeled transitions from each of the substates 1 and 2. For each such original transition, a transition weight ρt for each transition is determined as the sum of the weight assigned to that transition and the remainder associated with the original substate corresponding to that transition in the current state 1′. The weight to be associated with the new transition from the current state 1′ to the new state 3′ is then the minimum of the transition weights ρt. In particular, the minimum transition weight ρr for the new state 3′ is 1. Since there is only one reachable state for the input table "b" for the current state 1′, the minimum weight p for the b-labeled transition for the current state 1′ is 1.
The minimum transition weight ρ is then used as the weight for a new transition t3′ from the current state 1′ to the new state 3′. Because there is only one reachable state, the final state 3, reachable in the original non-deterministic finite-state transducer u1 shown in FIG. 5 from the current state 1′, the new state established from the current state 1′ reachable using the input symbol b is 3′=[(3,x)]. Using the same procedure, a transition t4′from the state 2′ to the state 3′ can be formed having a weight of 3. This is shown in FIG. 6. The remainder on the new state 3′ is the minimum remainder resulting from the remainders obtained by adding the remainders in the states 1′ and 2′ and the weights on the corresponding original transitions in the non-deterministic finite-state transducer u1, less the weight on the corresponding new transitions t3′ and t4′. Accordingly, this new state 3′ thus has a remainder of zero, resulting in the complete new state 3′=[(3,0)]. The end result is thus shown in FIG. 6.
Generally when the deserminization algorithm terminates, the resulting transducer τ2 is equivaent to r1. For example, if θ1(q,w,q′) denotes the minimum susof the outputs of all paths from q to q′ by construction, line 2 of FIG. 4 becomes:
Further, if the residual output associated to q in the subset δ2(i2,w) is defined as the weight c(q,w) associated to the pair containing q in δ2(i2,w), it is not hard to show by induction on |w| that the subsets contructed by the algorithm are the sets δ2(i2,w), w εA*, such that:
Notice that the size of a subset never exceeds |V|: card (δ2(i2,w))≦|V1|. A state q belongs at most to one pair of a subset since for all paths reaching q, only the minimum of the residual outputs is kept. Notice also that, by definition of min, in any subset there exists at least on state q with a residual output c(q,w) equal to 0.
A string w is accepted by τ1 if and only if there exists qεF1 such that qε(δ1(i1, w). Using the equations set above, it is accepted if and only if δ2 (i2, w) contains a pair (q,c(q,w)) with qεF1. This is exactly the definition of the final states F2 in line 7 of FIG. 4. So τ1 and τ2 accept the same set of strings.
Let wεA* be a string accepted by τ1 and τ2. The definition of ρ2 in the algorithm of line 9 of FIG. 4 gives:
Thus, if we denote by S the power series realized by τ1, we have:
Let T=(Q,ε,I,F,E,λ,ρ) be a string-to-weight transducer, περ→wq a path in T from the state pεQ to qεQ, and π′εp′→wq′ a path from p′εQ to q′εQ both labeled with the input string wεΣ*. Assume that the lengths of π and π′ are greater than |Q|2−1, then there exist strings u1, u2, u3 in Σ*, and states p1, p2, p′1, and p′2 such that |u2|>0, u1u2u3=w and such that π and π′ be factored in the following way:
Given two transducers T1=(Q1,Σ, I1,F1,E1,λ1,ρ1) and T2=(Q2,Σ,I2,F2,E2,λ2, ρ2), the cross product of T1 and T2 may be defined as the transducer:
with outputs in R+�R+ such that t=((q1,q2),a, (x1,x2), (q′1,q′2)) ε Q1�Σ�R+�R+�Q2 is a transition of T1�T2, namely tεE, if and only if (q1, a, x1, q′1) ε E1 and (q2, a, x2, q′2) εE2. λ and ρ can be also defined by: ∀(i1, i2) ε I1�I2, λ(i1, i2)=(λ(i1), λ2(i2)), ∀(f1, f2) ε F1�F2, ρ(f1, f2)=(ρ1(f1), ρ2(f2)).
Consider the cross product of T with itself, T�T. Let π and π′ be two paths in T with lengths greater than |Q|2−1, (M>|Q|2−1):
is a path in T�T with length greater than |Q|2−1. Since T�T has exactly |Q|2 states, π admits at least one cycle at some state (p1,p′1,) labeled with a non empty input string u2. This shows the existence of the factorization above.
Let , τ1=(Q1,Σ,I1,F1,E1,λ1,ρ1) be a string-to-weight transducer defined on the tropical semiring. If τ1 has the twins property then it is determinizable. For example, assume that τ has the twins property. If the determinization algorithm does not halt, there exists at least one subset of 2Q, {q0, . . . , qm}, such that the algorithm generates an infinite number of distinct weighted subsets {(q0, c0), . . . , (qm, cm)}.
Then it is necessarily m>1. Indeed, as previously mentioned, in any subset there exists at least one state qi with a residual output ci=0. If the subset contains only one state q0, then c0=0. So there cannot be an infinite number of distinct subsets {(q0, c0)}.
Let W⊂Σ* be the set of strings w such that the states of δ2(i2, w) be {q0, . . . , qm}. We have: ∀ωε A, δ2(i2, ω)={(q0, c(q0, ω)), . . . , (qm, c(qm, ω))}. Since W is infinite, and since in each weighted subset there exists a null residual output, there exist i0, 0≦i0≦m, such that c,(qi0, ω)=0 for an infinite number of strings ω ε W. Without loss of generality, it can be assumed that i0=0.
Let B⊂W be the infinite set of strings ω for which c(q0, ω))=0. Since the number of subsets {(q0c(q0, ω)), . . . , (qm, c(qm, ω)) }, ωεB, is infinite, there exists j, 0<j≦m, such that c(qj, ω) be distinct for an infinite number of strings ω ε B. Without loss of generality, j=1 can be assumed.
Let C⊂B be an infinite set of strings ω with c(q1, ω) all distinct. (q0, q1) can be defined as the finite set of differences of the weights of paths leading to q0 and q1 labeled with the same string ω, |ω|≦|Q1|2−1:
It can be shown that {c(q1, ω):ωεC}⊂R(q0, q1). This will yield a contradiction with the infinity of C, and will therefore prove that the algorithm terminates.
Let ωεC, and consider a shortest path π0 from a state i0ε I to q0 labeled with the input string ω and with total cost σ (π0). Similarly, consider a shortest path π1 from i1 ε I to q1 labeled with the input string ω and with total cost σ (π1). By definition of the subset construction we have: (λ(i1)+σ(π1))−(λ(i0)+σ(π0))=c(q1, ω). Assuming that |ω|>|Q1|2−1, there exists a factorization of π0 and π1 of the type:
with |u2|>0. Since p0 and p1 are twins, θ1(p0, u2, P0)=θ1(p1, u2, p1). π′0 and π′1 may be defined by:
Since π and π′ are shortest paths, σ(π0)=σ(π′0)+θ1(p0, u2, p0) and σ(π1)=σ(π′1)+θ1(p1, u2, p1). Therefore: (λ(i1)+σ(π′1)−(λ(i0)+σ(π′0)=c(q1, ω). By induction on |ω|, the shortest paths π0 and π1 from i0 to q0 (resp. i1 to q1) can be found with length less or equal to |Q1|2−1 and such that λ(i1)+σ(π1)) (λ(i0)+σ(π0))=c(q1, ω). Since σ(π1)−σ(π0)εR(q0, q1), c(q1, ω) εR(q0, q1), and C is finite.
There are transducers that do not have the twins property and that are still determinizable. To characterize such transducers one needs more complex conditions. Those conditions are not described in this application. However, in the case of trim unambiguous transducers, the twins property provides a characterization of determinizable transducers.
Let τ1=(Q1,Σ,I1,F1,E1,λ1,ρ1) be a trim unambiguous string-to-weight transducer defined on the tropical semiring. Then τ1 is determinizable if and only if it has the twins property.
For example, if τ1 has the twins property, then it is determinizable. Assume now that τ does not have the twins property, then there exist at least two states q and q′ in Q that are not twins. There exists (u, v) εΣ* such that: ({q, q′} ⊂ δ1(I, u), q ε δ(q, v) , q′εδ1(q′, v)) and θ1(q, v, q)≠θ1(q′, v, q′). Consider the weighted subsets δ2(i2, uvk) , with kεN, constructed by the determinization algorithm. A subset δ2(i2, uvk) contains the pairs (q, c(q, uvk)) and (q′, c(q′, uvk)) . It can be shown that these subsets are all distinct. The determinization algorithm, therefore, does not terminate if τ1 does not have the twins property.
Since τ1 is a trim unambiguous transducer, there exists only one path in τ1 from I to q or to q′ with input string u. Similarly, the cycles at q and q′ labeled with v are unique. Thus, there exist i ε I and i′ ε I such that:
Let λ and θ be defined by:
We have:
Since θ≠0, this equation shows that the subsets δ2(i2, uvk) are all distinct.
Notice that the power series determinization algorithm is equivalent to the usual determinization of automata when all output labels are equal to 0, and all final weights equal to 0. The corresponding power series is then the characteristic function of its support supp(S) and represents exactly a regular language. The subsets considered in the algorithm are then exactly those obtained in the powerset determination of automata, the remainder output being constant and equal to 0.
Both space and time complexity of the determinization algorithm for automata is exponential. There are minimal deterministic automata with an exponential size with respect to non-deterministic ones representing them. A fortiori the complexity of the determinization algorithm in the weighted case we just described is also exponential. However, in some cases in which the degree of nondeterminism of their initial transducer is high, the determinization algorithm appears as fast and the resulting transducer has fewer number of states than the initial one. Such cases which appear in speech recognition are discussed here. Also presented is a minimization algorithm which allows one to reduce the size of subsequential transducers representing power series.
The complexity of the application of subsequential transducers is linear in the size of the string to which they apply. This property makes it interesting to use the power series determinization in order to speed up the application of transducers. However, since the algorithm only applies to subsequential power series, we need an algorithm to test this property. The following section is devoted to the definition of such an algorithm.
4. Test of determinizability
The characterization of determinizable transducers described in section 3 herein above leads to the definition of an algorithm for testing the determinizability of trim unambiguous transducers. Before describing the algorithm, it is shown that it suffices to examine a finite number of paths to test the twins property.
For example, let τ1=(Q1Σ,I1,F1,E1,λ1,ρ1) be a trim unambiguous string-to-weight transducer defined on the tropical semiring. τ1 has the twins property if and only if ∀(u,v) ε(Σ*)2, |uv|≦2|Q1|2−1,
Clearly if τ1 has the twins property, then the above equation holds. Conversely, if the above equation holds, then it also holds for any (u,v)ε(Σ*)2, by induction on |uv|. Consider (u,v)ε(Σ*)2 and (q, q′)ε|Q1|2 such that:{q,q′}⊂δ1(q,v),q′εδ1(q′,v). Assume that |uv|>2|Q1|2−1 with |v|>0. Then either |u|>|Q1|2−1 or |v|>|Q1|2−1.
Assume that |u|>|Q1|2−1. Since τ1 is a trim unambiguous transducer there exists a unique path π in τ1 from iεI to q labeled with the input string u, and a unique path π′ from i′εI to q′. In view of above equation, there exist strings u1, u2, u3 in Σ*, and states p1, p2, p′1, and p′2 such that |u2|>0, u1u2u3=u and such that π and π′ be factored in the following way:
Since |u1u2v|<|uv|, by induction θ1(q,v,q)=θ1(q′,v,q′).
Next, assume that |V|>|Q1|2−1. Then, there exist strings v1,v2,v3 in Σ*, and states q1,q2,q′1, and q′2 such that |v2|>0, v1v2v3=v and such that π and π′ be factored in the following way:
Since |uv1v3|<|uv|, by induction, θ1(q,v1v3,q)=θ1(q′,v1v3,q′). Similarly, since |uv1v2|<|uv|, θ1(q1,v2,q1)=θ1(q′1, v2, q′1) . τ1 is a trim unambiguous transducer, so:
Thus, θ1(q,v,q)=θ1(q′,v,q′).
If τ1=(Q1, Σ,I1,F1,E1,λ1,ρ1) is a trim unambiguous string-to-weight transducer defined on the tropical semiring, then there exists an algorithm to test the determinizability of τ1.
For example, testing the determinizability of τ1 is equivalent to testing for the twins property. An algorithm to test this property is defined, specifically for testing the sequentiability of string-to-string transducers. It is based on the construction of an atom A=(Q,I,F,E) similar to the cross product of τ1 with itself.
Let k⊂+ be the finite set of real numbers defined by:
A can be defined by the following:
The set of states of A is defined by Q=Q1�Q1�K,
The set of initial states by I=I1�I1�{0}
The set of final states by F=F1�F1�K,
The set of transictions by:
By construction, two states q1 and q2 of Q can be reached by the same string u, |u|≦2|Q1|2−1, if and only if there exists cεK such that (q1,q2,c) can be reached from I in A. The set of such (q1,q2,c)is exactly the transitive closure of I in A. The transitive closure of I can be determined in time linear in the size of A,O(|Q|+|E|).
Two such states q1 and q2 are not twins if and only if there exists a path in A from (q1,q2,0) to (q1,q2,c), with c≠0. Indeed, this is exactly equivalent to the existence of cycles at q1 and q2 with the same input label and distinct output weights and it suffices to test the twins property for strings of length less than 2|Q1|2−1. So the following gives an algorithm to test the twins property of a transducer τ1:
1. Compute the transitive closure of I: T(I) .
2. Determine the set of pairs (q1,q2) of T(I) with distinct states q1≠q2.
3. For each such {q1,q2} compute the transitive closure of (q1, q2, 0) in A. If it contains (q1,q2,c) with c≠0, then T1 does not have the twins property.
The operations used in the algorithm (computation of the transitive closure, determination of the set of states) can all be done in polynomial time with respect to the size of A, using classical algorithms.
This provides an algorithm for testing the twins property of an unambiguous trim transducer T. It is very useful when one knows auto be unambiguous.
In many practical cases, the transducer one wishes to determine is ambiguous. It is always possible to construct an unambiguous transducer T′ from T. The complexity of such a construction is exponential in the worst case. Thus the overall complexity of the test of determinizability is also exponential in the worst case.
Notice that if one wishes to construct the result of the determinization of T for a given input string w, one does not need to expand the whole result. of the determinization, but only the necessary part of the determinized transducer. When restricted to a finite set the function realized by any transducer is subsequentiable since it has bounded variation. Acyclic transducers have the twins property, so they are determinizable. Therefore, it is always possible to expand the result of the determinization algorithm for a finite set of input strings, even if T is not determinizable.
5. Minimization
This section presents a minimization algorithm which applies to subsequential string to weight transducers. The algorithm is very efficient. The determinization algorithm can also be used in many cases to minimize a subsequential transducer.
A minimization algorithm for subsequential power series is defined on the tropical semiring which extends the algorithm defined by an article by one of the inventors (Mohri, "Minimization of sequential transducer," Lecture Notes in Computer Science 4, 1994, Institut Gaspard Monge, Universit Marne la Vallee) in the case of string to string transducers. This article is incorporated herein by reference. An algorithm allowing one to minimize the representation of power series was defined by Sch�tetzenberger. However, Sch�tzenberger's algorithm only applies when the semiring considered is a field. Thus, it does not apply to the tropical semiring. Our minimization algorithm applies to subsequential power series defined /+, �) other semirings, in particular to those defined on for which the algorithm by Sch�ttzenberger was defined.
For any subset L of a finite set A* of the alphabet A (or of a finite set Σ* of the alphabet Σ) and any string u we define u−1L by:
Recall that L is a regular language if and only if there exists a finite number of distinct u−1L. In a similar way, given a power series S we define a new power series u−1S by:
One can prove that S is a rational power series if and "only if it admits a finite number of independents u−1S. This is the equivalent for power series of the Nerode's theorem for regular languages.
For any subsequential power series S, we can now define the following relation on A*:
It is easy to show that Rs is an equivalence relation. u−1 supp(S)=v−1 supp(S)) defines the equivalence relation for regular languages. Rs is a finer relation. The additional condition in the definition of Rs is that the restriction of the power series [u−1S−v1S] to u−1supp(S)=v−1supp(S) is constant. The following shows that if there exists a subsequent transducer T computing S with a number of states equal to the number of equivalence classes of Rs, then T is a minimal transducer computing f.
For example if there is a subsequent power series defined on the tropical semiring, Rs has a finite number of equivalence classes. This number is bounded- by the number of states of any subsequent transducer realizing S. For example, let T=(V, i, F, A, δ, σ, λ, ρ) be a subsequent transducer realizing S. Clearly,
Also, if u−1supp(S)=v−1supp(S), ∀(u, v)ε(A*)2,
The existence of a minimal subsequent transducer representing S may be shown. For any sequential function S, there exists a minimal subsequent transducer computing it. Its number of states is equal to the index of Rs. For instance, given a subsequent series S, a series f may be defined by:
A subsequent transducer T=(V, i, F, A,δσ,λ,ρ) may then defined by:
where we denote by {overscore (u)} the equivalence class of uεA*.
Since the index of Rs is finite, V and F are well defined. The definition of δ does not depend on the choice of the element u in {overscore (u)} since for any a εA, u Rs v implies (ua) Rs (va). The definition of τ is also independent of this choice since by definition of Rs, if uRsv, then (ua) Rs (va) and there exists kε such that ∀wεA*, (S, uaw)−(S, vaw)=(S, uw)−(S, vw)=k. Notice that the definition of σ, implies that:
Thus, T realizes S:
Given a subsequential transducer T=(V, i, A, δ, σ, λ, ρ), each state qεV, d(q) can be defined by:
A new operation of pushing can be defined which applies to any transducer T. In particular, if T is subsequential and the result of the application of pushing to T is a new subsequential transducer T′=(V, i, F, A, δ, σ′, λ′, ρ′) which only differs from T by its output weights in the following way:
Since d(δ(q, a))−d(q)+σ(q,a)≦0, T′ is well defined.
Let T′ be the transducer obtained from T by pushing. T′ is a subsequential transducer which realizes the same function as T. Also,
Therefore, since δ(i, w)εF=>d(δ(i,w))=ρ(δ(iw)), λ′+σ−(i, w)+p′(δ(i, w))=λ+d(i)+σ(q, w)+ρ(δ(i, w))−d(i)+0
The following defines the minimization algorithm.
Let T be a subsequential transducer realizing a power series on the tropical semiring. Then applying the following two operations:
automata minimization leads to a minimal transducer.
The minimization step consists of considering pairs of input label and associated weights as a single label and of applying classical minimization algorithms for automata. In general, there are several distinct minimal subsequential transducers realizing the same function. However, their topology is identical. They only differ by their output labels which can be more or less delayed. The result of the application of pushing to any minimal transducer is however unique. It is the minimal transducer defined in the proof of the existence of a mimimal subsequential transducer computing the subsequential function S.
Notice that if a new super final state Φ to which each final state q is connected by a transition of weight p(q) is introduced, then d(q) in the definition of T′ is exactly the length of a shortest path from Φ to q. Thus, T′ can be obtained from T by the classical single-source shortest paths algorithms such as that of Dijkstra if the transition weights are low. This algorithm can be extended to the case where weights are negative. If there is no negative cycle the Bellman-Ford algorithm can be used. In case the transducer is acyclic, a linear time algorithm based on a topological sort of the graph allows one to obtain d.
Once the function d is defined, the transformation of T into T′ can be done in linear time, namely O([V]+[E]), if we denote by E the set of transitions of T. The complexity of pushing is therefore linear (O([V]+[E])) if the transducer is acyclic, C([E]+[V]log [V]) in the general case if we use Fibonacci heaps in the implementation of the algorithm or ([E]+[V][W]) in case the maximum transition weight W is small using the algorithm in an article by Ahuja. Faster algorithm for the shortest path problems.
Also, in case the transducer is acyclic, one can use a specific minimization algorithm with linear. time complexity. Therefore, the overall complexity of the minimization algorithm for a subsequential transducer is 0 ([V]+[E]) in case T is acyclic and 0 ([E]log [V]) in the general case. Thus, its complexity is always as good as that of classical automata minimization.
FIGS. 7, 8 and 9 illustrate the minimization process. β1 in FIG. 7 represents a subsequential string to weight transducer. Notice that the size of β1 cannot be reduced using the automata minimization. γ1 in FIG. 8 represents the transducer obtained by pushing, and δ1 in FIG. 9 is a minimal transducer realizing the same function as β1 in the tropical semiring. In particular, the minimal transducer δ1 shown in FIG. 9 is obtained from the transducer γ1 shown in FIG. 8 by collapsing states having identical output transitions, i.e., transitions leaving the states and with the same input label and weight, into a single state. As shown in FIGS. 8 and 9, the states 2 and 4 of the transducer γ1 shown in FIG. 8 have single output transistions labeled "c" and having a weight of "0". Thus, the states 2 and 4 of the transducer γ1 shown in FIG. 8 are collapsed into the single state 2 of the transducer γ1 shown in FIG. 9. Similarly the states 3 and 5 of the transducer γ1 shown in FIG. 8 each have a first output transition labeled "d" and having a weight of "6" and a second output transition labeled "e" and having a weight of "0". Thus, the states 3 and 5 of the transducer γ1 shown in FIG. 8 are collapsed into the single state 3 of the transducer δ1 shown in FIG. 9.
The transducer obtained by this algorithm and defined in the proof of the existence of a minimal subsequential transducer computting the subsequential function S has the minimal number of states. One can ask whether there exists a -subsequential transducer with the minimal number of transitions and computing the same function as a given subsequential transducer T. The following theorem brings a specific answer to this question.
A minimal subsequential transducer has also the minimal number of transitions among all subsequential transducers realizing the same function. This generalizes the analogous theorem which holds in the case of automata. For example, let T be a subsequential transducer with the minimal number of transitions. Clearly, pushing does not change the number of transitions of T and the automaton minimization which consists in merging equivalent states reduces or does not change this number. Thus, the number of transitions of the minimal transducer of T as previously defined is less or equal to that of T.
Given two subsequential transducers, one might wish to test their equality. The following theorem addresses this question.
Let A be a nondeterministic automaton. Then the automaton A′=(Q′, i′, F′, Σ, δ′) obtained by reversing A, applying determinization, rereversing the obtained automaton and determinizing it is the minimal deterministic automaton equivalent to A.
A rational power series S can be stated as bisubsequential when S is subsequential and the power series SR=ΣweΣ*(S, wR) w is also subsequential. However, not all subsequential transducers are bisubsequential. FIG. 10 shows a transducer representing a power series S that is not bisubsequential. S is such that:
The transducer of FIG. 10 is subsequential so S is subsequential. But the reverse SR is not because it does not have bounded variation. Indeed, since:
We have:
One can give a characterization of bisubsequential power series defined on the tropical semiring in a way similar to that of string-to-string transducers. In particular, the previous sections shows that S is bisubsequential if and only if S and SR have bounded variation.
Similarly bideterminizable transducers are defined as the transducers T also defined on the tropical semiring admitting two applications of determinization in the following way:
1. The reverse of T,TR can be determinized. We denote by det(TR) the resulting transducer.
2. The reverse of det(TR), [det(TR)]R can also be determinized. We denote by det([det(TR)]R) the resulting transducer.
In this definition, it is assumed that the reverse operation is performed simply by reversing the direction of the transitions and exchanging initial and final states. Given this definition, we can present the extension of the use of determinization algorithm for power series as minimization tool for bideterminizable transducers.
If T be a bideterminizable transducer defined on the tropical semiting, then the transducer det ([det (TR)]R) obtained by reversing T, applying determinization, rereversing the obtained transducer and determinizing it is a minimal subsequential transducer equivalent to T.
T can be denoted by:
T′=(Q′,i′,F′,Σ,δ′,σ′,λ′,ρ′) det([det(T R)]R)
the transducer obtained from T by pushing.
The double reverse and determinization algorithms clearly do not change the function T realizes. So T′ is a subsequential transducer equivalent to T. Then it is necessary to show that T′ is minimal. This is equivalent to showing that T″ is minimal since T′ and T″ have the same number of states. T1 is the result of a determinization, hence it is a trim subsequential transducer. It can be shown that T′=det (T1 R) is minimal if T1 is a trim subsequential transducer. T is not required to be subsequential.
Let S1 and S2 be two states of T″ equivalent in the sense of automata. It can be shown that S1=S2, namely that no two distinct states of T″ can be merged. This will prove that T″ is minimal. Since pushing only affects the output labels, T′ and T″ have the same set of states: Q′=Q″. Hence S1 and S2 are also states of T′. The states of T′ can be viewed as weighted subsets whose state elements belong to T1, because T′ is obtained by determinization of TR 1.
Let (q,c) εQ1 x , be a pair of the subset S1. Since T1 is trim there exists ωεΣ* such that δ1(i1,ω)=q, so δ′(S1, ω) εF′. Since S1 and S2 are equivalent, we also have: δ′ (S2,ω)εF′. Since T1 is subsequential, there exists only one state of T1 R admitting a path labeled with ω to i1, that state is q. Thus, qεS2. Therefore any state q member of a pair of S1 is also member of a pair of S2. By symmetry the reverse is also true. Thus exactly the same states are members of the pairs of S1 and S2. There exists k≧0 such that:
Weights are also the same in S1 and S2. Let Πj, (0≧j≧k), be the set of strings labeling the paths from i1 to qi in T1. σ1(i1,ω) is the weight output corresponding to a string ωεΠj. Consider the accumulated weights cij, 1≦i≦2,0≦j≦k, in determinization of TR 1. Each c1j for instance corresponds to the weight not yet output in the paths reach S1. It needs to be added to the weights of any path from qj εS1 to a final state in rev(T1). In other terms, the determinization algorithm will assign the weight c1j+σ1(i1,ω)+λ1 to a path labeled with ωR reaching a final state of T′ from S1. T″ is obtained by pushing from T′. Therefore, the weight of such a path in T″ is:
Similarly, the weight of a path labeled with the same string considered from S2 is:
Since S1 and S2 are equivalent in T″ the weights of the paths from S1 or S2 to F′ are equal. Thus, ∀ωεπj, ∀jε[0,k],
In the determinization section, the minimum weight of the pairs of any subset is 0. Therefore, ∀jε[0,k], c1j=c2j and S2=S1.
FIGS. 11-13 illustrate the minimization of string to weight transducers using the determinization algorithm. The transducer β2 of FIG. 11 is obtained from that of FIG. 7, β1, by reversing it. The application of determinization to β2 results in β3 as shown in FIG. 12. Notice that since β1 is subsequential, according to the theorem the transducer β3 is minimal too. β3 is then reversed and determinized. The resulting transducer β4 in FIG. 13 is minimal and equivalent to β1. One can compare the transducer β4 to the transducer of FIG. 9, δ1. Both are minimal and realize the same function. δ1 provides output weights as soon as possible. It can be obtained from β4 by pushing.
6. Application to Speech Recognition
In the previous sections we gave a theoretical description of the determinization and minimization algorithms for string to weight transducers. Here we indicate their use in practice by describing applications of the algorithms for speech recognition.
String to weight transducers are found at several steps of speech recognition. Phone lattices, language models, and word lattices are typically represented by such transducers. Weights in these graphs correspond to negative logarithms of probabilities. Therefore, they are added along a path. For a given string there might be many different paths in a transducer. The minimum of the total weights of these paths is only considered as relevant information. Thus, the main operations involved in the interpretation of these transducers are addition and min, which are those of the tropical semirings. Thus the algorithms we defined in the previous sections apply to speech recognition.
In the preferred embodiment of the present invention, word lattices are obtained by combining distributions over acoustic observations with acoustic models including context dependency restrictions, combined with pronunciation dictionaries and language models. For a given utterance, the word lattice obtained in such a way contains many paths labeled with the possible sentences and their probabilities. These lattices can be searched to find the most probable sentences which correspond to the best paths, the paths with the smallest weights.
FIG. 14 corresponds to a typical word lattice W1 obtained in speech recognition. It corresponds to the following utterance: "Which flights leave Detroit and arrive at Saint-Petersburg around nine a.m.?" Clearly the lattice is complex and contains much redundancy. Many sentences are repeated in the lattice with different weights. It contains about 83 million paths. Usually it is not enough to consider the best path. One needs to correct the best path approximation by considering the n best paths, where the value of n depends on the task considered. Notice that in case n is very large one would need to consider all these 83 million paths. The transducer contains 106 states and 359 transitions. Determinization applies to this lattice. The resulting transducer W2 as shown in FIG. 15 is sparser. Recall that it is equivalent to W1. It realizes exactly the same function mapping strings to weights. For a given sentence s recognized by W1 there are many different paths with different total weights. W2 contains a path labeled with s and with a total weight equal to the minimum of the weights of the paths of W1. No pruning, heuristics or approximation has been used here. The lattice W2 only contains 18 paths. It is not hard to realize that the search stage in speech recognition is greatly simplified when applied to W2 rather than W1. W2 admits 38 states and 51 transitions.
The transducer W2 can still be minimized. The minimization algorithm described in the previous section leads to the transducer W3 as shown in FIG. 16. It contains 25 states and 33 transitions and of course the same number of paths as W2, 18. The effect of minimization appears as less important. This is because determinization includes here a large part of the minimization by reducing the size of the first lattice. This can be explained by the degree of non-determinism of word lattices such as W1. Many states can be reached by the same set of strings. These states are grouped into a single subset during determinization.
Also the complexity of determinization is exponential in general, but in the case of the lattices considered in speech recognition, this is not the case. A more specific determinization can be used in the cases very often encountered in natural language processing where the graph admits a loop at the initial state over the elements of the alphabet. Since they contain much redundancy the resulting lattice is smaller than the initial. In fact, the time complexity of determinization can be expressed in terms of the initial and resulting lattices WI1 and W2 by O|JA| log |A|(|W1||W2|)2), where |W1| and |W2 denote the sizes of W1 and W2. Clearly if we restrict determinization to the cases where |W2|≦|W1| its complexity is polynomial in terms of the size of the initial transducer |W1|. The same remark applies to the space complexity of the algorithm. In practice the algorithm appears to be very efficient. As an example, it takes about 0.1s on a Silicon Graphics (indy 100 MHZ Processor, 64 Mb RAM; The main part of this time corresponds to I/O's and is therefore independent of the algorithm.) to determinize the transducer W1 of FIG. 14.
Determinization makes the use of lattices much faster. Since at any state there exists at most one transition labeled with the word considered, finding the weight associated with a sentence does not depend on the size of the lattice. The time and space complexity of such an operation is simply linear in the size of the sentence. When dealing with large tasks, most speech recognition systems use a rescoring method. This consists in first using a poor acoustic or grammar model to produce a word lattice, and then to reuse this word lattice with a more sophisticated model. The size of the word lattice is then a critical parameter in time and space efficient of the system. The determinization and minimization algorithms we presented allow one to considerably reduce the size of such word lattices as seen in the examples that experimented both determinization and minimization algorithms in the ATIS task. The table in FIG. 17 illustrates these results. It shows these algorithms to be very efficient in reducing the redundancy of speech networks in this task. The reduction is also illustrated in the exemplary ATIS task as follows:
Example of word lattice in the ATIS task.
States: 187→37
Transitions: 993→59
Paths: >232→6993
The number of paths of the word lattice before determinization was larger than that of the largest integer representable with 32 bits machines. We also experimented the minimization algorithm by applying it to several word lattices obtained in the NAB task. These lattices were already detesrminized. The table in FIG. 18 shows the average reduction factors we obtained when using the minimization algorithms with several deterministic lattices obtained for utterances of the NAB task. The reduction factors help to measure the gain of minimization alone since the lattices are already deterministic. The figures of the following example correspond to a typical case. Here is an example of reduction we obtained.
Example of word lattice in NAB task.
Transitions: 108211→37563
States: 10407→2553
An important characteristic of the determinization algorithm is that it can be used on the-fly. Indeed, the determinization algorithm is such that given a subset representing state of the resulting transducer, the definition of the transitions leaving that state only depends on that state or equivalently on the underlying subset, and on the transducer to determinize. We have given an implementation of the determinization which allows one both to completely expand the result or to expand it on demand. Arcs leaving state of the determinized transducer are expanded only if needed. This characteristic of the implementation is important. It can then be used for instance at any step in on-the-fly cascade of composition of transducers in speech recognition to expand only the necessary part of a lattice or transducer. One of the essential implications of the implementation is that it contributes to saving space during the search stage. It is also very useful in speeding up the n-best decoder in speech recognition.
It will be understood that the foregoing is only illustrative of the principles of the invention and that various modifications can be made by those skilled in the art without departing from the scope and spirit of the invention. For example, the determinization and minimization algorithms for string to weight transducers have other applications in speech processing. Many new experiments can be done using these algorithms at different stages of the recognition. They might lead to reshape some of the methods used in this field in particular by providing a new success of the theory of automata and transducers.
We briefly presented the theoretical bases, algorithmic tools and the practical use of set of devices which seem to fit the complexity of language and provide efficiency space and time. It helps to describe the possibilities they offer and to guide algorithmic choices. The notion of determinization can be generalized to that of ε-determinization, for instance, requiring more general algorithms. Other extensions of sequential transducers such as poly-subsequential transducers can be considered. New characterizations of rational function in terms of groups could shed new light on some aspects of the theory of finite transducers. The generalization of the operations in the preferred embodiment of the invention is based on that of the notions of semirings and power series.
Sequential transducers admit very efficient algorithms. Sequential machines lead to useful algorithms in many other areas of computational linguistics. In particular, subsequential power series allow one to achieve efficient results in indexation of natural language texts. Furthermore more precision in acoustic modeling, finer language models, fine and large lexicon grammars, a larger vocabulary will lead in the near future to networks of much larger sizes in speech recognition. The determinization and minimization algorithms may limit the size of these networks while keeping their time efficiency. These algorithms also apply to text-to-speech synthesis. In fact, the same operations of composition of transducers and perhaps more important size issues can be found in this field. Other specific example of possible uses of the invention include its application in optical character recognition ("OCR"), sampling of genes or biological samples, machine translation (e.g., speech-to-speech of text-to-text), text-to-speech synthesis, handwriting recognition search engine in worldwide web and even stability control of an aircraft.
|Cited Patent
|Filing date
|Publication date
|28 Oct 1994
|27 Feb 1996
|Matsushita Electric Industrial Co., Ltd.
|Constructing method of finite-state machine performing transitions according to a partial type of success function and a failure function
|8 Jun 1994
|14 Jan 1997
|Xerox Corporation
|Finite-state transduction of related word forms for text indexing and retrieval
|John R. Deller et al., "Discrete-Time Processing of Speech Signals", Prentice Hall, 1993 pp. 754-755 and 754.
|Mohri "On Some Applications of Finite-State Automata Theory to Natural Language Processing" May 9, 1995, pp. 1-17.*
|Wayne Wolf, "An Algorithm for Nearly-Minimal Collapsing of Finite-State Machine Networks", IEEE Comput. Soc. Press, Nov. 15, 1990, pp. 80-83.
|Citing Patent
|Filing date
|Publication date
|23 Feb 2000
|7 Jan 2003
|Canon Kabushiki Kaisha
|Apparatus and method for generating processor usable data from natural language input data
|1 Feb 2000
|1 Jul 2003
|At&T Corp.
|System and methods for optimizing networks of weighted unweighted directed graphs
|2 May 2000
|30 Mar 2004
|Iphrase.Com, Inc.
|Parsing ambiguous grammar
|18 Dec 2000
|13 Sep 2005
|Xerox Corporation
|Method and apparatus for factoring unambiguous finite state transducers
|17 Dec 2001
|24 Jan 2006
|Xl8 Systems, Inc.
|System and method for speech recognition and transcription
|16 Jul 2003
|21 Feb 2006
|Microsoft Corporation
|Method and apparatus for minimizing weighted networks with link and node labels
|12 Nov 1999
|23 May 2006
|Phoenix Solutions, Inc.
|Speech-enabled server for internet website and method
|6 Apr 2001
|14 Nov 2006
|2005 Keel Company, Inc.
|Wireless information retrieval
|7 Jan 2005
|21 Nov 2006
|Phoenix Solutions, Inc.
|Adjustable resource based speech recognition system
|17 Sep 2001
|16 Jan 2007
|Massachusetts Institute Of Technology
|Concatenative speech synthesis using a finite-state transducer
|18 Jul 2002
|20 Feb 2007
|At&T Corp.
|Systems and methods for generating weighted finite-state automata representing grammars
|22 May 2006
|10 Apr 2007
|Phoenix Solutions, Inc.
|Distributed internet based speech recognition system with natural language support
|6 Mar 2002
|24 Apr 2007
|At&T Corp.
|Systems and methods for dynamic re-configurable speech recognition
|1 Oct 2001
|15 May 2007
|At&T Corp.
|System and method for processing speech recognition results
|7 Jan 2005
|29 May 2007
|Phoenix Solutions, Inc.
|Speech recognition system trained with regional speech characteristics
|20 Jun 2002
|3 Jul 2007
|At&T Corp.
|Systems and methods for determining the determinizability of finite-state automata and transducers
|6 Nov 2003
|10 Jul 2007
|International Business Machines Corporation
|Prose feedback in information access system
|7 Jan 2005
|2 Oct 2007
|Phoenix Solutions, Inc
|Speech recognition system interactive agent
|22 Jul 2002
|30 Oct 2007
|At&T Corp.
|Systems and methods for regularly approximating context-free grammars through transformation
|22 Feb 2002
|11 Mar 2008
|International Business Machines Corporation
|Direct navigation for information retrieval
|13 Dec 2002
|18 Mar 2008
|Xerox Corporation
|Method and apparatus for recognizing multiword expressions
|5 Dec 2006
|8 Jul 2008
|At&T Corp.
|Systems and methods for generating weighted finite-state automata representing grammars
|7 Mar 2005
|15 Jul 2008
|Microsoft Corporation
|Method and apparatus for minimizing weighted networks with link and node labels
|13 Mar 2007
|11 Nov 2008
|At&T Corp.
|System and method of performing speech recognition based on a user identifier
|18 Sep 2007
|4 Aug 2009
|Microsoft Corporation
|Speech recognition using a state-and-transition based binary speech grammar with a last transition value
|20 Nov 2006
|12 Jan 2010
|Phoenix Solutions, Inc.
|Adjustable resource based speech recognition system
|3 Dec 2004
|2 Feb 2010
|Phoenix Solutions, Inc.
|System and method for processing sentence based queries
|19 May 2008
|2 Mar 2010
|Phoenix Solutions, Inc.
|Method for processing speech data for a distributed recognition system
|9 Apr 2007
|13 Apr 2010
|Phoenix Solutions, Inc.
|Speech recognition system for client devices having differing computing capabilities
|3 Dec 2004
|20 Apr 2010
|Phoenix Solutions, Inc.
|System and method for natural language processing of query answers
|11 Mar 2008
|20 Apr 2010
|International Business Machines Corporation
|Information retrieval from a collection of data
|18 Sep 2007
|11 May 2010
|At&T Intellectual Property Ii, L.P.
|Systems and methods for regularly approximating context-free grammars through transformation
|29 Aug 2003
|25 May 2010
|Phoenix Solutions, Inc.
|Query engine for processing voice based queries including semantic decoding
|9 Apr 2007
|25 May 2010
|Phoenix Solutions, Inc.
|Internet based speech recognition system with dynamic grammars
|23 Jun 2008
|25 May 2010
|Phoenix Solutions, Inc.
|Speech based query system using semantic decoding
|3 Dec 2004
|1 Jun 2010
|Phoenix Solutions, Inc.
|Partial speech processing device and method for use in distributed systems
|23 Aug 2007
|6 Jul 2010
|International Business Machines Corporation
|System and method for classifying text
|23 Aug 2007
|13 Jul 2010
|International Business Machines Corporation
|Software tool for training and testing a knowledge base
|29 Jun 2007
|24 Aug 2010
|At&T Intellectual Property Ii, L.P.
|Systems and methods for determining the determinizability of finite-state automata and transducers
|24 Jan 2008
|24 Aug 2010
|International Business Machines Corporation
|Direct navigation for information retrieval
|18 Nov 2007
|31 Aug 2010
|Nice Systems, Ltd.
|Method and apparatus for fast search in call-center monitoring
|23 Jun 2006
|9 Nov 2010
|Phoenix Solutions, Inc.
|Network based interactive speech recognition system
|31 Oct 2007
|18 Jan 2011
|Phoenix Solutions, Inc.
|Natural language speech lattice containing semantic variants
|9 Apr 2007
|8 Mar 2011
|At&T Intellectual Property Ii, L.P.
|System and method for processing speech recognition
|31 Oct 2007
|22 Mar 2011
|Phoenix Solutions, Inc.
|Statistical language model trained with semantic variants
|6 Jun 2008
|1 Nov 2011
|At&T Intellectual Property Ii, L.P.
|Systems and methods for generating weighted finite-state automata representing grammars
|9 Sep 2008
|27 Mar 2012
|At&T Intellectual Property Ii, L.P.
|System and method of performing user-specific automatic speech recognition
|16 Feb 2006
|5 Jun 2012
|At&T Intellectual Property Ii, L.P.
|System and method for providing large vocabulary speech processing based on fixed-point arithmetic
|8 Jun 2006
|26 Jun 2012
|Microsoft Corporation
|Uncertainty interval content sensing within communications
|23 Jun 2008
|24 Jul 2012
|Phoenix Solutions, Inc.
|Semantic decoding of user queries
|21 Nov 2002
|31 Jul 2012
|At&T Intellectual Property Ii, L.P.
|Systems and methods for determining the N-best strings
|27 Mar 2002
|16 Oct 2012
|International Business Machines Corporation
|System and method for determining a set of attributes based on content of communications
|14 Feb 2011
|1 Jan 2013
|At&T Intellectual Property Ii, L.P.
|System and method for processing speech recognition
|9 Apr 2007
|8 Jan 2013
|Phoenix Solutions, Inc.
|Method of interacting through speech with a web-connected server
|26 Aug 2004
|12 Mar 2013
|West Corporation
|Method and system to generate finite state grammars using sample phrases
|2 May 2000
|2 Jul 2013
|International Business Machines Corporation
|Database aliasing in information access system
|29 Apr 2004
|23 Jul 2013
|International Business Machines Corporation
|Software tool for training and testing a knowledge base
|30 Jul 2012
|3 Sep 2013
|At&T Intellectual Property Ii, L.P.
|Systems and methods for determining the N-best strings
|28 Oct 2011
|24 Sep 2013
|At&T Intellectual Property Ii, L.P.
|Systems and methods for generating weighted finite-state automata representing grammars
|1 Nov 2012
|24 Sep 2013
|Google Inc.
|Training an automatic speech recognition system using compressed word frequencies
|21 Jan 2013
|8 Oct 2013
|Google Inc.
|Localized speech recognition with offload
|17 Oct 2012
|29 Oct 2013
|Google Inc.
|Multi-stage speaker adaptation
|30 Nov 2012
|29 Oct 2013
|At&T Intellectual Property Ii, L.P.
|System and method for processing speech recognition
|25 Mar 2011
|21 Jan 2014
|Kabushiki Kaisha Toshiba
|Speech translation apparatus, method and program that generates insertion sentence explaining recognized emotion types
|5 Jan 2006
|4 Feb 2014
|International Business Machines Corporation
|Natural language expression in response to a query
|31 Jan 2013
|29 Apr 2014
|West Interactive Corporation Ii
|Method and system to generate finite state grammars using sample phrases
|1 Oct 2007
|24 Jun 2014
|Nuance Communications, Inc.
|Speech recognition system interactive agent
|17 Oct 2012
|12 Aug 2014
|Google Inc.
|Distributed speaker adaptation
|21 Jan 2013
|4 Nov 2014
|Google Inc.
|Localized speech recognition with offload
|26 Jun 2012
|27 Jan 2015
|Kabushiki Kaisha Toshiba
|Automaton determinization method, device, and computer program product that involves a plurality of states and deleting states that are next states to first transitions
|26 Mar 2012
|16 Jun 2015
|At&T Intellectual Property Ii, L.P.
|System and method of performing user-specific automatic speech recognition
|10 Oct 2003
|7 Jul 2015
|Nuance Communications, Inc.
|Distributed real time speech recognition system
|20 Feb 2013
|1 Sep 2015
|Google Inc.
|Minimum bayesian risk methods for automatic speech recognition
|20 Dec 2000
|20 Jun 2002
|Arons Barry M.
|Transcription and reporting system
|16 Feb 2001
|24 Oct 2002
|Russell Dale W.
|Interactive tool for semi-automatic creation of a natural language grammar from a domain model
|30 Sep 2002
|1 Apr 2004
|Wolf Peter P.
|Voice activated music playback system
|13 Dec 2002
|17 Jun 2004
|Xerox Corporation
|Method and apparatus for recognizing multiword expressions
|6 Nov 2003
|8 Jul 2004
|Iphrase.Com, Inc., A Delaware Corporation
|Prose feedback in information access system
|16 Jul 2003
|20 Jan 2005
|Microsoft Corporation
|Method and apparatus for minimizing weighted networks with link and node labels
|7 Jan 2005
|2 Jun 2005
|Bennett Ian M.
|Adjustable resource based speech recognition system
|7 Mar 2005
|7 Jul 2005
|Microsoft Corporation
|Method and apparatus for minimizing weighted networks with link and node labels
|22 May 2006
|7 Sep 2006
|Bennett Ian M
|Distributed Internet Based Speech Recognition System With Natural Language Support
|23 Jun 2006
|19 Oct 2006
|Bennett Ian M
|Network based interactive speech recognition system
|25 Mar 2011
|29 Mar 2012
|Kabushiki Kaisha Toshiba
|Speech translation apparatus, method and program
|14 Aug 2012
|30 May 2013
|Electronics And Telecommunications Research Institute
|Method and system for generating search network for voice recognition
|13 Aug 2012
|13 Feb 2014
|Xerox Corporation
|Solution for max-string problem and translation and transcription systems using same
|31 Dec 2013
|2 Jul 2015
|Google Inc.
|Pruning and label selection in hidden markov model-based ocr
|27 Mar 2003
|17 Mar 2004
|AT&T Corp.
|Systems and methods for determining the N-best strings of an automaton
|U.S. Classification
|International Classification
|Cooperative Classification
|European Classification
|22 Jan 2002
|Certificate of correction
|29 Sep 2004
|Fee payment
Year of fee payment: 4
|18 Sep 2008
|Fee payment
Year of fee payment: 8
|4 Oct 2012
|Fee payment
Year of fee payment: 12


text:
Federal Management Weaknesses Cry Out for Alternatives To Deliver Programs and Services to Indians To Improve Their Quality of Life
CED-78-166: Published: Oct 31, 1978. Publicly Released: Oct 31, 1978.
Additional Materials:
- Full Report:
(202) 512-4800
During the last decade, there has been increasing congressional activity with the goal of improving the quality of life of Indians. Recent GAO reports have shown the need for greater Federal efforts to meet this goal. A Bureau of Indian Affairs Reorganization Task Force concluded in its March 1978 report that a general management crisis pervades the Bureau of Indian Affairs (BIA).
In spite of recommendations by GAO and other groups dealing with Indian affairs, Federal agencies have failed to correct weaknesses in their management of programs and services to Indians. These weaknesses have led to needless suffering by Indians and to increased administrative costs. The following weaknesses were noted in BIA and other Federal programs and services: the need for effective supervision, monitoring, and evaluation of Federal and tribal performance to assure effective use of funds; lack of a defined role for some Federal agencies; the need for training and technical assistance for tribal governments; lack of agency coordination; and shortages of funds and staff.
Matter for Congressional Consideration
Status: Closed
Comments: Please call 202/512-6100 for additional information.
Matter: The Congress should consider the following alternatives for delivering programs and services to Indians: consolidate all federally administered Indian programs and services into a single agency, consolidate Indian programs and services into the Federal agency having primary responsibility for overall Federal program areas, have all Federal agencies funnel their Indian program funds through one agency rather than directly to Indian tribes, or assist tribes in developing the capability to manage all Federal programs and services and provide direct funding through block grants.
Explore the full database of GAO's Open Recommendations »
Sep 23, 2015
Corporate Bankruptcy:Stakeholders Have Mixed Views on Attorneys' Fee Guidelines and Venue Selection for Large Chapter 11 CasesGAO-15-839: Published: Sep 23, 2015. Publicly Released: Sep 23, 2015.
Sep 15, 2015
Confidential Informants:Updates to Policy and Additional Guidance Would Improve Oversight by DOJ and DHS AgenciesGAO-15-807: Published: Sep 15, 2015. Publicly Released: Sep 15, 2015.
Jun 29, 2015
Youth Athletes:Sports Programs' Guidance, Practices, and Policies to Help Prevent and Respond to Sexual AbuseGAO-15-418: Published: May 29, 2015. Publicly Released: Jun 29, 2015.
Jun 19, 2015
Federal Prison System:Justice Could Better Measure Progress Addressing Incarceration ChallengesGAO-15-454: Published: Jun 19, 2015. Publicly Released: Jun 19, 2015.
May 28, 2015
U.S. Parole Commission:Number of Offenders under Its Jurisdiction Has Declined; Transferring Its Jurisdiction for D.C. Offenders Would Pose ChallengesGAO-15-359: Published: May 28, 2015. Publicly Released: May 28, 2015.
Apr 29, 2015
Victims of Child Abuse Act:Further Actions Needed to Ensure Timely Use of Grant Funds and Assess Grantee PerformanceGAO-15-351: Published: Apr 29, 2015. Publicly Released: Apr 29, 2015.
Mar 23, 2015
Department of Justice:Alternative Sources of Funding Are a Key Source of Budgetary Resources and Could Be Better ManagedGAO-15-48: Published: Feb 19, 2015. Publicly Released: Mar 23, 2015.
Mar 16, 2015
Criminal History Records:Additional Actions Could Enhance the Completeness of Records Used For Employment-Related Background ChecksGAO-15-162: Published: Feb 12, 2015. Publicly Released: Mar 16, 2015.
Mar 4, 2015
Whistleblower Protection:Additional Actions Needed to Improve DOJ's Handling of FBI Retaliation ComplaintsGAO-15-343T: Published: Mar 4, 2015. Publicly Released: Mar 4, 2015.
Feb 23, 2015
Whistleblower Protection:Additional Actions Needed to Improve DOJ's Handling of FBI Retaliation ComplaintsGAO-15-112: Published: Jan 23, 2015. Publicly Released: Feb 23, 2015.
Looking for more? Browse all our products here

subset: commoncrawl


text:
|Dptop Computing
|Date added:
|17 December, 2013
|Editor rating:
Easy to use screen saver maker. You can add pictures, movies, flash animation files, background music, text and banners to your screen saver. Furthermore, you can build window standard screen saver file or distributable self installing exe file.Advertisements
Top Screen Saver Maker allows you to add several picture formats, for example, jpeg, bitmaps and others and construct the pictures into beautiful screen saver. The step-by-step instructions is quick plain to use. You can also add password to the screen saver you have made. Additionally, you can also add background music if required to the screen saver.
|Screen Saver Builder, Screen Saver, Screen Saver Maker, Screensaver Build
|Windows , WinME , 2000 , 2003 , 95/98 , Win95 , Win98 , WinNT 4.x , Windows2000 , Windows2003 , XP , WinXP
|PC with Intel or AMD processor
Top DVD Ripper is an easy to use high speed DVD ripping tool. It can backup or convert your favorite DVD movie into almost all popular video formats.You can rip your DVD to iPod, iPhone, AVI, MPEG, WMV, MPEG.Backup your DVD to hard drive easily.
Top RM Converter is a utility to help you convert, split or join RealMedia files. It supports RM or RMVB to AVI, MPEG and WMV.
Top Video Splitter 1.0 is a nice application that enables you to split video files in different fragments. The program is very easy to use.
Top Screensaver Builder is an easy to use screen saver builder. You can add background music and text to your screen saver. With Top Screensaver Builder you can build windows standard SCR files or distributable self-installing executable file.
Top Video Joiner is an fast video joining tool. It supports joining multiple MPEG, AVI-DivX, WMV-ASF and other video file formats. You can join several video files of different formats into one output format.
Top CD Ripper and Converter is, as its name says, a CD Ripper and audio converter. It supports various audio formats including MP3, WMA, WAV, Monkey's Audio (APE), OGG, FLAC, or MusePack(MPC).
Top Video Sound Extractor is a tool to extract audio sound from video files to MP3, WAV, WMA or OGG format. Supported video formats include AVI, MPEG I and II, RealMedia, WMV, ASF, VCD, DVD, QuickTime video formats.
The program has been created as common application for surveillance cross platforms running concurrently with wireless and wired Internet cameras, Television-boards, capture cards, power-line, and USB webcams.
Aplus DVD to MP4 Ripper is design for backup your favorite DVD movie to your computer by converting DVD to AVI, DivX, XviD, VCD, SVCD MPEG1,MPEG2,MPEG4 video files, with almost same quality, but just only 10% size.
This screensaver shows you off the wonderful images of carvings from Longman Grotto, situated in Dazu County in Chongqing, China. The grotto art of Dazu County incorporates elements of Buddhism, Taoism and Confucianism.
Install this screensaver and see the beautiful images of bright fishes on your desktop. They live mostly in the tropical water near the equator where sufficiency of heat and food allows them to be bright and extremely rich in colors.
Install this screensaver and say "hello" to the classical Disney toons characters! You will see on the screen of your PC: Mickey mouse and Minnie mouse, Goofy, Pluto, Donald duck, Daisy, Winnie the Pooh and friends, Beauty and the Beast and friends.
The night time transforms the day city landscape to the totally another scene. The night illumination outlights the historical buildings, skyscrapers, roads, trees, etc. and makes the fairy-tale atmosphere in the well-known places.
Butterflies are the most splendid creatures among other insects. Decorate your desktop with this screensaver on your computer to see the charm of splendid butterflies!
Feel the extremes of sailing in the open sea full of the strong fair wind. The screen saver will show you the calm and dramatic moment of sailing. You will see the views of sailing yachts from the side and from the bird-eye position.
Decorate your screen with this amazing Sail Boats Free screensaver. Let the sail boats of your dreams appear on the screen of your PC. Using this screensaver you will enjoy the amazing and attractive views of sail boats and tall ships.
Decorate your desktop with this amazing screensaver. Look at your screen and explore the enigma while the time is turning over on the old book pages. Look at the clock book and pass through the events of your life!
Lighthouse is the ancient invention that works till nowadays helping to sail in safety. This screensaver will please you eyes with attractive views of different lighthouses in various countries and environments.
Using the Spring Flourish Free screensaver you will see fascinating views of friut and wild trees in blossom. Many of them have unusually beautiful flowers, not so big in size, but rich in colors and amount. Install this screensaver to feel the mood
The program has been created as common application for surveillance cross platforms running concurrently with wireless and wired Internet cameras, Television-boards, capture cards, power-line, and USB webcams.
Aplus DVD to MP4 Ripper is design for backup your favorite DVD movie to your computer by converting DVD to AVI, DivX, XviD, VCD, SVCD MPEG1,MPEG2,MPEG4 video files, with almost same quality, but just only 10% size.
© 2000-2015 Xentrik.Net


text:
Re: [Hybrid] They don't know what is what.... they just strut... what the ****!
Expand Messages
> I was also at Bedrock last night and couldn't believe my luck when IYeah - I'd have been annoyed about that too...least you go the Plumps though
> saw Hybrid were playing in one of the rooms. When I tried to go in,
> some gimp on the door who had trouble putting a sentence together
> said it was VIP only. I was not happy... neither were many other
> Hybrid fans who were hanging around trying to get into the room, all
> looking very disappointed indeed :0( Anyway, I thought sod that and
> went off and lost it for two hours with my mates in the proper breaks
> room! No VIP nonsense with the Plumps... just wicked Plumptastic
> breaks! They rocked it!
> If Ally's right and Hybrid don't have any say in where they playI didn't say that really - Hybrid are booked through their agents...of
course they would turn sown anything they didn't want to do. I can't comment
on why they just played in the VIP room, because I really don't know. i will
try to find out though.
> Errr... Ally... what clubs do you go to? Your local Ritzy? I onlyWhat do you reckon? I usually go to Space, Back2Basics, Cream etc.
> ever wear trainers when I go clubbing. Fabric, Heaven, The End,
> Turnmills have no problems with trainers.
(I've taken a huge liking to Tangled too)
I don't live in london, so don't know what the rules are down there - as I
said before, fair enough if the 'no trainers' rule has been relaxed in
London....it's still in force elseware though.
I've only been to two clubs in London...The Cross, which I liked....and
Fabric, which I thought was probably the worst club ever...but then loads of
people seem to like it, so maybe I went on a bad night.
Your message has been successfully submitted and would be delivered to recipients shortly.