TRANFORMATION OF MODULAR FINITE STATE TRANSDUCERS
First Claim
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 semantics for defining ordered and unordered 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 ordered and unordered 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 Assignments
0 Petitions
Accused Products
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.
-
Citations
20 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 semantics for defining ordered and unordered 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 ordered and unordered 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
-
-
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 ordered and unordered 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 the ordered and unordered 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. - View Dependent Claims (13, 14, 15, 16, 17, 18)
-
-
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 ordered and unordered information defining ordered lists and unordered sets for the processes; and a transformation engine that analyzes the plurality of directed graph data structures based on a defined tree grammar and transduces the plurality of directed graph data structures to at least one MFST while preserving the ordered and unordered information of the plurality of directed graph data structures, wherein the transformation engine 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 to generate said at least one MFST, wherein it is determinable whether the resulting MFST accepts a non-empty input. - View Dependent Claims (20)
-
Specification