US 8,095,356 B2Grant

Method and apparatus for processing natural language using tape-intersection

Issue Date:2012-01-10

•7 Claims

•18 Drawing Sheets

Abstract

Operations for weighted and non-weighted multi-tape automata are described for use in natural language processing tasks such as morphological analysis, disambiguation, and entity extraction.

Metadata

Assignee

Xerox Corporation

Inventors

Andre Kempe
Franck Guingne
Florent Nicart

Application Information

Application Number:US 12/614,886

Filing Date:2009-11-09

Priority Date:2003-11-14

Art Unit:2626

Classifications

IPC:

G06F17/27

Patent Drawings (18 sheets)

Description

CROSS-REFERENCE TO RELATED APPLICATIONS

[0001] This application is a divisional application of U.S. application Ser. No. 10/849,919, filed May 21, 2004 now U.S. Pat. No. 7,617,091, which claims priority from U.S. Provisional Application No. 60/481,639, filed Nov. 14, 2003, the entire disclosure of which is incorporated herein by reference.

BACKGROUND AND SUMMARY

[0002] The present invention relates to a method an apparatus for processing natural language using operations performed on weighted and non-weighted multi-tape automata.

[0003] Finite state automata (FSAs) are mathematically well defined and offer many practical advantages. They allow for fast processing of input data and are easily modifiable and combinable by well defined operations. Consequently, FSAs are widely used in Natural Language Processing (NLP) as well as many other fields. A general discussion of FSAs is described in Patent Application Publication US 2003/0004705 A1 and in “Finite State Morphology” by Beesley and Karttunen (CSLI Publications, 2003), which are incorporated herein by reference.

[0004] Weighted finite state automata (WFSAs) combine the advantages of ordinary FSAs with the advantages of statistical models, such as Hidden Markov Models (HMMs), and hence have a potentially wider scope of application than FSAs. Weighted multi-tape automata (WMTAs) have yet more advantages. For example, WMTAs permit the separation of different types of information used in NLP (e.g., surface word form, lemma, POS-tag, domain-specific information) over different tapes, and preserve intermediate results of different steps of NLP on different tapes. Operations on WMTAs may be specified to operate on one, several, or all tapes.

[0005] While some basic WMTAs operations, such as union, concatenation, projection, and complementary projection, have been defined for a sub-class of non-weighted multi-tape automata (see for example the publication by Kaplan and Kay, “Regular models of phonological rule systems”, in Computational Linguistics, 20(3):331-378, 1994) and implemented (see for example the publication by Kiraz and Grimley-Evans, “Multi-tape automata for speech and language systems: A prolog implementation”, in D. Woods and S. Yu, editors, Automata Implementation, number 1436 in Lecture Notes in Computer Science, Springer Verlag, Berlin, Germany, 1998), there continues to be a need for improved, simplified, and more efficient operations for processing WMTAs to make use of these advantages in natural language processing.

[0006] In accordance with the invention, there is provided a method and apparatus for using weighted multi-tape automata (WMTAs) in natural language processing (NLP) that includes morphological analysis, part-of-speech (POS) tagging, disambiguation, and entity extraction. In performing NLP, operations are employed that perform cross-product, auto-intersection, and tape-intersection (i.e., single-tape intersection and multi-tape intersection) of automata. Such operations may be performed using transition-wise processing on weighted or non-weighted multi-tape automata.

[0007] In accordance with one aspect of the invention (referred to herein as the “tape-intersection” operation, or single-tape intersection for one tape or multi-tape intersection for a plurality of tapes), there is provided in a system for processing natural language, a method for intersecting tapes of a first multi-tape automaton (MTA) and a second MTA, with each MTA having a plurality of tapes and a plurality of paths. The method includes composing the first MTA and the second MTA by intersecting a first tape of the first MTA with a first tape of the second MTA to produce an output MTA. The first tape of the first MTA and the first tape of the second MTA corresponds to a first intersected tape and a second intersected tape of the output MTA, respectively. At least one of the first and the second intersected tapes from the output MTA is removed while preserving all its other tapes without modification.

[0008] In accordance with another aspect of the invention, there is provided in a system for processing natural language, a method for intersecting tapes of a first multi-tape automaton (MTA) and a second MTA, with each MTA having a plurality of tapes and a plurality of paths. The method includes: (a) computing a cross-product MTA using the first MTA and the second MTA; (b) generating string tuples for paths of the cross-product MTA; (c) for each string tuple generated at (b), evaluating whether the string of a first tape equals the string of a second tape; (d) for each string tuple evaluated at (c) having equal strings at the first and second tapes, retaining the corresponding string tuple in the cross-product MTA; (e) for each string tuple evaluated at (c) having unequal strings at the first and second tapes, restructuring the cross-product MTA to remove the corresponding string tuple; (f) removing redundant strings in the string tuples retained in the cross-product MTA at (d) to produce an output MTA.

[0009] In accordance with yet another aspect of the invention, there is provided in a system for processing natural language, a method for intersecting a first tape of a first multi-tape automaton (MTA) and a second tape of a second MTA, with each MTA having a plurality of tapes and a plurality of paths. The method includes: defining a simulated filter automaton (SFA) that controls how epsilon-transitions are composed along pairs of paths in the first MTA and the second MTA; building an output MTA by: (a) creating an initial state from the initial states of the first MTA, the second MTA, and the SFA; (b) intersecting a selected outgoing transition of the first MTA with a selected outgoing transition of the second MTA, where each outgoing transition having a source state, a target state, and a label; (c) if the label of the first tape of the selected outgoing transition of the first MTA equals the label of the second tape of the selected outgoing transition of the second MTA, creating (i) a transition in the output MTA whose label results from pairing the labels of the selected outgoing transitions, and (ii) a target state corresponding to the target states of the selected outgoing transitions and the initial state of the SFA; (d) if an epsilon transition is encountered on the first tape, creating a transition in the output MTA with a target state that is a function of (i) the target state of the outgoing transition of the first MTA, (ii) the source state of the outgoing transition of the second MTA, and (iii) a first non-initial state of the SFA; (e) if an epsilon transition is encountered on the second tape, creating a transition in the output MTA with a target state that is a function of (i) the source state of the outgoing transition of the first MTA, (ii) the target state of the outgoing transition of the second MTA, and (iii) a second non-initial state of the SFA; and (f) repeating (b)-(e) for each outgoing transition of the first MTA and the second MTA.

[0010] It will be appreciated that the present invention has the following advantages over weighted 1-tape or 2-tape processing of automata because it allows for: (a) the separation of different types of information used in NLP (e.g., surface form, lemma, POS-tag, domain-specific information, etc.) over different tapes; (b) the preservation of some or all intermediate results of various NLP steps on different tapes; and (c) the possibility of defining and implementing contextual replace rules referring to different types of information on different tapes.

BRIEF DESCRIPTION OF THE DRAWINGS

[0011] These and other aspects of the invention will become apparent from the following description read in conjunction with the accompanying drawings wherein the same reference numerals have been applied to like parts and in which:

[0012] FIG. 1 is a flow diagram that sets forth steps for performing an auto-intersection operation;

[0013] FIG. 2 presents two weighted three-tape automata for illustrating an example of the auto-intersection operation;

[0014] FIG. 3 is a flow diagram that sets forth steps for performing a single-tape intersection operation of a first WMTA and a second WMTA;

[0015] FIG. 4 presents two WMTAs for illustrating a simple example of the single-tape intersection operation;

[0016] FIG. 5 sets forth a method in pseudocode for performing a cross-product operation in an embodiment with path alignment;

[0017] FIG. 6 sets forth a first method in pseudocode for performing an auto-intersection operation;

[0018] FIG. 7 presents two automata for illustrating the method for performing the auto-intersection operation set forth in FIG. 6;

[0019] FIG. 8 presents two automata for illustrating an example of the method for performing the auto-intersection operation set forth in FIG. 6 that fails to perform auto-intersection;

[0020] FIG. 9 sets forth a second method in pseudocode for performing an auto-intersection operation;

[0021] FIGS. 10 and 11 each present two automata for illustrating the method for performing the auto-intersection operation set forth in FIG. 9 which results in a WMTA A⁽ⁿ⁾that is regular;

[0022] FIG. 12 presents two automata for illustrating an example of the method for performing the auto-intersection operation set forth in FIG. 9 which results in a WMTA A⁽ⁿ⁾that is not regular;

[0023] FIG. 13 sets forth a first method in pseudocode for performing a single-tape intersection operation;

[0024] FIG. 14 presents Mohri's epsilon-filter A_ε and two automata A₁and A₂;

[0025] FIG. 15 sets forth a method in pseudocode of a second embodiment for performing the single-tape intersection operation;

[0026] FIG. 16 presents an automaton for illustrating an operation for part-of-speech (POS) disambiguation and its use in natural language processing;

[0027] FIG. 17 illustrates one path of the automaton shown in FIG. 16;

[0028] FIG. 18 illustrates the intersection of an arc with a path of a lexicon automaton;

[0029] FIG. 19 illustrates the intersection of a path of a sentence automaton with a path of an HMM automaton;

[0030] FIG. 20 illustrates an example of a (classical) weighted transduction cascade; and

[0031] FIG. 21 illustrates an example of a weighted transduction cascade using multi-tape intersection;

[0032] FIG. 22 illustrates a general purpose computer system for carrying out natural language processing in accordance with the present invention.

DETAILED DESCRIPTION

Outline of Detailed Description

- [0033] A. Definitions
  - [0034] A.1 Semirings
  - [0035] A.2 Weighted Automata
  - [0036] A.3 Weighted Multi-Tape Automata
- [0037] B. Operations On Multi-Tape Automata
  - [0038] B.1 Pairing and Concatenation
  - [0039] B.2 Projection and Complementary Projection
  - [0040] B.3 Cross-Product
  - [0041] B.4 Auto-Intersection
  - [0042] B.5 Single-Tape Intersection
  - [0043] B.6 Multi-Tape Intersection
  - [0044] B.7 Transition Automata and Transition-Wise Processing
- [0045] C. Methods For Performing MTA Operations
  - [0046] C.1 Cross-Product
    - [0047] C.1.1 Conditions
    - [0048] C.1.2 Path Concatenation Method
    - [0049] C.1.3 Path Alignment Method
    - [0050] C.1.4 Complexity
  - [0051] C.2 Auto-Intersection
    - [0052] C.2.1 Conditions Of First Method
    - [0053] C.2.2 First Method
    - [0054] C.2.3 Example Of First Method
    - [0055] C.2.4 Conditions Of Second Method
    - [0056] C.2.5 Second Method
      - [0057] C.2.5.A Compile Limits
      - [0058] C.2.5.B Construct Auto-Intersection
      - [0059] C.2.5.C Test Regularity
    - [0060] C.2.6 Examples Of Second Method
  - [0061] C.3 Single-Tape Intersection
    - [0062] C.3.1 Conditions
    - [0063] C.3.2 First Embodiment
    - [0064] C.3.3 Mohri's Epsilon-Filter
    - [0065] C.3.4 Second Embodiment
    - [0066] C.3.5 Complexity
  - [0067] C.4 Multi-Tape Intersection
    - [0068] C.4.1 Conditions
    - [0069] C.4.2 Embodiments
    - [0070] C.4.3 Example
- [0071] D. Applications
  - [0072] D.1 General Use
  - [0073] D.2 Building A Lexicon From A Corpus
  - [0074] D.3 Enhancing A Lexicon With Lemmas
  - [0075] D.4 Normalizing A Lexicon
  - [0076] D.5 Using A Lexicon
  - [0077] D.6 Searching For Similarities
  - [0078] D.7 Preserving Intermediate Transduction Results
  - [0079] D.8 Example System
- [0080] E. Miscellaneous

A. Definitions

[0081] This section recites basic definitions of algebraic structures that are used in describing the present invention, such as for “monoid” and “semiring” and “weighted automaton” (which are described in more detail in the following publications, which are incorporated herein by reference, by: Eilenberg, “Automata, Languages, and Machines”, volume A, Academic Press, San Diego, Calif., USA, 1974; and Kuich and Salomaa, “Semirings, Automata, Languages”, Number 5 in EATCS Monographs on Theoretical Computer Science, Springer Verlag, Berlin, Germany, 1986), and for weighted multitape automaton, based on the definitions of multi-tape automaton (which are described in more detail in the following publication, which is incorporated herein by reference, by: Elgot and Mezei, “On relations defined by generalized finite automata”, IBM Journal of Research and Development, 9:47-68, 1965).

A.1 Semirings

[0082] A monoid consists of a set M, an associative binary operation “o” on M, and a neutral element 1 such that 1 o a=a o 1=a for all a ∈ M. A monoid is called commutative iff a o b=b o a for all a, b ∈ M.

[0083] The set K with two binary operations ⊕ (collection) and custom character

(extension) and two elements 0 and 1 is called a semiring, if it satisfies the following properties:

- [0084] (a) <K, ⊕, 0> is a commutative monoid;
- [0085] (b) <K, , 1> is a monoid;
- [0086] (c) is left-distributive and right-distributive over ⊕:
  a (b ⊕ c)=(a b) ⊕ (a c), (a ⊕ b) c=(a c) ⊕ (b c), ∀a, b, c ∈K;
- [0087] (d) 0 is an annihilator for : 0 a=a 0= 0, ∀a∈K.

[0088] A generic semiring custom character

is denoted as <K, ⊕, custom character

, 0, 1>.

[0089] Some methods for processing automata require semirings to have specific properties. Composition, for example, requires a semiring to be commutative (which is described in more detail in the following publications, incorporated herein by reference, by: Pereira and Riley, “Speech recognition by composition of weighted finite automata”, in Emmanuel Roche and Yves Schabes, editors, Finite-State Language Processing, MIT Press, Cambridge, Mass., USA, pages 431-453, 1997; and Mohri, Pereira, and Riley, “A rational design for a weighted finite-state transducer library”, Lecture Notes in Computer Science, 1436:144-158, 1998), and e (i.e., epsilon) removal requires it to be k-closed (which is described in more detail in the following publication incorporated herein by reference by: Mohri, “Generic epsilon-removal and input epsilon-normalization algorithms for weighted transducers”, International Journal of Foundations of Computer Science, 13(1):129-143, 2002). These properties are defined as follows:

- [0090] (a) commutativity: a b=b a, ∀a, b ∈K; and
- [0091] (b) k-closedness:

[0092]

\underset{n = 0}{\overset{k + 1}{\oplus}} a^{n} = \underset{n = 0}{\overset{k}{\oplus}} a^{n}, \forall a \in K .

[0093] The following well-known examples are all commutative semirings:

- [0094] (a) <IB, +, ×, 0, 1>: boolean semiring, with IB={0, 1} and 1+1=1;
- [0095] (b) <IN, +, ×, 0, 1>: integer semiring with the usual addition and multiplication;
- [0096] (c) <IR⁺, +, ×, 0, 1>: real positive sum times semiring;
- [0097] (d) < IR⁺, min, +, ∞, 0>: a real tropical semiring where IR⁺ denotes IR⁺∪{∞}.

