By way of general background, finite state machines (FSMs), also known as finite state automata (FSA) are models of behavior for systems composed of states, transitions and actions. FSMs, or FSA, can be represented in a variety of conceptual ways, using state diagrams, state transition diagrams, state tables, labeled directed graphs, trees, etc, which preserve the relationships of states, transitions and actions that comprise the machines, or automata. There are different kinds of FSMs or FSA, equivalencies among them, and various known conversions among some of them as well.
Presently, some graph transducers and tree transducers exist that accomplish some aspects of transforming a set of systems modeled by FSTs, e.g., for some types of directed graph data structure(s), to form a new FST or set of FSTs, e.g., new directed graph data structure(s), however, such systems are limited for various reasons. The Extensible Stylesheet Language Transformation (XSLT), for instance, is an XML-based language used for the transformation of XML documents. When used to transform other XML documents, the document is not changed; rather, a new document is created based on the content of the existing XML document. The new document may be serialized (output) by the processor in standard XML syntax or in another format, such as HTML or plain text. XSLT is often used to convert data between different XML schemas or to convert XML data into web pages or PDF documents.
In essence, XSLT allows the creation of an XML document that describes the transformation of other XML documents, which may in turn be translated to different formats. However, XSLT fails to take into account action semantics that can be represented in FSTs. In this respect, an action might be “when in a pre-defined state, once certain information is recognized, e.g., a name, perform some action.” However, to the extent that such arbitrary actions can be defined for an FST, XSLT is unable to handle calls to such arbitrary actions as part of its transformative capabilities. In addition, XSLT is unable to perform all of the complement, intersect and union operations on machines.
Still further, existing transforms, such as XSLT, are also unable to match and compose FSMs having both ordered and unordered hierarchical information, such as ordered and unordered nests (e.g., as represented as a tree structure). While, in certain circumstances, there are some systems that can handle preservation of only ordered information when transforming trees, and there are some systems that can handle preservation of only unordered information when transformation, neither XSLT, nor any other known system, includes transformative capabilities that can preserve both ordered and unordered nests across directed graphs or tree structures. These and other deficiencies in the state of the art of transformation of finite state transducers will become apparent upon description of the various exemplary non-limiting embodiments of the invention set forth in more detail below.