Patent ID: 7055093
Filing Date: 2006-05-30
Classification: G06F,Y10S

Abstract:
1. A method comprising employing a computer for generating an automaton for validating an XML document, the step of employing comprising: a first step of reading a document type definition of the XML Document; a second step of generating a binary tree automaton from said document type definition; and a third step of determining and further minimizing said binary tree automaton, and generating a minimum deterministic binary tree automaton, wherein said binary tree automaton is represented by a tuple of five components of an alphabet Σ whose element is each tag name σ of said document type definition, a state set Q whose element is each state q, and the transition function δ which maps a triple of said σ, child element state qc and sibling element of said σ, child element state qc and sibling element state qb to a transition state, an initial state set I and a set of final states F, and grammar G of said document type definition is represented by a sequence of grammar declarations of a regular expression t to be constructed of a selection, a sequence, a repetition, an element, a terminal symbol, and a nonterminal symbol specified by predefined metacharacters and a nonterminal symbol X corresponding to said regular expression t, and said second step includes: a step of receiving said grammar G and a start symbol Xs as arguments; an initialization step of making Q={Xs}, δ={ }, I={ }, F={Xs}; and as to said t corresponding to the symbol X in said state set Q, a step of executing a recursive call function compute (t) of which argument is said t and rendering a return value thereof as Δ; a step of, if said Δ includes a terminal symbol ε, adding a state corresponding to said t to said I; and a step of, as to said σ in said Δ excluding said ε, adding to said δ the symbol X corresponding to said t as the element of the set of said σ, said qc and said qb, and said recursive call function compute (t) returns: if said t is said ε, a set {ε} based on said ε; if said t is the sequence of selection of a first regular expression t if said t is the sequence of said t if said t is the sequence of the repetitions of said t if said t is the sequence of said t adds to said Q the symbol X corresponding to said t returns the result set of said compute (t) of which argument is the sequence of said ε and said t if said t is other than the above.