[0098] A number of methods for processing automata require semirings to be equipped with an order or partial order denoted by < custom character

. Each idempotent semiring custom character

(i.e., ∀a∈ custom character

: a ⊕ a=a) has a natural partial order defined by a < custom character

a ⊕ b=a. In the above examples, the boolean and the real tropical semiring are idempotent, and hence have a natural partial order.

A.2 Weighted Automata

[0099] A weighted automaton A over a semiring custom character

is defined as a six-tuple:
A=_def custom character

Σ, Q, I, F, E, custom character

with:

- [0100] Σ being a finite alphabet
- [0101] Q the finite set of states
- [0102] I ⊂ Q the set of initial states
- [0103] F ⊂ Q the set of final states
- [0104] E ⊂ Q×(Σ∪{ε})×Q the finite set of transitions and
- [0105] =K, 0, 1, ⊕, the semiring

[0106] For any state q∈Q, there is defined:

- [0107] λ(q) λ: I→ the initial weight function (with λ(q)= 0, ∀q∉I)
- [0108] (q) : F→ the final weight function (with (q)= 0, ∀q∉F)
- [0109] E(q)={e|p(e)=q} the finite set of out-going transitions
  and for any transition e∈E, e=<p, , w, n>, there is defined:
- [0110] p(e) p: E→Q the source state
- [0111] (e) : E→Σ∪{ε} the label (with ε being the empty string)
- [0112] w(e) w: E→ the weight (with w(e)≠ 0, ∀e∈E)
- [0113] n(e) n: E→Q the target state

[0114] A path π of length r=|π| is a sequence of transitions e₁e₂. . . e_rsuch that n(e_i)=p(e_i+1) for all i∈[[1, r−1]]. A path is said to be successful iff p(e₁)∈I and n(e_r)∈F. In the following description only successful paths are considered. The label, custom character

(π), of any successful path π equals the concatenation of the labels of its transitions:
custom character

(π)=

(e₁)

(e₂) . . . custom character

(e_r)
and its “weight” or “accepting weight” w(π) is:

[0115]

w (π) = λ (p (e_{1})) \otimes (\underset{j = 〚 1, l 〛}{\otimes} w (e_{j})) \otimes (n (e_{r}))

[0116] Π(s) denotes the (possibly infinite) set of successful paths of A and Π(s) denotes the (possibly infinite) set of successful paths for the string s:
Π(s)={π|∀π ∈ Π(A), s= custom character

(π) }

[0117]

(A) is defined as the language of A. It is the (possibly infinite) set of strings s having successful paths in A:
custom character

(A)={

(π)|π ∈ Π(A) }

[0118] The accepting weight for any string s∈ custom character

(A) is defined by

[0119]

w (s) = \underset{π \in Π (s)}{\oplus} w (π)

A.3 Weighted Multi-Tape Automata

[0120] In analogy to a weighted automaton, a weighted multi-tape automaton (WMTA), also called weighted n-tape automaton, over a semiring custom character

is defined as a six-tuple:
A⁽ⁿ⁾=_def custom character

Σ, Q, I, F, E⁽ⁿ⁾, custom character

with Σ, Q, I, F, and custom character

being defined as above in section A.2, and with:

- [0121] E⁽ⁿ⁾Q×(Σ∪{ε})ⁿ×Q
- [0122] n
  being the finite set of n-tape transitions and the arity, i.e., the number of tapes in A

[0123] Most of the definitions given for weighted automata are also valid for WMTAs, except that each transition e⁽ⁿ⁾∈ E^(e)is labeled with:

- [0124] (e⁽ⁿ⁾) : E⁽ⁿ⁾→(Σ∪{ε})ⁿan n-tuple of symbols

[0125] If all symbols σ ∈(Σ∪{ε}) of a tuple are equal, the short-hand notation σ⁽ⁿ⁾may be used on the terminal symbol. For example:
α⁽³⁾= custom character

α, α, α

ε⁽²⁾=

ε, ε

[0126] The label of a successful path π⁽ⁿ⁾of length r=|π⁽ⁿ⁾| equals the concatenation of the labels of its transitions, all of which must have the same arity n:
custom character

(π⁽ⁿ⁾)=

(e₁⁽ⁿ⁾)

(e₂⁽ⁿ⁾) . . . custom character

(e_r⁽ⁿ⁾)
which is an n-tuple of strings:
custom character

(π⁽ⁿ⁾)=s⁽ⁿ⁾= custom character

s₁, s₂, . . . , s_n custom character

where each string s_jis a concatenation of the j-th element of all custom character

(e_i⁽ⁿ⁾) of π⁽ⁿ⁾(with i∈[[1,r]]). In anticipation of the projection operation, custom character

( ), (defined in section B.2) this can be expressed as:
s_j= custom character

(

(π⁽ⁿ⁾))=

(

(e₁⁽ⁿ⁾))

(

(e₂⁽ⁿ⁾)) . . . custom character

(

(e_r⁽ⁿ⁾))

[0127] The symbols on e⁽ⁿ⁾are not “bound” to each other. For example, the string triple s⁽ⁿ⁾=<aaa, bb, ccc> can be encoded, among others, by any of the following sequences of transitions: (a:b:c) (a:b:c) (a:ε:c) or (a:b:c) (a:ε:c) (a:b:c) or (ε:ε:c) (a:b:c) (a:b:c) (a:ε:ε), etc.

[0128] Π(s) denotes the (possibly infinite) set of successful paths for the n-tuple of strings s⁽ⁿ⁾:
Π(s⁽ⁿ⁾)={π⁽ⁿ⁾|∀π⁽ⁿ⁾∈Π(A⁽ⁿ⁾), s⁽ⁿ⁾= custom character

(π⁽ⁿ⁾)}

[0129]

(A⁽ⁿ⁾) is called the n-tape language of A⁽ⁿ⁾(which may also be referred to as a relation of arity(n)). It is the (possibly infinite) set of n-tuples of strings s⁽ⁿ⁾having successful paths in A⁽ⁿ⁾:
custom character

(A⁽ⁿ⁾)={

⁽ⁿ⁾|

⁽ⁿ⁾=

(π⁽ⁿ⁾), ∀π⁽ⁿ⁾∈Π(A⁽ⁿ⁾)}

[0130] The accepting weight for any n-tuple of strings s⁽ⁿ⁾∈ custom character

(A⁽ⁿ⁾) is defined by:

[0131]

w (s^{(n)}) = \underset{π^{(n)} \in Π (s^{(n)})}{\oplus} w (π^{(n)})

[0132] It is possible to define an arbitrary weighted relation between the different tapes of custom character

(A⁽ⁿ⁾). For example, custom character

(A⁽²⁾) of the weighted transducer (i.e., two-tape automata) A⁽²⁾is usually considered as a weighted relation between its two tapes, custom character

(

(A⁽²⁾) and custom character

(

(A⁽²⁾)). One of the two tapes is considered to be the input tape, the other as the output tape.

B. Operations on Multi-Tape Automata

[0133] All operations defined in this section are defined on symbol tuples, string tuples, or n-tape languages, taking their accepting weights into account. Whenever these operations are used on transitions, paths, or automata, they are actually applied to their labels or languages respectively. For example, the binary operation ö on two automata, A₁⁽ⁿ⁾ö A₂⁽ⁿ⁾, actually means custom character

(A₁⁽ⁿ⁾ö A₂⁽ⁿ⁾)= custom character

(A₁⁽ⁿ⁾) ö

(A₂⁽ⁿ⁾), and the unary operation {dot over (o)} on one automaton, {dot over (o)} A⁽ⁿ⁾, actually means custom character

({dot over (o)} A⁽ⁿ⁾)={dot over (o)} custom character

(A⁽ⁿ⁾).

B.1 Pairing and Concatenation

[0134] The pairing of two string tuples, s⁽ⁿ⁾:v^(m)=u^(n+m), and its accepting weight is defined as:
custom character

s₁, . . . , s_n custom character

v₁, . . . , v_m custom character

=_def

s₁, . . . , s_n, v₁, . . . , v_m custom character

s₁, . . . , s_n custom character

v₁, . . . , v_m custom character

)=_defw(

s₁, . . . , s_n custom character

)

v₁, . . . , v_m custom character

)

[0135] 1-tuples of strings are not distinguished herein from strings, and hence, instead of writing s⁽¹⁾:v⁽¹⁾or <s>:<v>, s:v is simply written. If strings contain only one symbol σ∈(Σ∪ε), they are not distinguished from the strings and their only symbol, and instead the pairing σ₁:σ₂is written.

[0136] Pairing is associative:
s₁⁽ⁿ¹⁾:s₂⁽ⁿ²⁾:s₃⁽ⁿ³⁾=(s₁⁽ⁿ¹⁾:s₂⁽ⁿ²⁾:s₃⁽ⁿ³⁾=s₁⁽ⁿ¹⁾:(s₂⁽ⁿ²⁾:s₃⁽ⁿ³⁾)=sⁿ¹⁺ⁿ²⁺ⁿ³⁾

[0137] The concatenation of two sting tuples of equal arity, s⁽ⁿ⁾v⁽ⁿ⁾=u⁽ⁿ⁾, and its accepting weight are defined as:
custom character

s₁, . . . , s_n custom character

v₁, . . . , v_n custom character

=_def

s₁v₁, . . . , s_nv_n custom character

s₁, . . . , s_n custom character

v₁, . . . , v_n custom character

)=_defw(

s₁, . . . , s_n custom character

)

v₁, . . . , v_n custom character

)

[0138] Again, 1-tuples of strings are not distinguished herein from strings, and hence, instead of writing s⁽¹⁾v⁽¹⁾or <s><v>, sv is simply written. If strings contain only one symbol σ∈(Σ∪ε), they are not distinguished from the strings and their only symbol, and instead the concatenation σ₁σ₂is written.

[0139] Concatenation is associative:
s₁⁽ⁿ⁾s₂⁽ⁿ⁾s₃⁽ⁿ⁾=(s₁⁽ⁿ⁾s₂⁽ⁿ⁾)s₃⁽ⁿ⁾=s₁⁽ⁿ⁾(s₂⁽ⁿ⁾s₃⁽ⁿ⁾)=s⁽ⁿ⁾

[0140] The relation between pairing and concatenation can be expressed through a matrix of string tuples s_jk⁽ⁿ^j⁾given by:

[0141]

[\begin{matrix} s_{11}^{(n_{1})} & \dots & s_{1 r}^{(n_{1})} \\ ⋮ & ⋮ \\ s_{m 1}^{(n_{m})} & \dots & s_{mr}^{(n_{m})} \end{matrix}]

that are horizontally concatenated and vertically paired:

[0142]

\begin{matrix} s^{(n_{1} + \dots + n_{m})} = (s_{11}^{(n_{1})} \dots s_{1 r}^{(n_{1})}) ⋮ \dots ⋮ (s_{m 1}^{(n_{m})} \dots s_{mr}^{(n_{m})}) \\ = (s_{11}^{(n_{1})} ⋮ \dots ⋮ s_{m 1}^{(n_{m})}) \dots (s_{1 r}^{(n_{1})} ⋮ \dots ⋮ s_{mr}^{(n_{m})}) \end{matrix}

where the equation above does not hold for the accepting weights unless they are defined over a commutative semiring custom character

B.2 Projection and Complementary Projection

[0143] A projection custom character

_{, k, . . .}(s⁽ⁿ⁾) retains only those strings (i.e., tapes) of the tuple s⁽ⁿ⁾that are specified by the indices j, k, . . . ∈[[1,n]],and places them in the specified order. The projection and its accepting weight are defined as:
custom character

_{, k, . . .}( custom character

s₁, . . . , s_n custom character

)=_def

s_j, s_k, . . . custom character

_{, k, . . .}( custom character

s₁, . . . , s_n custom character

))=_defw(

s₁, . . . , s_n custom character

)
where the weights are not modified by the projection. Projection indices can occur in any order and more than once. Thus, the tapes of s⁽ⁿ⁾can, for example, be reversed or duplicated:
custom character

