Back to results
US 7,010,476 B2Granted
Method and apparatus for constructing finite-state networks modeling non-concatenative processes
AssigneeXerox Corporation
InventorsLauri J Karttunen, Kenneth R Beesley
Life of this patent
Estimating the term…
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.
Claims20
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 more elements
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.
6 more elements
Dependencies are inferred from the claim text.