Generating automata for validating XML documents, and validating XML documents

A method comprising generating an automaton for validating an XML Document, including:

• 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 fourth step of dividing a transition function δ of said binary tree automaton into minimum arrays α and η which make δ[σ, i, j]=α[η[σ, i], j], said fourth step including the steps of:
• determining whether each of states represented by combinations of said arrays α and η is the state identifiable with another state;
• and
• setting a new status value to said identifiable state and determining by using said new status value the arrays α and η which make δ[σ, i, j]=α[η[σ, i], j].

A system for generating an automaton for validating an XML document, including:

• first means for reading a document type definition of the XML Document;
• second means for generating a binary tree automaton from said document type definition;
• and
• fourth means for dividing a transition function δ of said binary tree automaton into minimum arrays α and η which make δ[σ, i, j]=α[η[σ, i], j], said fourth means including the means for:
• determining whether each of states represented by combinations of said arrays α and η is the state identifiable with another state;
• and
• setting a new status value to said identifiable state and determining by using said new status value the arrays α and η which make δ[σ, i, j]=α[η[σ, i], j].

A program product including:

• a first procedure for reading a document type definition of an XML Document;
• a second procedure for generating a binary tree automaton from said document type definition;
• and
• a fourth procedure for dividing a transition function δ of said binary tree automaton into minimum arrays α and η which make δ[σ, i, j]=α[η[σ, i], j], said fourth procedure including the procedures for:
• determining whether each of states represented by combinations of said arrays α and η is the state identifiable with another state;
• and
• setting a new status value to said identifiable state and determining by using said new status value the arrays α and η which make δ[σ, i, j]=α[η[σ, i], j].

A program product for having a computer execute:

• a procedure for inputting an automaton represented by an alphabet Σ based on each tag name σ of a document type definition of an XML Document, a state set Q based on a state q, and a transition function δ represented by a single three-dimensional array of which element is a transition state comprised of three indexes of said σ, child element row information qc and sibling element row information qb of said σ, an initial state set I and a set of final states F;
• a procedure for inputting the XML document which is a subject of validating whether it suits said document type definition;
• means for generating a stack and pushing an initial state q0 to said stack included in the initial state set I;
• a seventh procedure for reading a tag σ of said XML document;
• an eighth procedure for determining whether said tag σ is an open tag;
• a procedure for, if it is determined to be an open tag by said eighth procedure, stacking said initial state q0 on said stack and returning to said seventh procedure thereafter;
• a procedure for, if it is determined to be a closed tag by said eighth procedure, taking two out of the head of said stack and rendering them as q1 and q2;
• a ninth procedure for examining said transition function δ by (σ, q1, q2) and determining whether there is a transition;
• a procedure for, if it is determined that there is the transition by said ninth procedure, rendering the transition state as q3 and stacking said q3 on said stack;
• a tenth procedure for determining whether all the tags of said XML document were read;
• a procedure for, if it is determined that there is an unread tag by said tenth procedure, returning to said seventh procedure;
• an eleventh procedure for, if it is determined that all the tags were read by said tenth procedure, determining whether the state recorded at the head of the stack is included in said set of final states F;
• and
• a procedure for, if the determination in said eleventh procedure is true, accepting said XML document as reasonable.

A program product for having a computer execute:

• a procedure for inputting an automaton represented by an alphabet Σ based on each tag name σ of a document type definition of an XML document, a state set Q based on a state q, arrays α and η showing a transitional relationship of the states, an initial state set I and a set of final states F, and wherein said arrays α and η are comprised of three indexes of said σ, child element row information qc and sibling element row information qb of said σ, and a single three-dimensional array of which element is a transition state is divided into minimum arrays α and η which make δ[σ, i, j]=α[η[σ, i], j];
• a procedure for inputting the XML document which is a subject of validating whether it suits said document type definition;
• a procedure for generating a stack and pushing an initial state q0 to said stack included in said initial state set I;
• a twelfth procedure for reading a tag σ of said XML document;
• a thirteenth procedure for determining whether said tag σ is an open tag;
• a procedure for, if it is determined to be an open tag by said thirteenth procedure, stacking said initial state q0 on said stack and returning to said twelfth procedure thereafter;
• a procedure for, if it is determined to be a closed tag by said thirteenth procedure, taking two out of the head of said stack and rendering them as q1 and q2;
• a fourteenth procedure for examining said array η by (σ, q1) and determining whether there is a transition;
• a fifteenth procedure for, if it is determined that there is the transition by said fourteenth procedure, rendering the results as m, examining the array α by (m, q2) and determining whether there is the transition;
• a procedure for, if it is determined that there is the transition by said fifteenth procedure, rendering the results as q3 and stacking said q3 on said stack;
• a sixteenth procedure for determining whether all the tags of said XML document were read;
• a procedure for, if it is determined that there is an unread tag by said sixteenth procedure, returning to said twelfth procedure;
• a seventeenth procedure for, if it is determined that all the tags were read by said sixteenth procedure, determining whether the state recorded at the head of the stack is included in said set of final states F;
• and
• a procedure for, if the determination in said seventeenth procedure is true, accepting said XML document as reasonable.