Probabilistic Automata: Vidal et al., IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 27, NO. 7, JULY 2005
Presentation Paper for Formal Language class.
comment: The probabilistic extensions of NFA and CFG is reviewed in this paper. It's extensive and well organized.
The extension to Tree Automata is difficult to catch. Actually, considering the data that NFA or even Turing Machine accepts are 'strings', or sequence of characters, as aba and baa are considered different. But this structure is simple.
So how about adding stronger structure to it? Like tree structure? So the trees formed by characters (labels as called in the paper) will be processed by an Automata.
For a classical automata, characters in the string are eaten one by one, and the Automata changes its state correspondingly. For a tree automata, every subtree is eaten first before a new node can be eaten, and because the number of subtrees can vary between the nodes, so the dimension of the domain of transition functions is variable accordingly.
The paper Using Regular Tree Automata as XML schemas provides a good example of its application to parse XML documents (which is indeed instances of tree data). Although tree automata is interesting, I don't think it extends much on NFA, because every tree corresponds a string by ordered traversing.
No comments:
Post a Comment