Method and apparatus for constructing finite-state networks modeling non-concatenative processes

• US 20020091512A1
• Filed: 12/18/2000
• Published: 07/11/2002
• Est. Priority Date: 12/18/2000
• Status: Active Grant

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Karttunen, Lauri J., Beeseley, Kenneth R.
• Granted Patent: US 7,010,476 B2
• Time in Patent Office: Days
• US Class Current: 704/202
• CPC Class Codes: G10L 15/193 Formal grammars, e.g. finite state automata, context free grammars or word networks

Abstract

A system constructs finite-state networks. The system initially compiles an intermediate finite-state network from a source file of regular expressions. The intermediate finite-state network includes a delimited subpath that defines a substring having the form of a regular expression. The system subsequently produces an output finite-state network in which the delimited subpath is replaced with an FSN compiled from the substring encoded by the delimited subpath.

Claims

1. A method for producing finite-state networks, comprising:

producing an input finite-state network having a set of paths, with at least one of the paths in the set of paths containing a delimited subpath;

the delimited subpath encoding on an indicated side a delimited substring formatted as a regular expression;

creating a first temporary finite-state network by extracting from the first finite-state network the delimited subpath and eliminating the symbols on the indicated side of the delimited subpath;

creating a second temporary finite-state network by compiling the delimited substring formatted as a regular expression;

computing the cross-product of the first temporary finite-state network and the second temporary finite-state network to create a resulting finite-state network that is a compiled representation of the delimited substring; and

producing an output finite-state network by replacing the delimited subpath in the input finite-state network with the resulting finite-state network.

2. The method according to claim 1, wherein the delimited substring is produced by concatenating the symbols along the indicated side of the delimited subpath.

3. The method according to claim 1, wherein each finite-state network is represented using a data structure of a computer program.

4. The method according to claim 1, wherein the input finite-state network, the output finite-state network, and the third temporary finite-state network are finite-state transducers.

5. The method according to claim 1, wherein the first temporary finite-state network and the second temporary finite-state network are simple finite-state automata.

6. The method according to claim 1, wherein the input finite-state network and the second temporary finite-state network are formed using a regular expression compiler.

7. The method according to claim 1, wherein the output finite-state network encodes a relation that involves a nonconcatenative process.

8. The method according to claim 7, wherein the nonconcatenative process is described by the regular expression in the delimited substring.

9. The method according to claim 8, wherein the non-concatentative process described by the regular expression occurs in a natural language.

10. The method according to claim 7, wherein the nonconcatenative process is interdigitation.

11. The method according to claim 1, wherein the delimited substring is given by:

^ [X^ n ^ ], which denotes a concatenation of n instances of X, where;

^ [ is a special character string that serves as an opening delimiter;

^ ] is a special character string that serves as an closing delimiter;

X is a language; and

^ n denotes a concatenation of n instances of X.

12. The method according to claim 1, further comprising providing the output finite-state network to execute an application routine.

13. The system according to claim 11, wherein the application routine is a morphological analyzer.

14. The system according to claim 11, wherein the application routine is a morphological generator.

16. The system according to claim 15, further comprising a runtime module that accesses the output finite-state network to execute an application routine.

17. The system according to claim 16, wherein the application routine performs morphological analysis.

18. The system according to claim 16, wherein the application routine performs morphological generation.

19. The system according to claim 15, wherein the delimited substring is given by:

^ [X^ n A], which denotes a concatenation of n instances of X, where;

^ [ is a special character string that serves as an opening delimiter;

^ ] is a special character string that serves as an closing delimiter;

X is a language; and

^ n denotes a concatenation of n instances of X.

20. The system according to claim 15, further comprising a regular expression compiler for forming the input finite-state network and the second temporary finite-state network.

15. A system for producing finite-state networks, comprising:

a regular expression compiler for producing an input finite-state network having a set of paths, with at least one of the paths in the set of paths containing a delimited subpath;

the delimited subpath encoding on an indicated side a delimited substring formatted as a regular expression; and

a compile-replace module coupled to the regular expression compiler for;

creating a first temporary finite-state network by extracting from the first finite-state network the delimited subpath and eliminating the symbols on the indicated side of the delimited subpath;

creating a second temporary finite-state network by compiling the delimited substring formatted as a regular expression with the regular expression compiler;

computing the cross-product of the first temporary finite-state network and the second temporary finite-state network to create a resulting finite-state network that is a compiled representation of the delimited substring; and

producing an output finite-state network by replacing the delimited subpath in the input finite-state network with the resulting finite-state network.