_{, . . . , 1}( custom character

s₁, . . . , s_n custom character

s_n, . . . , s₁ custom character

_{, j,j}(

s₁, . . . , s_n custom character

s_j, s_j, s_j custom character

[0144] The relation between projection and pairing, and between their respective accepting weights is:

[0145]

s^{(n)} = 𝒫_{1} (s^{(n)}) ⋮ \dots ⋮ 𝒫_{n} (s^{(n)})

w (s^{(n)}) \neq w (𝒫_{1} (s^{(n)}) ⋮ \dots ⋮ 𝒫_{n} (s^{(n)})) = \underset{\underset{n times}{︸}}{w (s^{(n)}) \otimes \dots \otimes w (s^{(n)})}

[0146] A complementary projection custom character

_k, . . . (s⁽ⁿ⁾) removes those strings (i.e., tapes) of the tuple s⁽ⁿ⁾that are specified by the indices j, k, . . . , ∈[[1,n]], and preserves all other strings in their original order. Complementary projection and its accepting weight are defined as:
custom character

_{k, . . .}( custom character

s₁, . . . , s_n custom character

)=_def

. . . , s_j−1, s_j+1, . . . , s_k−1, s_k+1, . . . custom character

_{k, . . .}( custom character

s₁, . . . , s_n custom character

))=_defw(

s₁, . . . , s_n custom character

)

[0147] Complimentary projection indices can occur only once, but in any order.

[0148] The projection of an n-tape language is the projection of all its string tuples and complimentary projection of an n-tape language is defined in the same way, respectively as:
custom character

_{, k, . . .}( custom character

)={

_{, k, . . .}(s⁽ⁿ⁾)|∀s⁽ⁿ⁾∈ custom character

}

_{, k, . . .}( custom character

)={

_{, k, . . .}(s⁽ⁿ⁾)|∀s⁽ⁿ⁾∈ custom character

}

B.3 Cross-Product

[0149] The cross-product of two n-tape languages is defined as:
custom character

=_def{s⁽ⁿ⁾:v^(m)|∀s⁽ⁿ⁾∈ custom character

, ∀v^(m)∈ custom character

}

[0150] The accepting weight of each string tuple in custom character

follows from the definition of pairing. The cross product operation is associative.

[0151] A well known example (and special case) is the cross-product of two acceptors (i.e., a 1-tape automata) leading to a transducer (i.e., a 2-tape automaton):
A⁽²⁾=A₁⁽¹⁾×A₂⁽¹⁾
custom character

(A₁⁽¹⁾×A₂⁽¹⁾) ={s:v|∀s ∈ custom character

(A₁⁽¹⁾), ∀v ∈ custom character

(A₂⁽¹⁾)}
w(s:v)=w_A₁(s) custom character

w_A₂(v)

B.4 Auto-Intersection

[0152] Operations for auto-intersection are described in this section. More specifically, this section describes operations for performing auto-intersection on string tuples and languages.

[0153] The auto-intersection I_{j, k}(s⁽ⁿ⁾) on string tuples succeeds, if the two strings s_jand s_kof the tuple s⁽ⁿ⁾=<s₁, . . . , s_n> are equal (with j, k ∈ [[1, n]]), and fails otherwise (⊥). Auto-intersection and its accepting weight are defined as:

[0154]

ℐ_{j, k} (s^{(n)}) =_{def} {\begin{matrix} s^{(n)} & for s_{j} = s_{k} \\ ⊥ & for s_{j} \neq s_{k} \end{matrix} w (ℐ_{j, k} (s^{(n)})) =_{def} {\begin{matrix} w (s^{(n)}) & for s_{j} = s_{k} \\ \overline{0} & for s_{j} \neq s_{k} \end{matrix}

[0155] This means the weight of a successfully auto-intersected string tuple is not modified, whereas the weight of a string tuple where the auto-intersection failed is 0, which corresponds to the invalidation or elimination of that tuple.

[0156] FIG. 1 is a flow diagram that sets forth steps for performing the auto-intersection operation on a first tape and a second tape of a path of a weighted multi-tape automaton. At 102, a string tuple <s₁, . . . , s_n> is generated that has a string s for each of the n tapes of a selected path of the WMTA. At 104, the string s_jof the first tape is compared with the string s_kof the second tape in the string tuple. If at 106, the strings s_jand s_kare equal, then the string tuple is retained in the WMTA at 108; otherwise, the WMTA is restructured to remove the string tuple at 110. At 112, if the last of the paths of the WMTA has been processed, then auto-intersection completes; otherwise, it continues with the next selected path of the WMTA at 102.

[0157] For example, the result of performing the auto-intersection operation I_{j, k}(s⁽ⁿ⁾) on tapes 1 and 3 of the example three-tape WMTA (i.e., s⁽³⁾) shown FIG. 2 fails for the first of its two paths, producing a first string tuple <ax, by, az> (with weight w₁w₂), but succeeds for the second of its two paths, producing a second string tuple <ax, by, ax> (with weight w₁w₃). The final state of the WMTA has weight w₄. Because the strings of tape 1 (i.e., “ax”) and tape 3 (i.e., “az”) of the first string tuple <ax, by, az> are not equal unlike the strings of tape 1 (i.e., “ax”) and tape 3 (i.e., “ax”) of the second string tuple <ax, by, ax>, the WMTA shown in FIG. 2 is restructured to remove the arc x:y:x/w₂of the first path because there are no other successful paths in the WMTA that depend on that arc (i.e., I_{(1, 3)}(s⁽³⁾). The result of the auto-intersection of the two selected tapes 1 and 3 of the WMTA is to filter out all string tuples of the WMTA except for those that have strings that are equal on two selected tapes.

[0158] More generally, auto-intersection of a language, I_{j, k}( custom character

), equals the auto-intersection of all of its string tuples such that only the successfully auto-intersected string tuples are retained, which may be defined as:
custom character

=_def{s⁽ⁿ⁾|s_j=s_k, s⁽ⁿ⁾∈ custom character

}

_k(s⁽ⁿ⁾)|s⁽ⁿ⁾∈ custom character

}

[0159] For example, given a language custom character

(where “*” denotes kleen star):
custom character

a, x, ε

b, y, a

ε, z, b

ab*, xy*z, a*b custom character

,
the results of its auto-intersection I_{1, 3}( custom character

) of tapes 1 and 3 is:
I_{1, 3}( custom character

)={

ab, xyz, ab custom character

}
which means the auto-intersection admits a single iteration through the cycle <b, y, a>* (i.e., “*” takes only the value 1).

B.5 Single-Tape Intersection

[0160] Single-tape intersection of two multi-tape languages, custom character

and

, is based on one single tape j and k from each of their sets of n and m tapes, respectively, and may be defined as:

[0161]

ℒ_{1}^{(n)} ⋂_{j, k} ℒ_{2}^{(m)} =_{def} {\overline{𝒫}}_{n + k} (ℐ_{j, n + k} (ℒ_{1}^{(n)} \times ℒ_{2}^{(m)})) .

[0162] The single-tape intersection operation pairs each string tuple s⁽ⁿ⁾ε custom character

with each string tuple v^(m)∈ custom character

iff s_j=v_k. The resulting language custom character

is defined as:
custom character

={u^(n+m−1)|u^(n+m−1)= custom character

(s⁽ⁿ⁾:v^(m)), s⁽ⁿ⁾∈ custom character

, v^(m)∈ custom character

, s_j=v_k}
with weight w:
w(u^(n+m−1))=w(s⁽ⁿ⁾) custom character

w(v^(m)).

[0163] Single-tape intersection can intuitively be understood as a “composition” of the two languages such that tape j of custom character

is intersected with tape k of custom character

. Tape k, which due to the intersection becomes equal to tape j, is then removed, and all other tapes of both languages are preserved without modification. For example, if one language contains the ordered pair <x, y> and another language contains the ordered pair <y, z>, then composing <x, y> and <y, z>, in that order, results in a language that contains the ordered pair <x, z>, whereas intersecting <x, y> and <y, z>, at tapes 2 and 1 respectively, results in the language that contains the ordered pair <x, y, z>.

[0164] Single-tape intersection is neither associative nor commutative, except for special cases. A first special case of single-tape intersection is the intersection of two acceptors (i.e., 1-tape automata) leading to an acceptor, which may be defined as:

[0165]

A_{1}^{(1)} ⋂ A_{2}^{(1)} = A_{1}^{(1)} ⋂_{1, 1} A_{2}^{(1)} = {\overline{𝒫}}_{2} (ℐ_{1, 2} (A_{1}^{(1)} \times A_{2}^{(1)}))

where the first special case of single-tape intersection has the language custom character

and weight w:
custom character

(A₁⁽¹⁾∩ A₂⁽¹⁾)={s|s ∈ custom character

(A₁), s ∈

(A₂) }
w(s)=w_A₁(s) custom character

w_A₂(s)
and where single-tape intersection has the same language:
custom character

(A₁⁽¹⁾×A₂⁽¹⁾)={ custom character

s₁, s₂

|s₁∈

(A₁), s₂∈

(A₂) }

(

(A₁⁽¹⁾×A₂⁽¹⁾))={ custom character

s, s

|s ∈

(A₁), s ∈

(A₂)}

(

(A₁⁽¹⁾×A₂⁽¹⁾)))={s|s ∈ custom character

(A₁), s ∈

(A₂)}
w(s)=w( custom character

s, s

)=w(

s₁, s₂

)=w_A₁(s)

w_A₂(s)

[0166] A second special case of single-tape intersection is the composition of two transducers (i.e., 2-tape automata) leading to a transducer. The second special case of single-tape intersection requires an additional complementary projection and may be defined as:

[0167]

A_{1}^{(2)} ⋄ A_{2}^{(2)} = {\overline{𝒫}}_{2} (A_{1}^{(2)} ⋂_{2, 1} A_{2}^{(2)}) = {\overline{𝒫}}_{2, 3} (ℐ_{2, 3} (A_{1}^{(2)} \times A_{2}^{(2)})) .

[0168] FIG. 3 is a flow diagram that sets forth steps for performing a single-tape intersection operation of a first WMTA and a second WMTA. At 302, a cross-product WMTA is computed using the first WMTA and the second WMTA. At 304, a string tuple for each path of the cross-product WMTA is generated. At 306 and 316, for each string tuple generated at 304, the string of a first selected tape is compared with the string of a second selected tape at 308. If at 310, the strings compared at 308 are equal, then the corresponding string tuple is retained in the cross-product WMTA at 312; otherwise, the corresponding string tuple is restructured at 314. When strings of the last tuple have been compared at 316, redundant strings retained in the string tuples at 312 are removed in the cross-product WMTA at 318.

[0169] For example, FIG. 4 presents two WMTAs A₁⁽³⁾(with string tuple <ax, by, cz> and weight w₁ custom character

w₂and string tuple <ae, bf, cg> and weight w₁ custom character

w₃) and A₂⁽²⁾(with string tuple <aa, cg> and weight w₄ custom character

w₅) for illustrating a simple example of the single-tape intersection operation

[0170]

A_{1}^{(3)} ⋂_{3, 2} A_{2}^{(2)}

(where the final state of each automaton also has a weight). The resulting cross-product WMTA A₃⁽⁵⁾of the two WMTAs A₁⁽³⁾and A₂⁽²⁾results in the following two string tuples (see 302 FIG. 3): <ax, by, cz, aa, cg> having weight w₁ custom character

w₂

w₄

w₅and <ae, bf, cg, aa, cg> having weight w₁ custom character

w₃

w₄

w₅. In comparing tapes 3 and 5 of the cross-product WMTA A₃⁽⁵⁾(see 308 in FIG. 3), the following strings are compared for each string tuple of the cross-product WMTA A₃⁽⁵⁾, respectively: “cz” and “cg”; and “cg” and “cg”.

[0171] In the example shown in FIG. 4, one set of strings at the selected tapes 3 and 2 are equal, which results in the retention of the string tuple <ae, bf, cg, aa, cg> in the cross-product WMTA A₃⁽⁵⁾(see 312 in FIG. 3). Also in the example, one set of strings at the selected tapes 3 and 5 in the cross-product WMTA A₃⁽⁵⁾are not equal, resulting in the restructuring of the cross-product WMTA to remove the string tuple <ax, by, cz, aa, cg> through auto-intersection as WMTA A₄⁽⁵⁾=I_{(3, 5)}(A₃⁽⁵⁾) (see 314 in FIG. 3). Finally, redundant strings in the string tuple retained in the cross-product WMTA A₄⁽⁵⁾are removed through complementary projection A₄⁽⁴⁾= custom character

(A₄⁽⁵⁾) to result in the simplified string tuple <ae, bf, cg, aa> for the WMTA A₅⁽⁴⁾(see 318 in FIG. 3).

B.6 Multi-Tape Intersection

[0172] Multi-tape intersection of two multi-tape languages, custom character

and

, uses r tapes in each language, and intersects them pair-wise. In other words, multi-tape intersection is an operation that involves intersecting several tapes of a first MTA with the same number of tapes of a second MTA. Multi-tape intersection is a generalization of single-tape intersection, and is defined as:

[0173]

ℒ_{1}^{(n)} ⋂_{\underset{\underset{j_{r}, k_{r}}{\dots}}{j_{1}, k_{1}}} ℒ_{2}^{(m)} =_{def} {\overline{𝒫}}_{n + k_{1}, ..., n + k_{r}} (ℐ_{j_{r}, n + k_{r}} (\dots ℐ_{j_{1}, n + k_{1}} (ℒ_{1}^{(n)} \times ℒ_{2}^{(m)}) \dots))

[0174] The multi-tape intersection operation pairs each string tuple s⁽ⁿ⁾∈ custom character

with each string tuple v^(m)∈ custom character

iff s_j₁=v_k₁until s_j_r=v_k_r. The resulting language custom character

is defined as:
custom character

={u^(n+m−r)|u^(n+m−r)= custom character

_{. . . , n+k}_r(s⁽ⁿ⁾:v^(m)), s⁽ⁿ⁾∈ custom character

, v^(m)∈ custom character

, s_j₁=v_k₁, . . . , s_j_r=v_k_r}
weight w:
w(u^(n+m−r))=w(s⁽ⁿ⁾) custom character

w(v^(m)).

[0175] All tapes k_iof language custom character

that have directly participated in the intersection are afterwards equal to the tapes j_iof custom character

, and are removed. Multi-tape intersection is neither associative nor commutative (except for special cases).

B.7 Transition Automata and Transition-Wise Processing

[0176] A transition automaton custom character

(e) is defined herein as an automaton containing only one single transition e that actually belongs to another automaton A. Any automaton operation is allowed to be performed on custom character

(e), which means that the operation is performed on one single transition of A rather than on A. This can be thought of either as the operation being performed in place (i.e., inside A on one single transition) or as the transition being extracted from A and placed into a new automaton custom character

(e) that participates in an operation whose result is then placed back into A, at the original location of e.

[0177] The concept of transition automata allows a method to be defined where an automaton A is transition-wise processed (i.e., each of its transitions is processed independently through a sequence of automaton operations). In the following example that illustrates the transition automata custom character

(e) being transition-wise processed, e is one transition in a set of transitions E of automata A:

[0178]


	1	for ∀e ∈ E do
	2	(e) ← A₁⁽²⁾⋄ (e) ⋄ A₂⁽²⁾
	3	(e) ← ... (e) ...

C. Methods for Performing MTA Operations

[0179] This section sets forth methods for performing multi-tape operations for automata defined in section B, while referring to the variables and definitions in Table 1. Note that in Table 1 the following variables serve for assigning temporarily additional data to a state q: μ[q], v[q], ξ[q], Θ[q] and x[q].

[0180]

TABLE 1

A_j= Σ_j, Q_j, i_j, F_j, E_j,	Specific (original) weighted automaton
	from which a new weighted automaton A
	is constructed
A = Σ, Q, i, F, E,	New weighted automaton resulting from
	the construction
ν[q] = q₁	State q₁of an original automaton A₁
	assigned to a state q of a new auto-
	maton A
μ[q] = (q₁, q₂)	Pair of states (q₁, q₂) of two ordinal
	automata, A₁and A₂, assigned to a
	state q of a new automaton A
ψ[q] = {umlaut over (q)}	Previous state {umlaut over (q)} in the new automaton
	A on the same path as q (back pointer)
Θ[q] = (q₁, q₂, q_ε)	Triple of states q₁, q₂, q_ε belonging
	to the original automata, A₁and A₂,
	and to a simulated filter automaton,
	A_ε, respectively; assigned to a state
	q of a new automaton A
ξ[q] = (s, u)	Pair of “leftover” substrings (s, u)
	assigned to a state q of a new auto-
	maton A
lcp(s, s′)	Longest common prefix of the strings s
	and s′
_{k, . . .}(x) =	Short-hand notation for the projection
	of the label x
δ(s, u) = \|s\| − \|u\|	Delay between two string (or leftover
	substrings) s and u, where \|s\| is the
	length of string s and \|u\| is the
	length of string u. Example: δ(ξ[q])
χ[q] = (χ₁, χ₂)	Pair of integers assigned to a state
	q, expressing the lengths of two
	strings s and u on different tape of
	the same path ending at q

C.1 Cross-Product

[0181] Generally, this section sets forth two alternate embodiments for performing the cross-product operation defined in section B-3, and more specifically for compiling the cross product of two WMTAs, A₁⁽ⁿ⁾and A₂^(m).

[0182] The first embodiment pairs the label of each transition e₁∈ E₁with ε^(m)(producing custom character

(e₁):ε^(m)), and the label of each transition e₂∈E₂with ε⁽ⁿ⁾(producing ε⁽ⁿ⁾ custom character

(e₂)), and finally concatenates A₁^(n+m)with A₂^(n+m). This operation is referred to herein as “CrossPC (A₁, A₂)” where the suffix “PC” stands for “path concatenation” and can be expressed as:
custom character

(π₁⁽ⁿ⁾:π₂^(m))=( custom character

(e_{1, 1}⁽ⁿ⁾):ε^(m)) . . . ( custom character

(e_{1, α}⁽ⁿ⁾):ε^(m))·(ε⁽ⁿ⁾: custom character

(e_{2, 1}^(m))) . . . (ε⁽ⁿ⁾: custom character

(e_{2, β}^(m))).

[0183] The second embodiment pairs each string tuple of A₁⁽ⁿ⁾with each string tuple of A₂^(m), following the definition in section B-3. This embodiment in actuality pairs each path π₁of A₁⁽ⁿ⁾with each path π₂of A₂^(m)transition-wise, and appends epsilon transitions (i.e., ε-transitions) to the shorter of two paired paths, so that both have equal length. This operation is referred to herein as “CrossPA (A₁, A₂)” where the suffix “PA” stands for “path alignment” and can be expressed as:
custom character

(π₁⁽ⁿ⁾:π₂^(m))=( custom character

(e_{1, 1}⁽ⁿ⁾): custom character

(e_{2, 1}^(m))) . . . ( custom character

(e_{1, α}⁽ⁿ⁾): custom character

(e_{2, α}^(m)))·(ε⁽ⁿ⁾: custom character

(_{2, α+1}^(m))) . . . (ε⁽ⁿ⁾: custom character

(e_{2, β}^(m)))
for α<β, and similarly otherwise.

C.1.1 Conditions

[0184] Both embodiments for performing the cross-product operation operate under the conditions that:

- [0185] (A) the semirings of the two automata A₁⁽ⁿ⁾and A₂^(m)are equal to: =; and
- [0186] (B) the common semiring == is commutative (which holds in the case of CrossPA embodiment only):
  ∀w₁, w₂∈:w₁ w₂=w₂ w₁.

C.1.2 Path Concatenation Method

[0187] A (brute force) method for performing the cross-product operation in accordance with an embodiment, defined as “CrossPC( )”, with path concatenation “PC” may be described as follows in pseudocode:

[0188]


	CROSSPC(A₁⁽ⁿ⁾, A₂^(m)) → A :
	1	A ← Σ₁∪ Σ₂, Q₁∪ Q₂, i₁, F₂, E₁∪ E₂,
	2	for ∀e₁∈ E₁do
	3	(e₁) ← (e₁):ε^(m)
	4	for ∀e₂∈ E₂do
	5	(e₂) ← ε⁽ⁿ⁾: (e₂)
	6	for ∀q ∈ F₁do
	7	E ← E ∪ { q, ε^(n+m), (q), i₂ }
	8	(q) ← 0
	9	return A

[0189] The pseudocode set forth above for cross-product path concatenation (i.e., CrossPC( )) starts with a WMTA A that is equipped with the union of the alphabets (i.e., the union of the state sets of transducers A₁and A₂). The initial state of A equals that of A₁, its set of final states equals that of A₂, and its semiring equal those of A₁and A₂(see line 1). First, the labels of all transitions originally coming from A₁are (post-) paired with ε^(m)-transitions, and the labels of all transitions originally coming from A₂are (pre-) paired with ε⁽ⁿ⁾-transitions. Subsequently, all final states of A₁are connected with the initial state of A₂through ε^(n+m)-transitions. As a result, each string n-tuple of A₁will be physically followed by each string m-tuple of A₂. However, logically those string tuples will be paired since they are on different tapes.

[0190] It will be appreciated by those skilled in the art that the paths of the WMTA A become longer in this embodiment than the other embodiment with path alignment. In addition, it will be appreciated that each transition of A in this embodiment is partially labeled with an epsilon, which may increase the runtime of subsequent operations performed on A. Further it will be appreciated that this embodiment may be readily adapted to operate with non-weighted multi-tape automata (MTAs) by removing the weight custom character

(q) from line 7 and the semiring custom character

from line 1 and by replacing line 8 with “Final(q)←false”, in the pseudocode above for path concatenation (i.e., CrossPC( )).

C.1.3 Path Alignment Method

[0191] FIG. 5 sets forth a second embodiment in pseudocode for performing the cross-product operation with path alignment “PA” (i.e., CrossPA( )). In FIG. 5, the final weight of an undefined state q=⊥ is assumed to be 1: custom character

(⊥)= 1. In the embodiment shown in FIG. 5, the pseudocode starts with a WMTA A whose alphabet is the union of the alphabets of A₁and A₂, whose semiring equals those of A₁and A₂, and that is otherwise empty (see line 1). First, the initial state i of A is created from the initial states A₁and A₂(at line 3), and i is pushed onto the stack (at line 4) which was previously initialized (at line 2). While the stack is not empty, the states q are popped from it to access the states q₁and q₂that are assigned to q through u[q] (see lines 5 and 6).

[0192] Further in the embodiment shown in FIG. 5, if both q₁and q₂are defined (i.e., ≠⊥), each outgoing transition e₁of q₁is paired with each outgoing transition of e₂of q₂(see lines 7 to 9). Also (at line 13), a transition in A is created whose label is the pair custom character

(e₁):

(e₂) and whose target q′ corresponds to the tuple of targets (n(e₁), n(e₂)). If q′ does not exist yet, it is created and pushed onto the stack (see lines 10 to 12).

[0193] In addition in the embodiment shown in FIG. 5 (at lines 14 and 15), if a final state q₁(with custom character

(q₁)≠ 0) in A₁is encountered, the path is followed beyond q₁on an epsilon-transition that exists only locally (i.e., virtually) but not physically in A₁. The target of the resulting transition in A corresponds to the tuple of targets (n(e₁), n(e₂)) with n(e₁) being undefined (=⊥) because e₁does not exist physically (see line 17). If a final state q₂(with custom character

(q₂)≠ 0 in A₂is encountered, it is processed similarly (see lines 20 to 25). It will be appreciated by those skilled in the art that this embodiment may be readily adapted to operate with non-weighted multi-tape automata (MTAs) by removing the weights from lines 13, 19, and 25, and the semiring custom character

from line 1, and the and by replacing line 28 with “Final(q)←Final(q₁) {circumflex over ( )} Final(q₂)”, in the pseudocode shown in FIG. 5.

C.1.4 Complexity

[0194] The space complexity of the (brute-force) cross-product path concatenation embodiment described in section C.1.2 is |Q₁|+|Q₂| (i.e., on the order of O(n)) and its running complexity is |F₁|. In contrast, the space complexity of the cross-product path alignment embodiment described in section C.1.3 is (|Q₁|+1)·(|Q₂|+1) (i.e., on the order of O(n²) and its running complexity is (|E₁|+1)·(|E₂|+1).

C.2 Auto-Intersection

[0195] This section describes two methods for performing the auto-intersection operation defined in section B.4.

C.2.1 Conditions of First Method

[0196] The method described for performing auto-intersection operation in this section operates under the condition that the original automaton A₁⁽ⁿ⁾does not contain cycles labeled only with an epsilon on one and not only with an epsilon on the other of the two tapes involved in the operation. If condition occurs the method will stop without producing a result, rather than attempting to create an infinite number of states. It is assumed this undesirable condition occurs rarely (if at all) in natural language processing applications (see for example FIG. 8).

C.2.2 First Method

[0197] FIG. 6 sets forth a first method in pseudocode for performing the auto-intersection operation (i.e., AutoIntersect( )). Line 1 of the pseudocode begins with a WMTA A whose alphabet and semiring equal those of A₁and that is otherwise empty. To each state q that will be created in A (see line 3), three variables are assigned: (i) v[q]=q₁that indicates the corresponding state q₁in A₁(see line 24), (ii) ψ[q]={umlaut over (q)} that indicates the previous state {umlaut over (q)} in A on the current path (back pointer) (see line 25), and (iii) ξ[q]=(s, u) that states the leftover string s of tape j (yet unmatched in tape k) and leftover string u of tape k (yet unmatched in tape j) (see line 26).

[0198] At lines 3-4 and 20-27, an initial state i in A is created and pushed onto the stack defined at line 2. As long as the stack is not empty, the states q are popped from the stack and each of the outgoing transitions e₁∈E(q) in A with the same label and weight are followed (see line 5). To compile the leftover strings ξ[q′]=(s′, u′) of its target q′=n(e) in A, the leftover strings ξ[q]=(s, u) of its source q=p(e) are concatenated with the j-th and k-th component of its label, custom character

(e₁) and

(e₁), and the longest common prefix of the resulting string s· custom character

(e₁) and u· custom character

(e₁) is removed (see lines 7 and 16-19).

[0199] If both leftover strings s′ and u′ of q′ are non-empty (i.e., ≠ε) then they are incompatible and the path that is being followed is invalid. In this case, the transition e∈E(q) and its target q′ in A are not constructed. If either s′ or u′ is empty (i.e., =ε), then the current path is valid (at least up to this point) (see line 8).

[0200] At line 9, a test is made to determine whether the process will not terminate, which is the case if a cycle in A₁was traversed and the ξ[{circumflex over (q)}] at the beginning of the cycle differs from the ξ[n(e)]=(s′, u′) at its end. In this case the states {circumflex over (q)} and n(e) are not equivalent, and cannot be represented through one state in A, although they correspond to the same state q₁in A₁. In order that the process does not traverse the cycle an infinite number of times and create a new state on each transversal, the process aborts at line 10.

[0201] At line 14 (if the process did not abort at line 10), a transition e in A is constructed. If its target q′=n(e) does not exist yet, it is created and pushed onto the stack at lines 11-13. It will be appreciated by those skilled in the art that this embodiment may be readily adapted to operate with non-weighted multi-tape automata (MTAs) by removing the weight w(e₁) from line 14 and the semiring custom character

from line 1, and by replacing line 22 with “Final(q)←Final(q₁)” and line 23 with “Final(q)←false”, in the pseudocode shown in FIG. 6.

C.2.3 Example of First Method

[0202] FIG. 7 illustrates an example of the first method for performing the auto-intersection operation shown in FIG. 6. In the example shown in FIG. 7, the language of A₁⁽²⁾is the infinite set of string tuples <ab*¹, a*¹b>. Only one of those tuples, namely <ab, ab>, is in the language of the auto-intersection with A⁽²⁾=I_{1, 2}(A₁⁽²⁾)) because all other tuples contain different strings on tapes 1 and 2. In FIG. 7, weights of each WMTA are omitted and dashed states and transitions are not constructed.

[0203] The method described above in section C.2.2 builds first the initial state 0 of A⁽²⁾with v[0]=0, ψ[0]=1, and ξ[0]=(ε, ε). Then the only outgoing transition of the state referenced by v[0] is selected, which is labeled a:ε, and the leftover strings of its target, state 1, is compiled by concatenating ξ[0]=(ε, ε) with the label a:ε. This gives first (a, ε) and then, after removal of the longest comment prefix (ε in this case), ξ[1]=(a, ε). State 1 is created because ξ[1] meets the constrains defined in the method. It is assigned v[1]=1, because it corresponds to state 1 in A₁, ψ[1]=0, because it is (at present) reached from state 0 in A, and ξ[1]=(a, ε). State 1 in A is not final (unlike state 1 in A₁) because ξ[1]≠(ε, ε).

[0204] The remaining strings of state 2 in A result from ξ[1]=(a, ε) and the transition label ε:b, and are ξ[2]=(a, b). State 2 and its incoming transition are not created because ξ[2] does not meet the defined constraints. All other states and transitions are similarly constructed.

[0205] FIG. 8 illustrates an example where the first method for performing the auto-intersection operation shown in FIG. 6 fails to construct the auto-intersection whose language, <a*¹a, aa*¹, x*¹yz*¹>, and is actually not finite-state (see conditions in section C.2.1). The failure condition is met at states 2 and 3 of the new automaton A. In FIG. 8, weights of each WMTA are omitted and dashed states and transitions are not constructed.

C.2.4 Conditions of Second Method

[0206] The second method unlike the first method has no conditions. In accordance with the second method for performing auto-intersection, the second method detects whether the auto-intersection of a given WMTA A₁⁽ⁿ⁾is regular (i.e., whether it can be represented as an automaton). If it is found to be regular, the second method creates a WMTA A=I_{j, k}(A₁⁽ⁿ⁾); otherwise if it is found not to be regular and the complete result cannot be represented by an automaton, the second method creates the automaton A ⊂ I_{j, k}(A₁⁽ⁿ⁾), which is a partial result.

[0207] Briefly, the second method performs auto-intersection by assigning leftover-strings to states using variable ξ[q]=(s, u) and makes use of the concept of delay using variable δ(s, u), which are both defined in Table 1. The variable custom character

[q] defines a pair of integers assigned to a state q, which expresses the lengths of two strings s and u on different tape of the same path in a WMTA ending at q. The concept of delay provides that given a path in a WMTA, the delay of its states q is the difference of lengths of the strings on the tapes j and k up to q. It is expressed as the function δ(s, u)=|s|−|u|, where |s| is the length of string s and |u| is the length of string u.

C.2.5 Second Method

[0208] FIG. 9 sets forth the second method in pseudocode for performing the auto-intersection operation (i.e., AutoIntersect( )). The method is based on the observation that if the auto-intersection A⁽ⁿ⁾=I_{j, k}(A₁⁽ⁿ⁾) of a WMTA A₁⁽ⁿ⁾is regular, the delay will not exceed a limit δ_maxat any state q of A⁽ⁿ⁾. If it is not regular, the delay will exceed any limit, but it is possible to construct a regular part, A_p⁽ⁿ⁾, of the auto-intersection within the limit of δ_maxand a larger regular part, A_p2⁽ⁿ⁾, within a larger limit δ_max2(i.e., A_p⁽ⁿ⁾⊂ A_p2⁽ⁿ⁾⊂ I_{j, k}(A₁⁽ⁿ⁾)).

[0209] By way of overview, the second method set forth in FIG. 9 and described in detail below involves three operations. First, two limits are computed corresponding to delays δ_maxand δ_max2of the auto-intersection (i.e., line 1). The first delay δ_maxis computed by traversing the input automaton and measuring the delays along all its paths. The second delay is computed similar to the first delay while traversing an additional cycle of the input automaton. Next, the auto-intersection of the automaton is constructed using the delay δ_max2(i.e., lines 2-10, where the second limit serves to delimit construction of the automaton). Finally, the constructed automaton is tested for regularity using the delay δ_max(i.e., line 11, where the first limit serves to determine whether the auto-intersection is regular).

C.2.5.A Compile Limits

[0210] In FIG. 9, a maximal delay, δ_max, is compiled. The maximal delay, δ_max, can occur at any point between the two strings custom character

(π) and

(π) on any path π of I_{j, k}(A₁⁽ⁿ⁾) if it is regular. Let custom character

(A₁⁽²⁾)=({ custom character

aa, ε

} ∪ {

ε, aaa

})*, encoded by two cycles (as provided at lines 1 and 27-42), where custom character

(A⁽ⁿ⁾) is the n-tape relation of A⁽ⁿ⁾. To obtain a match between custom character

₁(π) and

₂(π) in A⁽²⁾=I_{1, 2}(A₁⁽²⁾), the first cycle must be traversed three times and the second cycle two times, allowing for any permutation: A⁽²⁾=( custom character

aa, ε

ε, aaa

²∪

aa, ε

ε, aaa

aa, ε

¹∪ . . . )*. This illustrates that in a match between any two cycles of A₁⁽ⁿ⁾, the absolute value of the delay does not exceed δ_cyc={circumflex over (δ)}_cyc·max (1, δ_cy−1), with δ_cycbeing the maximal absolute value of the delay of any cycle (as provided at line 30). For any other kind of match, the difference between the maximal and the minimal delay, {circumflex over (δ)}^maxand {circumflex over (δ)}_min, encountered at any (cyclic or acyclic) path π of A₁⁽ⁿ⁾) is taken into account. Therefore, the absolute value of the delay in A⁽ⁿ⁾does not exceed δ_max=max ({circumflex over (δ)}_max−{circumflex over (δ)}_min, δ_cyc) if I_{j, k}(A₁⁽ⁿ⁾) is regular (as provided at line 31). If it is non-regular, then δ_max, will limit A⁽ⁿ⁾to a regular subset of the auto-intersection, A⁽ⁿ⁾⊂ I_{j, k}(A₁⁽ⁿ⁾).

[0211] Next, a second limit, δ_max2, is compiled that permits, in case of non-regularity, to construct a larger regular subset A⁽ⁿ⁾⊂ I_{j, k}(A₁⁽ⁿ⁾) than δ_maxdoes. Non-regularity can only result from matching cycles in A₁⁽ⁿ⁾. To obtain a larger subset of I_{j, k}(A₁⁽ⁿ⁾), the cycles of A₁⁽ⁿ⁾must be unrolled further until one more match between two cycles is reached. Therefore, δ_max2=δ_max+δ_cyc(as provided at line 32).

C.2.5.B Construct Auto-Intersection

[0212] Construction starts with a WMTA A whose alphabet and semiring equal those of A₁and that is otherwise empty (as provided at line 2). To each state q that will be created in WMTA A, two variables are assigned: (i) v[q]=q₁indicating the corresponding state q₁in A₁; and (ii) ξ[q]=(s, u), which sets forth the leftover string s of tape j (yet unmatched in tape k) and the leftover string u of tape k (yet unmatched in tape j).

[0213] Subsequently, an initial state i in A is created and pushed onto a stack (as provided at lines 4 and 17-26). As long as the stack is not empty, states q are taken from it and each of the outgoing transitions e₁∈E(q₁) of the corresponding state q₁=v[q] in A₁are followed (as provided in lines 5 and 6). A transition e₁in A₁is represented as e∈E(q) in A, with the same label and weight. To compile the leftover strings ξ[q′]=(s′, u′) of its target q′=n(e) in A, the leftover strings ξ[q]=(s, u) of its source q=p(e) are concatenated with the j-th and k-th component of its label, custom character

(e₁) and

(e₁), and the longest common prefix of the resulting strings s· custom character

(e₁) and u· custom character

(e₁) is removed (as provided in lines 7 and 13-16).

[0214] If both leftover strings s′ and u′ of q′ are non-empty (i.e., ≠ε) then they are incompatible and the path that is being followed is invalid. If either s′ or u′ is empty c (i.e., =ε) then the current path is valid (at least up to this point) (as provided in line 8). Only in this case and only if the delay between s′ and u′ does not exceed δ_max2, a transition e in A is constructed corresponding to e₁in A₁(as provided in line 10). If its target q′=n(e) does not exist yet, it is created and pushed onto the stack (as provided in lines 9 and 17-26). The infinite unrolling of cycles is prevented by δ_max2.

C.2.5.C Test Regularity of Auto-Intersection

[0215] Finally, the constructed auto-intersection of the WMTA A is tested for regularity. From the above discussion of δ_maxand δ_max2it follows that if I_{j, k}(A₁⁽ⁿ⁾) is regular then none of the states that are both reachable and coreachable have |δ(ξ[q])|>δ_max. Further, if I_{j, k}(A₁⁽ⁿ⁾) is non-regular then a WMTA A⁽ⁿ⁾built having a δ_max2, is bigger than a WMTA A⁽ⁿ⁾built having δ_max, and hence has states with |δ(ξ[q])|>δ_maxthat are both reachable and coreachable. Since all states of A⁽ⁿ⁾are reachable, due to the manner in which the WMTA A is constructed, it is sufficient to test for their coreachability (as provided at line 11) to know whether the WMTA A is regular (i.e., the delay of WMTA A⁽ⁿ⁾will not exceed a limit δ max at any state q of A⁽ⁿ⁾).

C.2.6 Examples of Second Method

[0216] FIGS. 10 and 11 each present two different automata for illustrating the method for performing the auto-intersection operation set forth in FIG. 9 which results in a WMTA A⁽ⁿ⁾that is regular. In contrast, FIG. 12 presents two automata for illustrating an example of the method for performing the auto-intersection operation set forth in FIG. 9 which results in a WMTA A⁽ⁿ⁾that is not regular. In the FIGS. 10-12, the dashed portions are not constructed by the method set forth in FIG. 9, and the states q in the Figures identified with the arrow custom character

have delay such that |δ(ξ[q])|>δ_max.

[0217] FIG. 10 illustrates the WMTA A₁⁽²⁾and its auto-intersection A(²). In FIG. 10, the WMTA A (²₁) is the infinite set of string tuples { custom character

ab^k, a^kb custom character

|k∈

} (where

is the set of natural numbers). Only one of those tuples, namely custom character

ab, ab

, is in the relation of the auto-intersection A⁽²⁾=I_{1, 2}(A₁⁽²⁾) because all other tuples contain different strings on tape 1 and tape 2. In accordance with the method for performing the auto-intersection operation set forth in FIG. 9, the following four steps are performed (namely, at (1) the limits are computed, at (2)-(3) the auto-intersection is computed, and at (3) the auto-intersection is tested for regularity):
δ_max=δ_max2=1 (1)
custom character

(A₁⁽²⁾)={

ab^k, a^kb custom character

|k ∈

} (2)

((A₁⁽²⁾))= custom character

(A⁽²⁾)={

ab¹, a¹b custom character

} (3)

q∈Q:|δ(ξ[q])|>δ_max→regular (4)

[0218] FIG. 11 illustrates the WMTA A₁⁽³⁾and its auto-intersection A⁽³⁾= custom character

(A₁⁽³⁾), where the state 3 of A⁽²⁾in FIG. 11 identified with the arrow custom character

has a delay such that |δ(ξ[q])|>δ_max. In accordance with the method for performing the auto-intersection operation set forth in FIG. 9, the following four steps are performed (namely, at (1)-(2) the limits are computed, at (3)-(4) the auto-intersection is computed, and at (5) the auto-intersection is tested for regularity):
δ_max=2 (1)
δ_max2=3 (2)
custom character

(A₁⁽³⁾)={

a^k, a, x^ky custom character

|k ∈

} (3)

(A₁⁽³⁾))=

(A⁽³⁾)={

a¹, a, x¹y custom character

} (4)

q∈Q:|δ(ξ[q])|>δ_max custom character

coreachable(q)→regular (5)

[0219] FIG. 12 illustrates the WMTA A₁⁽³⁾and its auto-intersection A⁽³⁾= custom character

(A₁⁽³⁾), where the states 3, 8, and 11 of A⁽²⁾in FIG. 12 identified with the arrow custom character

have a delay such that |δ(ξ[q])|>δ_max. In accordance with the method for performing the auto-intersection operation set forth in FIG. 9, the following four steps are performed (namely, at (1)-(2) the limits are computed, at (3)-(5) the auto-intersection is computed, and at (6) the auto-intersection is tested for regularity):
δ_max=2 (1)
δ_max2=3 (2)
custom character

(A₁⁽³⁾)={

a^ka, aa^h, x^kyz^h custom character

|k, h ∈

} (3)

(A₁⁽³⁾))={ custom character

a^ka, aa^k, x^kyz^k custom character

|k ∈

} (4)

