TRANSFORMATION OF MODULAR FINITE STATE TRANSDUCERS

• US 20080071801A1
• Filed: 09/15/2006
• Published: 03/20/2008
• Est. Priority Date: 09/15/2006
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Della-Libera, Giovanni M., Langworthy, David E., Lucco, Steven E.
• Granted Patent: US 7,624,075 B2
• Time in Patent Office: Days
• US Class Current: 707/100
• CPC Class Codes: G06F 16/9027 Trees

Abstract

A Q Framework, or QFX for short, is provided for performing efficient tree transformation in a generalized manner that achieves preservation of action semantics for FSTs that support action information in their representations across a diverse set of types of representations for FSTs. Among other features, the QFX also enables the preservation of ordered and unordered nest information while performing tree transformation, supports the transformation of non-deterministic data structures to a deterministic data structure and enables intersection operations on machines having action semantics.

Claims

1. A method for transforming at least one data structure specifying at least one tree structure in a computing system to at least one modular finite state transducer (MFST), comprising:

receiving at least one data structure specifying at least one tree structure representing at least one finite state transducer (FST) including action semantics for defining action information; and

for any type of finite state machine (FSM) model represented by the at least one data structure, transforming the at least one data structure to at least one MFST while preserving the action information of the at least one data structure in the at least one MFST, wherein said transforming includes performing any of an intersection, union and complement operation, or performing any transformation operation that is reducible to any of an intersection, union and complement operation, on the at least one data structure, wherein it is determinable whether the resulting MFST accepts a non-empty input.

2. The method of claim 1, wherein said transforming includes transforming the at least one data structure with a translation grammar that preserves the action information in the at least one MFST irrespective of the type of FSM model represented by the at least one tree structure specified by the at least one data structure.

3. The method of claim 1, wherein said transforming includes performing at least one control flow analysis algorithm on the FSTs represented by at least one data structure that preserves the action semantics information of the at least one data structure across any type of representation.

4. The method of claim 1, wherein said transforming includes transforming the at least one data structure with a pre-defined translation grammar that preserves both ordered and unordered nest information of the at least one data structure irrespective of the type of FSM model represented by the at least one tree structure specified by the at least one data structure.

5. The method of claim 1, wherein said receiving includes receiving at least one data structure specifying at least one directed graph structure representing the at least one FST including action semantics for defining action information.

6. The method of claim 4, wherein said receiving includes receiving at least one data structure specifying at least one extensible markup language (XML) document representing the at least one FST including action semantics for defining action information.

7. The method of claim 1, wherein said transforming includes performing an empty nest test on at least one data structure while preserving the action information.

8. The method of claim 1, wherein said transforming includes performing a structural compatibility test on at least two data structures while preserving the action information.

9. The method of claim 1, wherein said receiving includes receiving at least one data structure specifying at least one non-deterministic tree data structure and said transforming includes transforming the at least one data structure to a deterministic MFST.

10. A computer readable medium comprising computer executable instructions for performing the method of claim 1.

11. A computing device comprising means for performing the method of claim 1.

12. A transformation framework for transducing directed graph data structures representing finite state transducers (FSTs) to a modular finite state transducer (MFST) in a computing system, comprising:

means for storing a plurality of directed graph data structures of varying types for representing FSTs in a computing system including action semantics information of the plurality of directed graph data structures; and

a transducer that analyzes the plurality of directed graph data structures based on a pre-defined tree grammar and transduces the plurality of directed graph data structures to at least one MFST while preserving action semantics information of the plurality of directed graph data structures, wherein the transducer performs any of intersect, complement and union operations, or performs any transformations that are reducible to any of intersection, union and complement operations, on the plurality of directed graph data structures, wherein it is determinable whether the resulting MFST accepts a non-empty input.

13. The transformation framework of claim 12, wherein said transducer performs at least one control flow analysis algorithm on the FSTs represented by the plurality of directed graph data structures that preserves the action semantics information of the plurality of directed graph data structures across any type of directed graph representation.

14. The transformation framework of claim 12, wherein said transducer includes a transformation engine that performs specialized binding handling when transducing the plurality of directed graph data structures, wherein the specialized binding handling includes performing binding for the action semantics information during a pattern matching process for matching patterns of the plurality of directed graph data structures.

15. The transformation framework of claim 12, wherein said transducer in-lines at least one transducer definition as defined by a directed graph data structure of the plurality of directed graph data structures while preserving the action semantics information.

16. The transformation framework of claim 12, wherein said transducer compiles variable bindings of the plurality of directed graph data structures to slots in an activation record.

17. The transformation framework of claim 12, wherein said transducer performs register analysis of the FSTs represented by the plurality of directed graph data structures.

18. The transformation framework of claim 12, further comprising:

an interface for receiving a directed graph data structure of the plurality of directed graph data structures that defines and translates directed graph data structures according to said pre-defined tree grammar.

19. A compiler for transforming directed graph data structures representing finite state transducers (FSTs) to a modular finite state transducer (MFST) in a computing system, comprising:

a plurality of directed graph data structures representing FSTs for processes in a computing system including action information defining actions for the processes; and

a transducer that analyzes the plurality of directed graph data structures based on a pre-defined tree grammar and transduces the plurality of directed graph data structures to at least one MFST while preserving the action information of the plurality of directed graph data structures, wherein the transducer performs any of intersect, complement and union operations, or performs any transformation operations that are reducible to any of intersection, union and complement operations, on the plurality of directed graph data structures to generate said at least one MFST, wherein it is determinable whether the generated MFST accepts a non-empty input.

20. The compiler of claim 19, wherein the plurality of directed graph data structures are represented according to varying FST model types for representing action information.