Method and apparatus for constructing finite-state networks modeling non-concatenative processes
First Claim
Patent Images
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 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;
producing an output finite-state network by replacing the delimited subpath in the input finite-state network with the resulting finite-state network; and
performing language processing using the output finite-state network.
5 Assignments
0 Petitions
Accused Products
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.
31 Citations
20 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 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; producing an output finite-state network by replacing the delimited subpath in the input finite-state network with the resulting finite-state network; and performing language processing using the output finite-state network. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14)
-
-
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;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 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; producing an output finite-state network by replacing the delimited subpath in the input finite-state network with the resulting finite-state network; and a language processor that processes language using the output finite-state network. - View Dependent Claims (16, 17, 18, 19, 20)
-
Specification