(A₁⁽³⁾)) ⊃ custom character

(A⁽³⁾)={

a^ka, aa^k, x^kyz^k custom character

|k ∈ [[0, 3]]} (5)
∃q∈Q:|δ(ξ[q])|>δ_max custom character

coreachable(q)→non-regular (6)

C.3 Single-Tape Intersection

[0220] This section sets forth two alternate embodiments for performing, in one step, the single-tape intersection operation of two WMTAs A₁⁽ⁿ⁾and A₂^(m)defined in section B.5 above. Instead of first building the cross-product, A₁⁽ⁿ⁾×A₂^(m), and then deleting most of its paths by the auto-intersection, I_{j, n+k}( ) operation defined in section B.4, both embodiments construct only the useful part of the cross-product. However, it will be understood by those skilled in the art that an alternate embodiment follows the definition and performs single-tape intersection in multiple steps.

[0221] The first embodiment is a method for performing single-tape intersection similar to known methods for performing composition, and is not adapted to handle WMTAs that contain epsilons on the intersected tapes, j and k. The first embodiment is referred to herein as IntersectCross(A₁, A₂, j, k), which is defined as:

[0222]

\begin{matrix} IntersectCross (A_{1}, A_{2}, j, k) = ℐ_{j, n + k} (A_{1}^{(n)} \times A_{2}^{(m)}) \\ A_{1}^{(n)} ⋂_{j, k} A_{2}^{(m)} = {\overline{𝒫}}_{n + k} (IntersectCross (A_{1}, A_{2}, j, k)) \end{matrix}

[0223] It will be appreciated by those skilled in the art that the complementary projection, custom character

₍₎, operation defined in section B.2 may be integrated into the first embodiment in order to avoid an additional pass. However, it is kept separate from IntersectCross( ) because IntersectCross( ) may serve also as a building block of another operation where the complementary projection operation must be postponed (e.g., multi-tape intersection).

[0224] The second embodiment simulates the behavior of an epsilon-filter transducer for composing transducers with epsilon-transitions that is disclosed by Mohri, Pereira, and Riley in “A rational design for a weighted finite-state transducers”, published in Lecture Notes in Computer Science, 1436:144-158, 1998, which is incorporated herein by reference and hereinafter referred to as “Mohri's Epsilon-Filter Publication”. The second embodiment is referred to herein as IntersectCrossEps(A₁, A₂, j, k), where the suffix “Eps” expresses its suitability for WMTAs with epsilons on the intersected tapes, j and k.

[0225] Similar to the first embodiment, it will be appreciated by those skilled in the art that the complementary projection, custom character

( ), operation defined in section B.2 may be integrated into the second embodiment in order to avoid an additional pass. However, it is kept separate from IntersectCrossEps( ) because IntersectCrossEps( ) may serve also as a building block of other operations where the complementary projection operation must be postponed or extended (e.g., classical composition and multi-tape intersection).

C.3.1 Conditions

[0226] Both embodiments for performing the single-tape intersection operation operate under the conditions that:

[0227] (A) the semirings of the two automata A₁⁽ⁿ¹⁾and A₂⁽ⁿ²⁾equal to: custom character

;

[0228] (B) the common semiring custom character

is commutative:
∀w₁, w₂∈ custom character

:w₁

w₂=w₂

w₁;

[0229] (C) For IntersectCross( ): Neither of the two intersected tapes contains ε:
( custom character

∃e₁∈ E₁: custom character

(e₁)=ε)

(

∃e₂∈ E₂: custom character

(e₂)=ε).

C.3.2 First Embodiment

[0230] FIG. 13 sets forth a method in pseudocode of the first embodiment for performing the single-tape intersection operation (i.e., A=IntersectCross(A₁, A₂, j, k)). Line 1 begins with a WMTA A whose semiring equals those of A₁and A₂and that is otherwise empty. At lines 3 and 12-18, the initial state i of the WMTA A is created from the initial states A₁and A₂and pushed onto the stack initialized at line 2. While the stack is not empty, the states q are popped from it and the states q₁and q₂are accessed that are assigned to q through μ[q] at lines 4 and 5.

[0231] At lines 6 and 7, each outgoing transition e₁of q₁is intersected with outgoing transitions e₂of q₂. This succeeds at line 8 only if the j-th labeled component of e₁equals the k-th labeled component of e₂, where j and k are the two intersected tapes of A₁and A₂, respectively. Only if it succeeds at line 8 will a transition be created at line 10 for A whose label results from pairing custom character

(e₁) with

(e₂) and whose target q′ corresponds with the pair of targets (n(e₁), n(e₂)). If q′ does not exist yet, it is created and pushed onto the stack at lines 9 and 12-18.

[0232] It will be appreciated by those skilled in the art that this embodiment may be readily adapted to operate with non-weighted multi-tape automata (MTAs) by removing the weights from line 10 and the semiring custom character

from line 1, and by replacing line 15 with “Final(q)←Final(q₁) custom character

Final(q₂)” in the pseudocode shown in FIG. 13.

C.3.3 Mohri's Epsilon-Filter

[0233] The second embodiment for performing the single-tape intersection operation makes use of an epsilon-filter transducer similar to its use in the composition of two transducers with an epsilon-transition that is described in by Mohri et al. in Mohri's Epsilon-Filter Publication. This section describes the use of Mohri's epsilon-filter by simulating its use.

[0234] FIG. 14 illustrates Mohri's epsilon-filter A_ε and two transducers A₁and A₂. The transducers A₁and A₂are pre-processed for filtered composition (where x= custom character

{Φ₁, Φ₂, ε₁, ε₂}) and each ε in tape 2 of A₁⁽²⁾is replaced by an ε₁and each ε in tape 1 of A₂⁽²⁾by an ε₂. In addition, a looping transition labeled with ε:Φ₁is added to each state of A₁⁽²⁾, and a loop labeled with Φ₂:ε to each state of A₂⁽²⁾. The pre-processed transducers are then composed with the filter A_ε⁽²⁾in between: A₁⋄ A_ε⋄ A₂. The filter controls how epsilon-transitions are composed along each pair of paths in A₁and A₂, respectively. As long as there are equal symbols (ε or not) on the two paths, they are composed with each other, and the state does not change in A_εfrom state zero. If a sequence of ε in A₁but not in A₂is encountered, the state advances in A₁, and the state does not change in A₂from the state shown and in A_εfrom state 1. If a sequence of ε in A₂but not in A₁is encountered, the state advances in A₂, and the state does not change in A₁from the state shown and in A_ε from state 2.

C.3.4 Second Embodiment

[0235] FIG. 15 sets forth a method in pseudocode of the second embodiment for performing the single-tape intersection operation (i.e., A=IntersectCrossEps(A₁A₂, j, k)). Unlike the embodiment set forth in section C.3.2 which builds the cross-product, A₁×A₂, and then deletes some of its paths by auto intersection, I_j,n+k( ), this embodiment simulates the behavior of Mohri's epsilon-filter transducer described in section C.3.3 without Mohri's epsilon-filter transducer being present by adding an attribute at each state of the resulting WMTA A, thereby allowing only the useful parts of the cross-product to be constructed.

[0236] More specifically, in FIG. 15, line 1 begins with a WMTA A whose alphabet is the union of the alphabets of transducers A₁and A₂, whose semiring equals those of A₁and A₂, and that is otherwise empty. At lines 3 and 20-26, the initial state i of A is created from the states of A₁, A₂, and A_ε, and the initial state i is pushed onto the stack initialized at line 2. While the stack is not empty, states q are popped from it and the states q₁, q₂, and q_εthat are assigned to states q through Θ[q] at lines 4-5.

[0237] At lines 6-7, each outgoing transition e₁of state q₁is intersected with each outgoing transition e₂of state q₂. This succeeds at line 8 only if the j-th labeled component of e₁equals the k-th labeled component of e₂, where j and k are the two intersected tapes of A₁and A₂, respectively, and if the corresponding transition in A_ε has target zero. Only if it succeeds at line 8 then at line 10, a transition in A is created (from the current source state) whose label results from pairing custom character

(e₁) with

(e₂) and whose target state q′ corresponds with the triple of targets (n(e₁), n(e₂), 0). If state q′ does not exist yet, it is created and pushed onto the stack at lines 20-26.

[0238] Subsequently, all epsilon-transitions are handled in A₁at lines 11-14 and in A₂at lines 15-18. If an epsilon is encountered in A₁and the automaton A_εis in state 0 or in state 1, the current state advances in A₁, does not change in A₂, and advances to state 1 in A_ε. At lines 11-14, a transition in A is therefore created whose target corresponds to the triple (n(e₁), q₂, 1). Corresponding actions take place at lines 15-18 if an epsilon is encountered in A₂.

[0239] It will be appreciated by those skilled in the art that this embodiment may be readily adapted to operate with non-weighted multi-tape automata (MTAs) by removing the weights from lines 10, 14, and 18 and the semiring custom character

from line 1, and by replacing line 23 with “Final(q)←Final(q₁) custom character

Final(q₂)” in the pseudocode shown in FIG. 15.

[0240] It will further be appreciated by those skilled in the art that the embodiment shown in FIG. 15 for performing single-tape intersection of transducers A₁and A₂may be readily adapted to permit the composition of a first tape of the automata A₁and a second tape of the automata A₂while retaining one of the first and the second tapes and all other tapes of both transducers at the transitions where the tapes intersect by revising the labels at each transition E created at lines 10, 14, and 18 to remove one component (i.e., removing either the first tape or the second tape to eliminate redundant paths through complementary projection).

[0241] In addition it will be appreciated by those skilled in the art that the embodiment set forth in FIG. 15 may be readily adapted to perform a classical-composition operation where both the first tape of the automata A₁and the second tape of the automata A₂are removed while retaining all other tapes of both transducers at the transitions where the tapes intersect by revising the labels at each transition E created at lines 10, 14, and 18 to remove both components (i.e., removing both the first tape and the second tape).

C.3.5 Complexity

[0242] The worst-case complexity of both the first embodiment and the second embodiment for carrying out the a single-tape intersection is |E₁|·|E₂| in space and runtime (i.e., on the order of O(n²)). The complexity of the second embodiment is only linearly greater than that of the first, which may be significant for large WMTAs.

C.4 Multi-Tape Intersection

[0243] This section sets forth two embodiments for performing the multi-tape intersection operation of two WMTAs A₁⁽ⁿ⁾and A₂^(m)defined in section B.6. The first embodiment is referred to herein as Intersect1(A₁⁽ⁿ⁾and A₂^(m), j₁. . . j_r, k₁. . . k_r), follows the definition of multi-tape intersection while performing operations for cross-product, auto-intersection, and complementary projection. The second embodiment, which is more efficient, is referred to herein as Intersect2(A₁⁽ⁿ⁾and A₂^(m), j₁. . . j_r, k₁. . . k_r), makes use of methods that perform cross-product and auto-intersection in one step (for intersection tape j₁and k₁), and then the auto-intersection (for any intersecting tapes j_iwith k_i, for i>1).

C.4.1 Conditions

[0244] Both embodiments for performing the multi-tape intersection operation operate under the conditions that:

- [0245] (a) the semirings of the two automata A₁⁽ⁿ⁾and A₂^(m)are equal to: =; and
- [0246] (b) the common semiring == is commutative:
  ∀w₁, w₂∈ :w₁ w₂=w₂ w₁
- [0247] (c) A₁⁽ⁿ⁾and A₂^(m)have no cycles exclusively labeled with epsilon on any of the intersected tapes:
  j_i∈ [[1, n]] and k_i∈ [[1, m]], for i ∈ [[1, r]].

C.4.2 Embodiments

[0248] The first embodiment, Intersect1( ), for carrying out the multi-tape intersection operation defined in section B.6 may be expressed in pseudocode as follows:

[0249] (a) in one embodiment, while referring at line 1 to CrossPA( ) (to perform a cross product operation on the WMTAs A₁⁽ⁿ⁾and A₂^(m)) set forth in FIG. 5, at line 3 to the first AutoIntersect( ) method (to perform the auto-intersection operation for each intersecting tapes j_iand k_i) set forth in FIG. 6, and at line 4 to complementary projection (to eliminate redundant tapes) described in section B.2:

[0250]


	INTERSECT1(A₁⁽ⁿ⁾, A₂^(m), j₁. . . j_r, k₁. . . k_r) → A :
	1	A ← CROSSPA(A₁⁽ⁿ⁾, A₂^(m))
	2	for ∀i ∈ 1, r do
	3	A ← AUTOINTERSECT(A, j_i, n + k_i)
	4	A ← _n+k_₁, ... ,n+k_r(A)
	5	return A

[0251] or (b) in another embodiment, while referring at line 1 to CrossPA( ) (to perform a cross product operation on the WMTAs A₁⁽ⁿ⁾and A₂^(m)) set forth in FIG. 5, at line 4 to the second AutoIntersect( ) method (to perform the auto-intersection operation for each intersecting tapes j_iand k_i) set forth in FIG. 9, and at line 6 to complementary projection (to eliminate redundant tapes) described in section B.2:

[0252]


	INTERSECT1(A₁⁽ⁿ⁾, A₂^(m), j₁. . . j_r, k₁. . . k_r) → (A, boolean) :
	1	A ← CROSSPA(A₁⁽ⁿ⁾, A₂^(m))
	2	regular ← true
	3	for ∀i ∈ 1, r do
	4	(A, reg) ← AUTOINTERSECT(A, j_i, n + k_i)
	5	regular ← regular reg
	6	A ← _{... ,n+k}_{_r}(A)
	7	return (A, regular)

[0253] The second embodiment, Intersect2( ), for carrying out the multi-tape intersection operation defined in section B.6 may be expressed in pseudocode as follows:

[0254] (a) in one embodiment, while referring at line 1 to IntersectCrossEps( ) set forth in FIG. 15 (to perform the single-tape intersection operation on one pair of tapes for tapes j₁with k₁on the WMTAs A₁⁽ⁿ⁾and A₂^(m)), at line 3 to AutoIntersect( ) set forth in FIG. 6 (to perform the auto-intersection operation for any intersecting tapes j_iwith k_i, for i>1), and at line 4 to complementary projection (to eliminate redundant tapes) described in section B.2:

[0255]


	INTERSECT2(A₁⁽ⁿ⁾, A₂^(m), j₁. . . j_r, k₁. . . k_r) → A :
	1	A ← INTERSECTCROSSEPS(A₁⁽ⁿ⁾, A₂^(m), j₁, k₁)
	2	for ∀i ∈ 2, r do
	3	A ← AUTOINTERSECT(A, j_i, n + k_i)
	4	A ← _{, ... ,n+k}_{_r}(A)
	5	return A

[0256] or (b) in another embodiment, while referring at line 1 to IntersectCrossEps( ) set forth in FIG. 15 (to perform the single-tape intersection operation on one pair of tapes tapes j_i=1with k_i=1on the WMTAs A₁⁽ⁿ⁾and A₂^(m)), at line 4 to AutoIntersect( ) set forth in FIG. 9 (to perform the auto-intersection operation for any intersecting tapes j_iwith k_i, for i>1), and at line 6 to complementary projection (to eliminate redundant tapes) described in section B.2:

[0257]


	INTERSECT2(A₁⁽ⁿ⁾, A₂^(m), j₁. . . j_r, k₁. . . k_r) → (A, boolean) :
	1	A ← INTERSECTCROSSEPS(A₁⁽ⁿ⁾, A₂^(m), j₁, k₁)
	2	regular ← true
	3	for ∀i ∈ 2, r do
	4	(A, reg) ← AUTOINTERSECT(A, j_i, n + k_i)
	5	regular ← regular reg
	6	A ← _{, ... ,n+k}_{_r}(A)
	7	return (A, regular)

C.4.3 Example

[0258] By way of example, a solution is presented for compiling a multi-tape intersection of the MTA A₁⁽²⁾and the MTA A₂⁽²⁾in accordance with the last method presented immediately above to produce the regular MTA A⁽²⁾as follows:

[0259]

A^{(2)} = A_{1}^{(2)} ⋂_{\underset{2, 2}{1, 1}} A_{2}^{(2)} = {\overline{𝒫}}_{3, 4} (ℐ_{2, 4} (ℐ_{1, 3} (A_{1}^{(2)} \times A_{2}^{(2)})

where

[0260]

A_{1}^{(2)} ⋂_{\underset{2, 2}{1, 1}} A_{2}^{(2)}

is given by:

[0261]

\begin{matrix} a & b \\ ɛ & A \end{matrix} {(\begin{matrix} c & a & b \\ B & ɛ & C \end{matrix})}^{*} \begin{matrix} ɛ & ɛ & ɛ & c & ɛ \\ A & B & C & ɛ & A \end{matrix} ⋂_{\underset{2, 2}{1, 1}} \begin{matrix} ɛ \\ A \end{matrix} {(\begin{matrix} a & b & ɛ & c \\ B & ɛ & C & A \end{matrix})}^{*}

where the preceding each row of the matrix-like representation sets forth a tape of each WMTA (e.g., A₁⁽²⁾= custom character

a, ε

b, A

(

c, B

a, ε

b, C

ε, A

ε, B

ε, C

c, ε

ε, A

[0262] In accordance with the method set forth above, the multi-tape intersection operation is performed in three steps. First, the following automaton B₁⁽⁴⁾=I_{1, 3}(A₁⁽²⁾×A₂⁽²⁾) is computed using single-tape intersection at line 1 (i.e., IntersectCrossEps( ) shown in FIG. 15) to obtain:

[0263]

\begin{matrix} ɛ & a & b \\ ɛ & ɛ & A \\ ɛ & a & b \\ A & B & ɛ \end{matrix} {(\begin{matrix} ɛ & c & a & b \\ ɛ & B & ɛ & C \\ ɛ & c & a & b \\ C & A & B & ɛ \end{matrix})}^{*} \begin{matrix} ɛ & ɛ & ɛ & c & ɛ \\ A & B & C & ɛ & A \\ ɛ & ɛ & ɛ & c & ɛ \\ C & ɛ & ɛ & A & ɛ \end{matrix}

[0264] Next, the following automaton B₂⁽⁴⁾=I_{2, 4}(B₁⁽⁴⁾) is computed using auto-intersection at line 4 (i.e., AutoIntersect( ) shown in FIG. 9) to obtain:

[0265]

\begin{matrix} ɛ & a & b \\ ɛ & ɛ & A \\ ɛ & a & b \\ A & B & ɛ \end{matrix} {(\begin{matrix} ɛ & c & a & b \\ ɛ & B & ɛ & C \\ ɛ & c & a & b \\ C & A & B & ɛ \end{matrix})}^{1} \begin{matrix} ɛ & ɛ & ɛ & c & ɛ \\ A & B & C & ɛ & A \\ ɛ & ɛ & ɛ & c & ɛ \\ C & ɛ & ɛ & A & ɛ \end{matrix}

[0266] Finally, the following automaton A²= custom character

(B₂⁽⁴⁾) is computed using complementary projection custom character

at line 6 (described in section B.2) to obtain:

[0267]

\begin{matrix} ɛ & a & b \\ ɛ & ɛ & A \end{matrix} {(\begin{matrix} ɛ & c & a & b \\ ɛ & B & ɛ & C \end{matrix})}^{1} \begin{matrix} ɛ & ɛ & ɛ & c & ɛ \\ A & B & C & ɛ & A \end{matrix}

D. Applications

[0268] This section describes different applications for using the operations on WMATs that are described herein.

D.1 General Use

[0269] FIG. 16 sets forth an automaton W⁽¹⁾for illustrating a proposed operation for part-of-speech (POS) disambiguation and how it may be used in natural language processing (NLP).The automaton W⁽¹⁾shown in FIG. 16 is an automaton that represents a natural-language sentence, with one word w on each transition. In general, such an automaton can contain one or several paths, according to whether the sentence was unambiguously tokenized or not. In the example shown in FIG. 16, the automaton W⁽¹⁾contains two paths, corresponding to an ambiguous tokenization into either three or four words. FIG. 17 illustrates the process for one path π_i(W) (which occurs similarly for all paths) of the automaton W⁽¹⁾.

[0270] Table 2 sets forth resources that may be used in this example, which are encoded as WMTAs.

[0271]

TABLE 2

	Type Of
Automaton	Resource	Tapes

N⁽²⁾	normalizer	original word form,
		normalized form
L⁽³⁾	morphological	surface form,
	lexicon	lemma,
		POS-tag
H⁽¹⁾	Hidden	POS-tag sequence
	Markov Model

[0272] This example can be expressed in pseudocode as follows:

[0273]


	1	for ∀e ∈ E(W) do

	2	⁢ ( e ) ( 1 ) ← ⁢ ( ⁢ ( e ) ( 1 ) ⁢ ⋂ 1 , 1 ⁢ N ( 2 ) )

	3	⁢ ( e ) ( 3 ) ← ⁢ ( e ) ( 1 ) ⁢ ⋂ 1 , 1 ⁢ L ( 3 )

	4	if (e)⁽³⁾= ⊥
	5	then (e) ← . . .

	6	W ( 4 ) ← W ( 4 ) ⁢ ⋂ 3 , 1 ⁢ H ( 1 )

	7	W⁽⁴⁾← bestPath(W⁽⁴⁾)

[0274] At line 1 of the pseudocode above, each transition of 1-tape automaton W⁽¹⁾(i.e., each word of the sentence) is processed separately: custom character

(e), representing the transition e ∈ E(W), is intersected with a normalizer N⁽²⁾and only the second tape of the result is retained at line 2. Subsequently, custom character

(e) is intersected with a 3-tape morphological lexicon custom character

and becomes itself 3-tape as set forth in line 3 of the pseudocode and in FIG. 18. Specifically, FIG. 18 illustrates the intersection of an arc e of W⁽¹⁾with a path π⁽³⁾of the lexicon automaton custom character

. If at line 4 this operation fails, then something else is done with custom character

(e) at line 5 such as intersecting custom character

(e) with another n-tape automaton.

[0275] When all transitions have been separately processed, as described above, processing begins again on the sentence automaton W⁽⁴⁾, which at this point has four tapes due to previous operations. At line 6, the sentence automaton W⁽⁴⁾is intersected with a 1-tape automaton H⁽¹⁾that represents an HMM as shown in FIG. 19. More specifically, FIG. 19 illustrates the intersection of a path π_j⁽⁴⁾of the sentence automaton W⁽⁴⁾with a path π⁽¹⁾of the HMM automaton H⁽¹⁾. Finally at line 7, only the best path of the sentence automaton W⁽⁴⁾is retained.

D.2 Building a Lexicon from a Corpus

[0276] Using basic software programming utilities such as those forming part of UNIX, a list of inflected words with their POS-tags and their frequencies from an annotated corpus may be generated and stored in a file. Such a file may for example contain entries as shown in Table 3.

[0277]

TABLE 3

Inflected	POS-
Word	tag	Fequency


leave	NN	7
leave	VB	154
leaves	NNS	18
leaves	VBZ	25
leaving	VBG	67
left	JJ	47
left	VBD	118
left	VBN	147

[0278] In one implementation, a WMTA lexicon may be created over the semiring < IR⁺, +, ×, 0, 1>, where each line of a file (as illustrated in Table 3) becomes the n-tape label of a path, such that each token of the line (or each column of Table 3) is placed onto a different tape, except for the last token (i.e., the frequency) which becomes the weight of the path. Using such an implementation and the example data in Table 3, a 2-tape corpus lexicon C⁽²⁾may be constructed with paths having the labels custom character

and the weights w as shown in Table 4.

[0279]

	TABLE 4

	Label	Weight w


	<leave, NN>	7
	<leave, VB>	154
	<leaves, NNS>	18
	<leaves, VBZ>	25
	<leaving, VBG>	67
	<left, JJ>	47
	<left, VBD>	118
	<left, VBN>	147

D.3 Enhancing a Lexicon with Lemmas

[0280] The corpus of lexicons and lemmas defined in section D.2 may be enhanced using another lexicon encoded as a non-weighted MTA, T⁽³⁾having entries of the form T⁽³⁾<InflectedWord, Lemma, PosTag>, and containing at least those entries in Table 5.

[0281]

TABLE 5

Inflected
Word	Lemma	PosTag

leave	leave	NN
leave	leave	VB
leaves	leaf	NNS
leaves	leave	NNS
leaves	leave	VBZ
leaving	leave	VBG
left	left	JJ
left	leave	VBD
left	leave	VBN

[0282] Each of the entries in Table 5 is uniformly weighted with w=1.0 by assigning 1.0 to each transition and final state. To distribute the probability among different lemmas for equal inflected forms and POS tags, the lexicon T⁽³⁾is normalized with respect to tape 1 and tape 3 using multi-tape intersection resulting in the entries shown in Table 6.

[0283]

	TABLE 6

	Lexicon T⁽³⁾	Weight w

	<leave, leave, NN>	1.0
	<leave, leave, VB>	1.0
	<leaves, leaf, NNS>	0.5
	<leaves, leave, NNS>	0.5
	<leaves, leave, VBZ>	1.0
	<leaving, leave, VBG>	1.0
	<left, left, JJ>	1.0
	<left, leave, VBD>	1.0
	<left, leave, VBN>	1.0

[0284] The intersection of the lexicon T⁽³⁾(having values shown in column 1 of Table 6) with the corpus lexicon C⁽²⁾(having values shown in Table 4) on the tapes of inflected forms and POS-tags, respectively, is defined as:

[0285]

L^{(3)} = T^{(3)} ⋂_{\underset{3, 2}{1, 1}} C^{(2)}

and results in the lexicon L⁽³⁾the entries of which are shown in Table 7.

[0286]

	TABLE 7

	Lexicon L⁽³⁾	Weight w


	<leave, leave, NN>	7
	<leave, leave, VB>	154
	<leaves, leaf, NNS>	9
	<leaves, leave, NNS>	9
	<leaves, leave, VBZ>	25
	<leaving, leave, VBG>	67
	<lett, left, JJ>	47
	<left, leave, VBD>	118
	<left, leave, VBN>	147

[0287] Finally, the lexicon L⁽³⁾(having values shown in Table 7) is normalized (i.e., all entries with the same inflected form have a weight w that sums to one) with respect to inflected forms to provide the entries shown in Table 8.

[0288]

	TABLE 8

	Lexicon L⁽³⁾	Weight w

	<leave, leave, NN>	0.043
	<leave, leave, VB>	0.957
	<leaves, leaf, NNS>	0.209
	<leaves, leave, NNS>	0.209
	<leaves, leave, VBZ>	0.581
	<leaving, leave, VBG>	1.000
	<left, left, JJ>	0.151
	<left, leave, VBD>	0.378
	<left, leave, VBN>	0.471

D.4 Normalizing a Lexicon

[0289] In this example, the conditional normalization of a WMTA, A₁^(n+m), compiled over the semiring < IR⁺, +, ×, 0, 1>, with respect to some of its tapes, using a generalization of the method proposed by Eisner in “Parameter Estimation For Probabilistic Finite-state Transducers”, in Proceedings of the 40th Annual Meeting, pages 1-8, Philadelphia, Pa., USA, Association For Computer Linguistics, 2002, which is incorporated herein by reference. Consider, for instance, each string tuple u^(n+m)in the language custom character

of A₁^(n+m)to be a pair of string tuples (i.e., u^(n+m)=s⁽ⁿ⁾:v^(m)). Normalizing A₁^(n+m)conditionally with respect to n+1 to n+m means compiling for each u^(n+m)the probability of s⁽ⁿ⁾in the context of v^(m).

[0290] Suppose, originally the weight of each u^(n+m)is its frequency (i.e., the frequency of concurrence of tuples s⁽ⁿ⁾and v^(m)) is given by:
w_A₁(u^(n+m))=f(s⁽ⁿ⁾:v^(m))

[0291] The context tapes of custom character

are projected and the following context language is obtained:
custom character

. . . , n+m( custom character

)

[0292] Each string tuple v^(m)∈ custom character

of the determinized context automaton A_c^(m)has the weight given by:

[0293]

w (v^{(m)}) = \underset{v_{i}^{(m)} = v^{(m)}}{\oplus} w_{A_{1}} (s_{i}^{(n)} : v_{i}^{(m)}) = f (v^{(m)})

[0294] The weight of all string tuples v^(m)∈ custom character

is inversed by inversing the weight of each transition and each final state of A_c^(m). The resulting weight of each v^(m)is given by:
w_A_c(v^(m))=f(v^(m))⁻¹.

[0295] Finally, the original A₁^(n+m)is intersected with A_c^(m)on all context tapes, and an automaton A₂^(n+m)obtained with the language given by:

[0296]

ℒ_{2}^{(n + m)} = ℒ_{1}^{(n + m)} ⋂_{\underset{n + m, m}{\underset{\dots}{n + 1, 1}}} ℒ_{c}^{(m)}

[0297] All string tuples u^(n+m)=s⁽ⁿ⁾:v^(m)ε custom character

have the weight given by:

[0298]

\begin{matrix} \begin{matrix} w_{A_{2}} (u^{(n + m)}) = w_{A_{1}} (s^{(n)} : v^{(m)}) \otimes w_{A_{c}} (v^{(m)}) \\ = f (s^{(n)} : v^{(m)}) \cdot {f (v^{(m)})}^{- 1} \\ = p (s^{(n)} | v^{(m)}) \end{matrix} \end{matrix}

[0299] Those skilled in the art will appreciate that this approach does not require the context tapes to be consecutive.

[0300] To compile the joint normalization of a WMTA, A₁⁽ⁿ⁾, over the semiring < IR⁺, +, ×, 0, 1>, the frequency of each string tuple s(n)ε custom character

(A₁⁽ⁿ⁾) is multiplied with the inverse of the total frequency f_Tof all string tuples. The total frequency f_Tcan be obtained by replacing the label of each transition of A₁⁽ⁿ⁾with ε and applying an epsilon removal (as described for example by Mohri in “Generic epsilon-removal and input epsilon-normalization algorithms for weighted transducers”, in International Journal of Foundations of Computer Science, 13(1):129-143, 2002, which is incorporated herein by reference). The resulting automaton, A_T, has one single state, without any outgoing transitions, and a final weight that equals the total frequency, custom character

=f_T. The final weight custom character

is inversed and A₁⁽ⁿ⁾is concatenated with A_T. All string tuples s⁽ⁿ⁾∈ custom character

(A₂⁽ⁿ⁾) of the resulting automaton A₂⁽ⁿ⁾=A₁⁽ⁿ⁾A_Thave the weight given by:

[0301]

\begin{matrix} \begin{matrix} w_{A_{2}} (s^{(n)}) = w_{A_{1}} (s^{(n)}) \otimes w_{A_{T}} (ɛ^{(n)}) \\ = f (s^{(n)}) \cdot f_{T}^{- 1} \\ = p (s^{(n)}) \end{matrix} \end{matrix}

D.5 Using a Lexicon

[0302] When using a lexicon WMTA, A(n), the following may be specified: r input tapes, j₁to j_r, and x output tapes, k₁to k_x, which do not have to be consecutive. A weighted r-tuple of input strings, s^r, may first be converted into an input WMTA, I^(r), having one single path with the specified label, s^(r), and weight, w(s^(r)). Subsequently to obtaining the output WMTA, O^(x), whose language contains all weighted x-tuples of output strings, v^(x), the following multi-tape intersection and projection may be used:

[0303]

O^{(x)} = 𝒫_{k_{1}, \dots, k_{x}} (A^{(n)} ⋂_{\underset{\underset{j_{r}, r}{\dots}}{j_{1}, 1}} I^{(r)})

D.6 Searching for Similarities

[0304] In the applications described in this section, string tuples s(n) may searched for in the language custom character

of a WMTA A₁⁽ⁿ⁾whose strings s_j₁to s_j_rare similar to its strings s_k₁to s_k_r, respectively. The comparison of each pair of tapes, j_iand k_i, may be done independently form all other pairs of tapes. Hence the task may be reduced to comparing two tapes, j and k.

[0305] First, a 2-tape automaton, R⁽²⁾, may be created, whose language, custom character

, describes the requested relation between tape j and k of custom character

. To obtain the language given by the relation:
custom character

and where when this relation holds between the languages, the following language may be compiled:

[0306]

ℒ_{2}^{(n)} = ℒ_{1}^{(n)} ⋂_{\underset{k, 2}{j, 1}} R^{(2)}

[0307] In one specific example, suppose there exists an English-German dictionary that is encoded as a 3-tape WMTA, with each entry being of the form <English, German, PosTag>. To find all words that are similar in the two languages, while having the same POS tag, a 2-tape automaton, R⁽²⁾, may be created that describes this similarity by using, for example, either of the approaches referred to herein as the “Levenshtein Distance” or the “List of Grapheme Correspondences” described below.

[0308] The Levenshtein Distance between two strings is the minimal number of intersections, deletions or substitutions of symbols that are needed to transform one string into the other, as disclosed by Schulz and Mihov in “Fast string correction with Levenshtein automata”, International Journal on Document Analysis and Recognition, 5(1):67-85, 2002, which is incorporated herein by reference. A WMTA, Lv_d⁽²⁾, having a Levenshtein Distance d between the members s₁and s₂of all string tuples s⁽²⁾∈ custom character

(Lv_d⁽²⁾) can be compiled from the regular expression:
Lv_d⁽²⁾=((?:_i?)*(?:? ∪ ?:ε ∪ ε:?) (?:_i?)*)^d,
where ? means any symbol (i.e., ? ∈ {a, b, c, . . . }), and :_iis an identity paring such that (?:_i?) ∈ {a:a, b:b, c:c, . . . }, whereas (?:?) ∈ {a:a, a:b, b:a, . . . }.

[0309] The List of Grapheme Correspondences by manually writing a list of synchronic grapheme correspondences resulting from historical phonological alterations in the English and German languages may, for example, contain the entries in Table 9 (for English in column 1 and German in column 2).

[0310]

	TABLE 9

	ENGLISH	GERMAN

	th	d
	th	ss
	d	t

[0311] Using the lexicon construction method described in sections D.2-D.5, the list of entries in Table 9 may be used to construct a lexicon-like automaton, Ch⁽²⁾, that encodes these changes in the form set forth in Table 10 (where column 1 identifies the lexicon, and column 2 identifies the weight).

[0312]

	TABLE 10

	Lexicon Ch⁽²⁾	Weight w

	<th, d>	1
	<th, ss>	1
	<d, t>	1

[0313] The lexicon-like automaton Ch⁽²⁾may then be used to obtain a WMTA, R⁽²⁾, whose language describes the relation between any English word and its potential German form that is given by:
R⁽²⁾=(Ch⁽²⁾∪ ?:_i?)⁺.

D.7 Preserving Intermediate Transduction Results

[0314] In this section, the advantage of WMTAs through transduction cascades, which are frequently used in language and speech processing, is illustrated. In a (classical) weighted transduction cascade, T₁⁽²⁾. . . T_r⁽²⁾, a set of weighted strings, encoded as a weighted acceptor, L₀⁽¹⁾, is composed with the transducer, T₁⁽²⁾, on its input tape as shown in FIG. 20. The output projection of this composition is the first intermediate result, L₁⁽¹⁾, of the cascade. It is further composed with the second transducer, T₂⁽²⁾, which leads to the second intermediate result, L₂⁽¹⁾, etc. The projection of the last transducer is the final result, L_r⁽¹⁾, which is defined as follows:
L_i⁽¹⁾= custom character

(L_i-1⁽¹⁾⋄ T_i⁽²⁾) for i ∈ custom character

At any point in this cascade, previous results cannot be accessed.

[0315] In a weighted transduction cascade, A₁⁽ⁿ¹⁾. . . A_r⁽ⁿ^r), that uses WMTAs and multi-tape intersection, intermediate results can be preserved and used by all subsequent transductions. For example, assuming the two previous results at each point in the cascade (except in the first transduction) are to be used in computing the results. This operation requires all intermediate results, L_i⁽²⁾, to have two tapes as shown in FIG. 2 and defined as follows:

[0316]

L_{1}^{(2)} = L_{0}^{(1)} ⋂_{1, 1} A_{1}^{(2)}

L_{i}^{(2)} = 𝒫_{2, 3} (L_{i - 1}^{(2)} ⋂_{\underset{2, 2}{1, 1}} A_{i}^{(3)})

L_{r}^{(2)} = 𝒫_{3} (L_{r - 1}^{(2)} ⋂_{\underset{2, 2}{1, 1}} A_{r}^{(3)})

for i \in 〚 2, r - 1 〛

[0317] This augmented descriptive power is also available if the whole cascade is intersected into a single WMTA, A⁽²⁾(although A⁽²⁾has only two tapes in the example). Each of the “incorporated” multi-tape sub-relations in A⁽²⁾(except for the first one) will still refer to its two predecessors as follows:

[0318]

\begin{matrix} A_{1 \dots i}^{(3)} = 𝒫_{1, n - 1, n} (A_{1 \dots i - 1}^{(m)} ⋂_{\underset{n, 2}{n - 1, 1}} A_{i}^{(3)}) for i \in 〚 2, r 〛, m \in {2, 3} \\ A^{(2)} = 𝒫_{1, n} (A_{1 \dots r}) \end{matrix}

[0319] Advantageously, this example illustrates how intermediate results can be preserved in transduction cascades sot that they can be accessed by any of the following transductions.

D.8 Example System

[0320] FIG. 22 illustrates a general purpose computer system 1610 for carrying out NLP in accordance with the present invention. The system 1610 includes hardware 1612 and software 1614. The hardware 1612 is made up of a processor (i.e., CPU) 1616, memory 1618 (ROM, RAM, etc.), persistent storage 1620 (e.g., CD-ROM, hard drive, floppy drive, tape drive, etc.), user I/O 1622, and network I/O 1624. The user I/O 1622 can include a keyboard 1626, a pointing device 1628 (e.g., pointing stick, mouse, etc.), microphone 1608, camera 1604, speakers 1606, and the display 1630. The network I/O 1624 may for example be coupled to a network 1632 such as the Internet. The software 1614 of the system 1610 includes an operating system 1636, a regular expression compiler 1638, a WMTAs and MTAs methods 1640 (e.g., auto-intersection and tape-intersection), and NLP methods and applications 1642. In one embodiment, the natural language processing methods and applications 1642 use WMTAs and MTAs that are stored in memory 1618 and that are compiled, for example, from regular expressions using compiler 1638, to perform one or more singly or in combination of POS tagging, tokenization, phonological and morphological analysis, disambiguation, spelling correction, translation, entity extraction, and shallow parsing.

E. Miscellaneous

[0321] Although the present invention is generally directed at weighted automata, each operation described in the forgoing specification may be used to operate on non-weighted automata as well. Additional background of the invention is described in the following publications incorporated herein by reference: Andre Kempe, Christof Baeijs, Tamas Gaal, Franck Guingne, Florent Nicart, “WFSC—A new weighted finite state compiler”, 8th Int. Conf. on Implementation and Application of Automata (CIAA 03), Santa Barbara, Calif., USA, Jul. 16-18, 2003 (which describes an example framework for carrying out the weighted finite state operations set forth herein); and Andre Kempe, “NLP Applications based on weighted multi tape automata”, TALN, Fes, Morocco, Apr. 19-22, 2004 (which describes an additional example related to section D.6 for extracting similar words in French and Spanish).

[0322] Advantageously over (weighted) 1-tape or 2-tape system for processing automata, the forgoing specification for processing n-tape automata permits: (a) the separation of different types of information used in NLP over different tapes (e.g., surface form, lemma, POS-tag, domain-specific information, etc.); (b) the preservation of some or all intermediate results of various NLP steps on different tapes; and (c) the possibility of defining and implementing contextual replace rules referring to different types of information on different tapes. Contextual replace rules are more fully described in the publications, which are incorporated herein by reference, by: Kaplan and Kay “Regular models of phonological rule systems”, Computational Linguistics 20(3):331-378, 1994; Karttunen “The replace operator”, Proceedings of the 33rd Annual Meeting, Cambridge, Mass., USA, Association for Computational Linguistics, pages 16-23, 1995; and Kempe and Karttunen, “Parallel replacement in finite-state calculus”, Proceedings of the 16th International Conference on Computational Linguistics (CoLing), volume 2, pages 622-627, Copenhagen, Denmark, ACL, 1996.

[0323] In addition, it will be appreciated by those skilled in the art that the forging specification provides the following advantages that are difficult to obtain using 1-tape or 2-tape automata: (a) a simplified description, implementation, modification, and maintenance of a sequence of NLP tasks (as described for example in section D.1); and (b) the ability to execute a sequence of NLP tasks in a single tool via an end-user interface enabled for performing the operations on automata described herein.

[0324] Using the foregoing specification, the invention may be implemented as a machine (or system), process (or method), or article of manufacture by using standard programming and/or engineering techniques to produce programming software, firmware, hardware, or any combination thereof. It will be appreciated by those skilled in the art that the flow diagrams described in the specification are meant to provide an understanding of different possible embodiments of the invention. As such, alternative ordering of the steps, performing one or more steps in parallel, and/or performing additional or fewer steps may be done in alternative embodiments of the invention.

[0325] Any resulting program(s), having computer-readable program code, may be embodied within one or more computer-usable media such as memory devices or transmitting devices, thereby making a computer program product or article of manufacture according to the invention. As such, the terms “article of manufacture” and “computer program product” as used herein are intended to encompass a computer program existent (permanently, temporarily, or transitorily) on any computer-usable medium such as on any memory device or in any transmitting device.

[0326] Executing program code directly from one medium, storing program code onto a medium, copying the code from one medium to another medium, transmitting the code using a transmitting device, or other equivalent acts may involve the use of a memory or transmitting device which only embodies program code transitorily as a preliminary or final step in making, using, or selling the invention.

[0327] Memory devices include, but are not limited to, fixed (hard) disk drives, floppy disks (or diskettes), optical disks, magnetic tape, semiconductor memories such as RAM, ROM, Proms, etc. Transmitting devices include, but are not limited to, the Internet, intranets, electronic bulletin board and message/note exchanges, telephone/modem based network communication, hard-wired/cabled communication network, cellular communication, radio wave communication, satellite communication, and other stationary or mobile network systems/communication links.

[0328] A machine embodying the invention may involve one or more processing systems including, but not limited to, CPU, memory/storage devices, communication links, communication/transmitting devices, servers, I/O devices, or any subcomponents or individual parts of one or more processing systems, including software, firmware, hardware, or any combination or subcombination thereof, which embody the invention as set forth in the claims.

[0329] The claims, as originally presented and as they may be amended, encompass variations, alternatives, modifications, improvements, equivalents, and substantial equivalents of the embodiments and teachings disclosed herein, including those that are presently unforeseen or unappreciated, and that, for example, may arise from applicants/patentees and others.

Claims

What is claimed is:

1. In a system for processing natural language, a method for intersecting a first tape of a first multi-tape automaton (MTA) and a second tape of a second MTA, with each MTA having a plurality of tapes and a plurality of paths, comprising:

defining a simulated filter automaton (SFA) that controls how epsilon-transitions are composed along pairs of paths in the first MTA and the second MTA; and,

building by a processor an output MTA by;

(a) creating an initial state from the initial states of the first MTA, the second MTA, and the SFA;

(b) intersecting a selected outgoing transition of the first MTA with a selected outgoing transition of the second MTA, where each outgoing transition has a source state, a target state, and a label;

(c) creating a transition in the output MTA if the label of the first tape of the selected outgoing transition of the first MTA equals the label of the second tape of the selected outgoing transition of the second MTA, wherein the transition in the output MTA is created whose label results from pairing the labels of the selected outgoing transitions and whose target state corresponds to the target states of the selected outgoing transitions and the initial state of the SFA;

(d) if an epsilon transition is encountered on the first tape, creating a transition in the output MTA with a target state that is a function of the target state of the outgoing transition of the first MTA, the source state of the outgoing transition of the second MTA, and a first non-initial state of the SFA;

(e) if an epsilon transition is encountered on the second tape, creating a transition in the output MTA with a target state that is a function of the source state of the outgoing transition of the first MTA, the target state of the outgoing transition of the second MTA, and a second non-initial state of the SFA; and

(f) repeating (b)-(e) for each outgoing transition of the first MTA and the second MTA.

2. The method according to claim 1, further comprising revising the labels of transitions of the output MTA to remove one of its tapes corresponding to either the first tape of the first MTA or the second tape of the second MTA to complete single-tape intersection.

3. The method according to claim 1, further comprising revising the labels of each transition of the output MTA to remove both of its tapes corresponding to the first tape of the first MTA and the second tape of the second MTA to complete classical composition.

4. The method according to claim 1, further comprising performing auto-intersection on the output MTA for two selected tapes, wherein no more than one of the two selected tapes corresponds to the first tape of the first MTA or the second tape of the second MTA.

5. The method according to claim 4, further comprising revising the output MTA to eliminate redundant tapes to complete multi-tape intersection.

6. The method according to claim 1, wherein the output MTA preserves at least one other tape besides one of the first tape of the first MTA and the second tape of the second MTA.

7. The method according to claim 1, further comprising repeating (a)-(f) in a cascade of a first transduction and a second transduction, where at least one of the tapes preserved after completing the first transduction is accessed to perform the second transduction.

Patent Citations (21)

Patent	Date	Inventor	Cited By
US5113342(A)	1992-05-01	Zamora	Examiner
US5412567(A)	1995-05-01	Karttunen	Examiner
US5594641(A)	1997-01-01	Kaplan et al.	Applicant
US5625554(A)	1997-04-01	Cutting et al.	Examiner
US5642522(A)	1997-06-01	Zaenen et al.	Applicant
US5781884(A)	1998-07-01	Pereira et al.	Examiner
US5806032(A)	1998-09-01	Sproat	Examiner
US6430557(B1)	2002-08-01	Gaussier et al.	Examiner
US6961693(B2)	2005-11-01	Kempe	Applicant
US7010476(B2)	2006-03-01	Karttunen et al.	Applicant
US7085918(B2)	2006-08-01	Sharangpani et al.	Examiner
US7093231(B2)	2006-08-01	Nuss	Examiner
US7240004(B1)	2007-07-01	Allauzen et al.	Examiner
US7240040(B2)	2007-07-01	Wyschogrod et al.	Examiner
US7257575(B1)	2007-08-01	Johnston et al.	Applicant
US7346511(B2)	2008-03-01	Privault et al.	Applicant
US7383185(B1)	2008-06-01	Mohri	Applicant
US7552051(B2)	2009-06-01	Privault et al.	Applicant
US7783485(B2)	2010-08-01	Allauzen et al.	Examiner
US2003/0004705(A1)	2003-01-01	Kempe	Examiner
EP1531400(A3)	2006-03-01		Applicant

Non-Patent Literature (25)

Eilenberg, S., “Automata, Languages, and Machines”, vol. A., Academic Press, San Diego, CA, 1974: Chapter 1, Sec. 3, “Monoids”, pp. 3-6; Chapter 6, Sec. 1 “Multiplicity in Automata”, pp. 120-122; Chapter 6, Sec. 2, “Semirings”, pp. 122-126.Applicant
Elgot, C.C. and Mezei, J.R., “On Relations Defined by Generalized Finite Automata”, IBM Journal Res. 9, pp. 47-68, 1965.Applicant
Kaplan, R. and Kay, M., “Regular Models of Phonological Rule Systems”, Computational Linguistics, 20(3):331-378, 1994.Applicant
Karttunen, L., “The Replace Operator”, Proceedings of the 33rd Annual Meeting, pp. 16-23, Cambridge, MA 1995.Applicant
Kay, M., “Nonconcatenative Finite-State Morphology”, ACL Proceedings, Third European Conf. 1987.Applicant
Kempe, A. et al., “Parallel Replacement in Finite-State Calculus”, Proc. of the 16th Int. Conf. on Computational Linguistics (CoLing), vol. 2, pp. 622-627, Copenhagen, Denmark, ACL, cmp-lg/9607007, 1996.Applicant
Kempe, A. et al., “WFSC—A New Weighted Finite State Compiler”, 8th Int. Conf. on Implementation and Application of Automata (CIAA 03), Santa Barbara, CA, Jul. 16-18, 2003.Applicant
Kempe, A., “NLP Applications Based on Weighted Multi-Tape Automata”, TALN, Fes, Morocco, Apr. 12-22, 2004.Applicant
Kempe, A., et al.,“Algorithms for Weighted Multi-Tape Automata”, XRCE Research Report, vol. 2004, No. 031, Jun. 2004, pp. 1-28.Applicant
Kempe, A., “Extraction of Epsilon-Cycles from Finite-State Transducers”, Lecture Notes in Computer Science, vol. 2494, pp. 190-201, 2002.Applicant
Kiraz, G., et al., “Multi-Tape Automata for Speech and Language Systems: A Prolog Implementation”, D. Woods and S. Yu, editors, Automata Implementation, No. 1436 in Lecture Notes in Computer Science, Springer Verlag, Berlin, Germany, 1998.Applicant
Kiraz, G., “Linearization of Nonlinear Lexical Representations”, ACL Special Interest Group in Computational Phonology, 1997.Applicant
Mohri, M., et al., “Weighted Finite-State Transducers in Speech Recognition”, Computer Speech and Language, vol. 16, No. 1, pp. 69-88, Jan. 2002.Applicant
Mohri, M., et al., “The Design Principles of a Weighted Finite-State Transducer Library”, Theoretical Computer Science, vol. 231, No. 1, pp. 17-32, Jan. 2000.Applicant
Reape, M., et al., “Parallel Intersection and Serial Composition of Finite State Transducers”, Proceedings of the 12th Conference on Computational Linguistics, pp. 535-539, Aug. 1988.Applicant
Karttunen, M., et al., “Regular Expressions for Language Engineering”, Journal of Natural Language Engineering, 2(4):307-330, 1997.Applicant
Koskenniemi, K., et al., “Compiling and using finite-state syntactic rules”, Proc. of COLING '92, vol. 1, pp. 156-162, Nantes, France 1992.Applicant
Kuich, W., et al., “Semirings, Automata, Languages”, No. 5 in EATCS Monographs on Theoretical Computer Science, Springer Verlag, Berlin, Germany, 1986: Chapter 1 “Linear Algebra”, pp. 5-103.Applicant
Mohri, M., “Finite-State Transducers in Language and Speech Processing”, Computational Linguistics, 23(2):269-312, 1997.Applicant
Mohri, M., “Generic epsilon-removal and input epsilon-normalization algorithms for weighted transducers”, International Journal of Foundations of Computer Science, 13(1):129-143, 2002.Applicant
Mohri, M., et al., “A rational Design for a Weighted Finite-State Transducer Library”, Lecture Notes in Computer Science, 1436:144-158, 1998.Applicant
Mohri, M., et al., “Weighted Automata in Text and Speech Processing”, Proceedings of the 12th biennial European Conference on Artificial Intelligence (ECAI-96), Workshop on Extended finite state models of language, Budapest, Hungary, 1996.Applicant
Pereira, F., et al., “Speech Recognition by Composition of Weighted Finite Automata”, Emmanuel Roche and Yves Schabes, editors, Finite-State Language Processing. MIT Press, Cambridge, MA, pp. 431-453, 1997.Applicant
Schulz, K., et al., “Fast String Correction with Levenshtein Automata”, International Journal on Document Analysis and Recognition (IJDAR), 5(1):67-85, 2002.Applicant
Stethem, S., Review of “Morphology and Computation” by Richard Sproat, the MIT Press 1992, in Computational Linguistics, vol. 18, No. 4, pp. 552-554, Dec. 1992.Applicant

US 8,095,356 B2Grant

Method and apparatus for processing natural language using tape-intersection

Issue Date:2012-01-10

•7 Claims

•18 Drawing Sheets

Abstract

Operations for weighted and non-weighted multi-tape automata are described for use in natural language processing tasks such as morphological analysis, disambiguation, and entity extraction.

Metadata

Assignee

Xerox Corporation

Inventors

Andre Kempe
Franck Guingne
Florent Nicart