Generating automata for validating XML documents, and validating XML documents

[0001] The present application is related to the following application even dated herewith: Attorney Docket Number JP920010142US1, entitled, SCHEMA GENERATION APPARATUS, DATA PROCESSORS, AND PROGRAM FOR PROCESSING IN THE SAME DATA PROCESSORS, having common inventors and priority, which is incorporated herein by reference in entirety for all purposes.

[0002] The present invention relates to generating automata for validating XML documents, and for validating the XML documents.

[0003] XML (extensible markup language) is receiving attention as means capable of general-purpose data exchange. The XML can provide document type definitions (DTD) XML schema or RELAX, etc., where an XML document matching with the document type definition is referred to as a valid XML. The valid XML is different from a well-formed XML which is merely grammatically well-formed, and its validity is assured including: a sequence of elements, whether or not the element is omissible; repetitions of the element, whether or not a hierarchical relationship of the elements is correct; and so on. It is possible, by handling such an XML document of which validity is assured, to render design, development and so on of applications easier so as to implement the data exchange of higher reliability.

[0004] Validation of the XML document is implemented by XML document analysis software (validator) called an XML parser or an XML processor. An overview of processing by a general validator is as follows. First, the document type definition is inputted to the validator. A table in compliance with the content model of the document type definition is generated for each element. Each of these tables is constituted to show a character string automaton for representing each content model of the document type definition, that is, a sibling relationship of the elements. Furthermore, a tree automaton for showing a rule of parentage of the elements is prepared. Next, the XML document to be validated is inputted to the validator. The above described table for each model and tree automaton are used so that the tree automaton reads execution results of each character string automaton and operates to validate the XML document.

[0005] The document type definition is illustrated by a case of the DTD. If a tag name appearing in the DTD is , a character string automaton M corresponding to is represented by a tuple of five components represented by M<, Q, , I, F>. Here, is a set (alphabet) comprised of all the element types which can emerge as children of the element type . Q is a state set based on a state q. is a table representing a transitional relationship determined by on which is based and the state q, and it prescribes a transition from a combination of (, q₁) to a state q₂. I is an initial state set, and F is a set of final states. It will be concretely described by taking the following sample DTD as an example.

[0006] (Sample DTD)

[0007] <ELEMENT title (PCDATA)>

[0008] <ELEMENT para (PCDATA)>

[0009] <ELEMENT doc (title, section)>

[0010] <ELEMENT section (title, (sectionpara))>

[0011] The character string automaton M_doc has the content model of an element doc represented by a tuple of five components of <_doc, Q_doc, _doc, I_doc, F_doc>. However, an alphabet _doctitle, section, a state set Q_doc0, 1, 2, an initial state set I_doc0, and a set of final states F_doc2. In addition, a transitional relationship table _doc is shown as table 1.

	TABLE 1
	Title	section
0I	1
1		2
2F		2

[0012] To be more specific, validity analysis on a row of child elements of the doc element is started from a state 0, and it is verified whether it finally reaches a state 2 while referring to a corresponding tag name in Table 1 and tracking the state thereof. It is valid if it reaches the final state.

[0013] Likewise, the character string automaton M_section has the content model of the element doc represented by a tuple of five components of <_section, Q_section, _section, I_section, F_section>. However, an alphabet _sectiontitle, section, para, a state set Q_section0, 1, 2, 3, an initial state set I_section0, a set of final states F_section2, 3. In addition, a transitional relationship table _section is shown as Table 2.

	TABLE 2
	Title	section	para
	0I	1
	1		2	3
	2F		2
	3F

[0014] As for M_title, and M_para, QIF0 and (empty set). A transitional relationship table is empty as shown by Table 3.

TABLE 3
0I

[0015] Thus, the automaton M is prepared for each element (tag name) . And a pushdown memory (stack) and an element reader are prepared so as to validate the XML document according to the following procedure 1. FIG. 13 is a flowchart showing procedure 1.

[0016] (Procedure 1)

[0017] In a starting step of the procedure, the stack is an empty stack . First, the tag is read (step 201). It is determined whether the read tag is an open tag or a closed tag (step 202), and the head of the stack s_o is read if it is the open tag (step 203). It is determined whether s_o is empty (step 204), and (M_o, I_o) is stacked on the stack if it is empty (step 205), and it returns to the step 201. If the stack is not empty in the step 204, it is assumed to be the read head of the stack s_o(M, q) here as shown in a step 206. A table , of the element is examined (step 207), and it is determined whether there is the transition (step 208). If there is the transition (here, q transitions to q as shown in a step 209), the head of the stack s_o is replaced with s_o(M, q) (step 210). Thereafter, (M, I) is stacked on the stack (step 205), and it returns to the step 201. If there is the transition in the step 208, the validation is a failure (step 211).

[0018] If it is determined that the read in the step 202 is the closed tag, the head of the stack s_o is read (step 212). It is the read head of the stack s_o(M, q) here as shown in a step 213. It is assumed to be determined whether q is included in F₉₄ (step 214), and the validation is a failure if it is not included therein (step 215). If it is determined to be included in step 214, the head of the stack s_o(M, q) is deleted (step 216). Thereafter, it is determined whether the XML document has ended (step 217), and it returns to the step 201 if it has not ended. The processing is finished if it has ended.

[0019] The above steps of the validation will be described in detail by taking the following XML document as an example.

(XML document)
	<doc>
	<title></title>
	<section>
	<title></title>
	<para></para>
	</section>
	</doc>

[0020] i) Read an open tag <doc>. Stack the automaton Md_doc and its initial state 0 in the stack. The stack is (M_doc, 0).

[0021] ii) Read an open tag <title>. Examine a table _doc by (title, 0). The state of Md_doc transitions from 0 to 1 ((M_doc, 0) at the head of the stack changes to (M_doc, 1)). Stack the automaton M_title and its initial state 0 on the stack. The stack becomes (M_title, 0), (M_doc, 1).

[0022] iii) Read a closed tag </title>. As the state 0 of M_title is the final state, it is accepted. (M_title, 0) is deleted from the stack. The stack becomes (M_doc, 1).

[0023] iv) Read an open tag <section>. Examine the table _doc by (section, 1). The state of M_doc transitions from 1 to 2 ((M_doc, 1) at the head of the stack changes to (M_doc, 2)). Stack the automaton M_section and its initial state 0 on the stack. The stack becomes (M_section, 0), (M_doc, 2).

[0024] v) Read the open tag <title>. Examine the table _section by (title, 0). The state of the automaton M_section transitions from 0 to 1 ((M_section, 0) at the head of the stack changes to (M_section, 1)). Stack the automaton M_title and its initial state 0 on the stack. The stack becomes (M_title, 0) (M_section, 1), (M_doc, 2).

[0025] vi) Read the closed tag </title>. As the state 0 of M_title is the final state, it is accepted. (M_title, 0) is deleted from the stack. The stack becomes (M_section, 1) (M_doc, 2).

[0026] vii) Read an open tag <para>. Examine the table _section by (para, 1). The state of M_section transitions from 1 to 3 ((M_section, 1) at the head of the stack changes to (M_section, 3)). Stack the automaton M_para and its initial state 0 on the stack. The stack becomes (M_para, 0) (M_section, 3), (M_doc, 2).

[0027] viii) Read a closed tag </para>. As the state 0 of M_para is the final state, it is accepted. (M_para, 0) is deleted from the stack. The stack becomes (M_section, 3) (M_doc, 2).

[0028] ix) Read a closed tag </section>. As the state 3 of M_section is the final state, it is accepted. (M_section, 3) is deleted from the stack. The stack becomes (M_doc, 2).

[0029] x) Read a closed tag </doc>. As the state 2 of M_doc is the final state, it is accepted.

[0030] As described above, it is verified that an XML document 1 satisfies the content model of the sample DTD.

[0031] Moreover, as the content model of the DTD is corresponding to a tree language of a so-called local class, the automaton M of each content model corresponds to the tag name . In the case of the document type definition having a single type constraint such as the XML schema, however, an automaton M_x of each content model does not correspond to the tag name . For this reason, in the case of applying the document type definition corresponding to a language class wider than DTD such as the XML schema or the RELAX, it requires an algorithm more complicated than the aforementioned validation of the DTD. For instance, in the case of the XML schema, it is necessary to calculate a table for acquiring, from a parent content model X and the tag name of a child, a content model Y of the child. If the table is acquired, the above described procedure 1 is expanded as follows. To be more specific, the tag name is stored in the above described stack in addition to the automaton M and the state q. The content model Y is acquired by using the table from the tag name read in the step 201 and a content model x corresponding to the automaton M_x currently at the head of the stack. And a table _x is examined by (Y, q) so as to obtain a transition state q. Otherwise, it is the same as the procedure 1. Thus, it is necessary to further use the table in addition to the table in sequence to obtain the transition state q.

[0032] Furthermore, it is necessary, for the sake of the validation of the document type definition corresponding to the tree language of a wider class such as the RELAX, to perform a more complicated validation operation such as seeing some tables in parallel.

[0033] As previously mentioned, the background art uses a plurality of transitional relationship tables by switching them. To be more specific, a complicated and intricate validation process is implemented. For this reason, a program size for the validation of the XML document becomes larger, so that it requires hardware resources to meet an increase in throughput of the validation (high computation speed, large memory capacity and so on). In addition, the automaton for each content model is generated from the document type definition each time the validation is performed in sequence to provide general versatility. Thus, the program size inevitably becomes larger and processing time becomes longer.

[0034] On the other hand, it is demanded that the XML document should be obtained from the Internet and so on and validated by using a small processing apparatus such as a portable telephone or a PDA (personal digital assistant). However, the validators in the past have the complicated process as previously mentioned, and so the load is excessive for such a small processing apparatus of which hardware resources are scarce. Moreover, as previously mentioned, the processing is more complicated and the problem becomes more serious in the cases of the XML schema and the RELAX than the DTD.

[0035] An aspect of the present invention is to simplify processing for the validation of an XML document and improve the processing speed.

[0036] Another aspect is to provide means for generating a transitional relationship table capable of simplifying the validation.

[0037] A further aspect is to render the size of the program required for validation smaller, and reduce the necessary memory size.

[0038] FIG. 1 is a block diagram showing functions as to an example of an automaton generation system and a validation system as one embodiment of the present invention;

[0039] FIG. 2 is a flowchart showing an example of the procedure for acquiring the binary tree automaton corresponding to the grammar G;

[0040] FIG. 3 is a flowchart showing an example of the recursive call function compute (t);

[0041] FIG. 4 is a flowchart showing an example of the procedure of the determination;

[0042] FIG. 5 is an overview flowchart showing an example of the procedure of the minimization;

[0043] FIG. 6 is a flowchart showing an example of the procedure for determining an identifiable state;

[0044] FIG. 7 is a flowchart showing an example of the procedure for calculating a representative source;

[0045] FIG. 8 is a flowchart showing an example of the procedure of the calculation of the new transition function ;

[0046] FIG. 9 is a flowchart showing an example of the procedure of the validation which is an embodiment of the present invention;

[0047] FIG. 10 is a block diagram showing the functions as to an example of the automaton generation system and the validation system as another embodiment of the present invention;

[0048] FIG. 11 is a flowchart showing an example of the procedure of the transitional relationship array division of this embodiment;

[0049] FIG. 12 is a flowchart showing an example of the procedure of the validation of this embodiment; and

[0050] FIG. 13 is a flowchart showing the procedure of the validation in the past.

[0051] 1 . . . Binary tree automaton generation module

[0052] 2 . . . Determination module

[0053] 3 . . . Minimization module

[0054] 4 . . . Processing module for determining an identifiable state

[0055] 5 . . . Representative source calculation module

[0056] 6 . . . New transitional relationship calculation module

[0057] 7 . . . Document type definition

[0058] 8 . . . Minimum deterministic binary tree automaton

[0059] 9 . . . Validation module

[0060] 10 . . . XML document

[0061] 11 . . . Validation results

[0062] 104 . . . Transitional relationship array division module

[0063] 105 . . . Binary tree automaton

[0064] 106 . . . Validation module

[0065] An overview of the present invention will be described as follows. To be more specific, validation of an XML document of the present invention detects a similarity among a plurality of table structures (character string automatons) for each content model of the document type definition. This similarity is utilized to coordinate the automaton of each content model and miniaturize it. Otherwise, the plurality of table structures of each content model are coordinated together with a table representing a rule of parentage of the elements so as to render them as a single table structure. And this table is minimized. Once a minimization operation is finished, the validation by a program size and a memory area far smaller than the background art becomes possible. In addition, it is possible to speed up the validation since access to data of the table becomes easier. It is possible, by using this table structure, to create a general-purpose validator for operating at high speed even with a small memory capacity.

[0066] The present invention is also described as follows by another representation. An example method of the present invention for generating the automaton for validating the XML Document includes a first step of reading the document type definition of the XML Document, a second step of generating a binary tree automaton from the document type definition, a third step of determining and further minimizing the binary tree automaton and generating a minimum deterministic binary tree automaton. To be more specific, the content model is described by regular representation in most document type definitions, which has a representation ability belonging to a language class called a regular tree language. The present invention converts such a document type definition represented by the language class of the regular tree language into the representation of the language class called a regular binary tree language. To be more specific, it generates the binary tree automaton for representing the document type definition. This binary tree automaton defines a single transitional relationship associated with a tag name of the document type definition, child element row information and sibling element row information of the tag. It is possible to simplify the validation of the XML Document by referring to the single transitional relationship. It is thereby possible to speed up processing of a validator, contract the program size, and render a memory area (stack capacity) smaller. For this reason, the validator using the present invention allows a practical use thereof by a small processing apparatus of which hardware resources are scarce.

[0067] Generally, a the method of the present invention for generating the automaton for validating the XML Document includes the first step of reading the document type definition of the XML Document, the second step of generating the binary tree automaton from the document type definition, and a third step of dividing a transition function of the binary tree automaton into minimum arrays and which make , i, j, i, j, and the fourth step includes the steps of determining whether each of states represented by combinations of the arrays and is the state identifiable with another state, and setting a new status value to the identifiable state and determining by using the new status value the arrays and which make , i, j, i, j. To be more specific, it is possible to divide the single array into the minimum arrays and which make , i, j, i, j. It is thereby possible to contract the table size.

[0068] Moreover, it is also possible to grasp the present invention as a system or a program.

[0069] Hereafter, particular example embodiments of the present invention will be described based on the drawings. However, the present invention can be implemented in many different forms, and should not be interpreted by limiting it to these embodiments. Moreover, the same elements are given the same numbers throughout the embodiments.

[0070] As is clear to those skilled in the art, the methods or the systems described in the following embodiments can also be implemented as the program usable on a computer.

[0071] Accordingly, the present invention can take the embodiment as hardware, the embodiment as software or the embodiment as a combination of the software and the hardware. The program can be recorded on any computer-readable medium such as a hard disk, a CD-ROM, an optical storage or a magnetic storage.

[0072] In addition, the following embodiments can use a general computer system as the system thereof. The computer system usable in the embodiments has the hardware resources generally provided to the computer system such as a central processing unit (CPU), a main memory (RAM), a nonvolatile storage (ROM), a coprocessor, an image accelerator, a cache memory and an input-output controller (I/O). In addition, it has an external memory such as the hard disk and communication means connectable to a network such as the Internet. The computer system includes various computers such as a personal computer, a workstation and a mainframe computer.

[0073] (Embodiment 1)

[0074] 1. System

[0075] FIG. 1 shows an example embodiment for a system. FIG. 1 is a block diagram showing functions as to an example of an automaton generation system and a validation system as one embodiment of the present invention. The automaton generation system of this embodiment includes a binary tree automaton generation module 1, a determination module 2 and a minimization module 3. The minimization module 3 includes a processing module 4 for determining an identifiable state, a representative source calculation module 5 and a new transitional relationship calculation module 6. The automaton generation system has a document type definition 7 inputted, and outputs a binary tree automaton 8. In addition, the validation system of this embodiment includes a validation module 9. The validation module 9 has the binary tree automaton 8 reflecting the content model of the document type definition 7 and an XML Document 10 which is a subject of the validation inputted, and outputs validation results 11. Moreover, each of the above described modules can implement its functions as an independent program component, or it is also possible to combine all or part of the functions thereof and implement them as a program module. Furthermore, it is also possible to divide the functions thereof and implement them as a plurality of program components.

[0076] The binary tree automaton generation module 1 receives an input of the document type definition 7, and generates a non-deterministic binary tree automaton for representing the content model of the document type definition 7. To be more specific, it generates, from the document type definition belonging to a language class of a regular tree language (so-called hedge grammar), the automaton belonging to a regular binary tree language class in a unique relationship therewith. The binary tree automaton is represented by a tuple of five components of <, Q, , I, F>. Here, is a set (alphabet) based on a tag name , and Q is a state set. is not a transition function per content model as with the past automaton, but is constituted as the single transition function (a table or an array) reflecting the content models of all the elements. The transition function of the binary tree automaton provides a transition state when the tag name , child element row information qc and sibling element row information qb thereof are specified. For instance, the transition function can be implemented by recording the transition state as the element of a three-dimensional array of which index is (, qc, qb). Moreover, while this embodiment illustrates the method for implementing the transition function by the arrays, it can be implemented by the table and any means of associating (, qc, qb) with the transition state. An initial state set I and a set of final states F are subsets of the state set Q, and an input document is accepted if it starts from a state q0 included in the initial state set I and reaches the state included in the set of final states F.

[0077] The determination module 2 has the function of determining the non-deterministic binary tree automaton generated by the binary tree automaton generation module 1. To be more specific, it converts a non-deterministic automaton of which state transition function is a multivalued function into a deterministic automaton which is a unique function. For instance, it is implemented by regarding the state set which the transition state function of the non-deterministic automaton can take as the state of the transition function of the deterministic automaton.

[0078] The minimization module 3 has the function of minimizing the size of deterministic binary tree automaton determined by the determination module 2. If a plurality of identifiable states are included in the determined deterministic binary tree automaton, it renders them as one state. The identifiable states are determined by the processing module 4. If the identifiable states are determined, the representative source which is the source of the smallest number, for instance, of the identifiable states is calculated by the representative source calculation module 5. From the set of the representative sources, a new transitional relationship is calculated by the calculation module 6.

[0079] The binary tree automaton 8 calculated by each of the above modules is represented by a tuple of five components of <, Q, , I, F>. This binary tree automaton 8 and the XML Document 10 are inputted so as to have the XML Document 10 validated by the validation module 9. The validation module 9 outputs the validation results 11 as to whether or not the inputted XML Document 10 is accepted by the binary tree automaton 8, where the XML Document 10 is valid if it is accepted, and it is not valid if it is not accepted.

[0080] Moreover, it is also possible to constitute the validation system by integrating the above described automaton generation system into the validation system. In addition, it is also feasible to independently constitute the automaton generation system and input the binary tree automaton 8 generated thereby to a general-purpose validation system so as to validate the XML Document.

[0081] 2. Method

[0082] The present invention may be embodied as a method implementing the procedures of the automaton generation system and the validation system shown in FIG. 1. The example method will be described by using a flowchart and a pseudocode. An overview of the procedure of the validation of the XML Document is as follows. To be more specific, the document type definition 7 is given, and the following procedures are performed to generate the minimum deterministic binary tree automaton 8. (1) Generation of the non-deterministic binary tree automaton by the binary tree automaton generation module 1. (2) Determination by the determination module 2. (3) Minimization by the minimization module 3. And the minimum deterministic binary tree automaton 8 and the XML document 10 are given, and (4) the validation by the validation module 9 is performed. The procedures will be described hereafter. Moreover, the number in parenthesis indicated at the beginning of each line shows a line number, and does not constitute the program. In addition, each code sequence is strictly pseudo and does not assure regular operation on a specific computer. To implement it so as to actually operate on the specific computer, it needs to be rewritten to comply with an operating system of the computer or the grammar unique to the programming language. There is no specific constraint to the programming language for implementing the system of this embodiment.

[0083] 2.0 Data Structure

[0084] Now the data structure is described. In the method (algorithm) described hereafter, the non-deterministic binary tree automaton <, Q, , I, F> and the deterministic binary tree automaton <, Q, , q0, F> have the following structure. To be more specific, the state set Q is a set (array) of certain objects. The initial state set I is the subset (array) of Q. The initial state q0 is the element of Q. The set of final states F is the subset (array) of Q. The transition function of the non-deterministic automaton is different form that of the deterministic automaton. When it is the non-deterministic automaton, the transition function is the function from a triplet of , q1, q2 to the subset of Q. When it is the deterministic automaton, the transition function is the function from a triplet of , q1, q2 to the element of Q. can be represented by a three-dimensional array and so on in either case. In addition, is corresponding to an XML element name and is a source of the alphabet .

[0085] 2.1 Grammar of the Document Type Definition (Hedge Grammar)

[0086] Grammar G of the regular tree language (hedge grammar) for representing the document type definition is represented by a string of grammatical declaration Xt comprised of a non-terminal symbol X and the following regular expression t and a start signal X_s. If Xt in the grammar G, t is represented by GX.

(regular expression t)
t::tt	(choice)
tt	(sequence)
t*	(Star)
<X>	(element)
	(terminal symbol)

[0087] 2.2 Conversion to the Binary Tree Automaton Corresponding to the Grammar G

[0088] FIG. 2 is a flowchart showing an example of the procedure for acquiring the binary tree automaton corresponding to the grammar G. In addition, a pseudocode 1 shown below is an example of the program (binary tree automaton generation module 1) for implementing the process corresponding to the procedure shown in FIG. 2. Moreover, the above described data structure and the algorithm for conversion to the binary tree automaton described here are the same as the method used for implementing the system called XDuce. The XDuce is described in detail in Haruo Hosoya. Regular Expression Types for XML. Phd thesis, The University of Tokyo, December 2000. (http://www. Kurims, Kyoto-u.ac.jp/hohosoya/papers/phdth.ps) or http://xduce.sourceforge.net, incorporated herein by reference in entirety for all purposes.

(Pseudocode 1)
(01.01)	proc main(G,Xs)
(01.02)	global Q : Xs
(01.03)	:
(01.04)	I:
(01.05)	F:
(01.06)	for t in Q
(01.07)	: compute(t)
(01.08)	if () then I : I t
(01.09)	for (t1,t2) in
(01.10)	,t1,t2 : ,t1,t2 t
(01.11)	rof
(01.12)	rof
(01.13)	return (Q,,I,F)
(01.14)	corp

[0089] The binary tree automaton is represented by the set of five terms as previously mentioned. The alphabet is a set of the elements which appear in the document type definition (that is, also the elements of the XML document), and the automaton is acquired if a set of four terms of (Q, , I, F) is acquired by the above described program. The state, that is, the elements of Q are corresponding to t appearing in the grammar and t obtained by rewriting it. A conversion algorithm depends on a recursive call of the procedure compute. t which is given as an argument of compute is rewritten until it takes the form of t1<X>. Intuitionally speaking, <X>is taken one by one out of the right end of t to obtain one transition, and also a new t is obtained. This operation is repeated until no more <X>can be taken out. Moreover, global represents a global variable. Switch t is assumed to branch according to the shape of t.

[0090] First, the grammar G representing the document type definition and the start signal Xs are passed as the arguments to the binary tree automaton generation module 1 (line number 01.01). The binary tree automaton generation module 1 refers to the received arguments, and performs initialization as shown between the line numbers 01.02 and 01.05 (step 12). Next, for all the t in the set Q (step 13, line number 01.06), the processing between the line numbers 01.07 and 01.11 is repeated (step 13, 20). The elements in Q increase in a loop (recursive call of compute), but they stop increasing before long. At line number 01.07, the recursive call function compute is executed with t as the argument, and is substituted in the set (step 14). The recursive call function compute will be described later.

[0091] It is determined whether a terminator is included in (step 15), and t is added to I if it is true (step 16, line number 01.08). To be more specific, if compute (t) includes , t is the initial state. Next, the following operation is performed for in excluding (line numbers 01.09 to 01.11, steps 17 to 19). To be more specific, t is added to , t1, t2 associating , t1 and t2 as one of its sources (line number 01.10, steps 18). When is taken out by compute (t), t provides the state to which can transition in a (t1, t2) state. When the above processing is finished, (Q, , I, F) is acquired (step 21, line number 01.13).

[0092] FIG. 3 is a flowchart showing an example of the recursive call function compute (t). A pseudocode 2 shown below is an example of the program for implementing the processing of compute (t).

(Pseudocode 2)
	(02.01)	proc compute(t)
	(02.02)	switch t
	(02.03)	case :
	(02.04)	return
	(02.05)	case t1 (t2 t3):
	(02.06)	return compute (t1 t2)
	compute (t2 t3)
	(02.07)	case t1 (t2 t3):
	(02.08)	return compute((t1 t2) t3)
	(02.09)	case t1 t2*:
	(02.10)	return compute((t1 t2*) t2)
	compute(t1)
	(02.11)	case t1 :
	(02.12)	return compute(t1)
	(02.13)	case t1 <X>:
	(02.14)	Q : Q t1,GX
	(02.15)	return (t1,GX)
	(02.16)	otherwise:
	(02.17)	return compute( t)
	(02.18)	hctiws
	(02.19)	corp

[0093] The function compute (t) has its processing branched according to the type of the argument t (line number 02.02, step 22).

[0094] If t is (line number 02.03, step 23), the set based on is returned as a return value of the function compute (line number 02.04, step 24).

[0095] If t is sequence and the term on the right thereof is choice, that is, t is a sequence of selection of a first regular expression (t1), a second regular expression (t2) and a third regular expression (t3) (line number 02.05, step 25), the compute (t) of which argument is the sequence of t1 and t2 is recursively called, and a sum set of the results thereof and the result set of the recursive compute (t) of which argument is the sequence of t1 and said t3 is returned as the return value (line number 02.06, step 26).

[0096] If t is the sequence and the term on the right thereof is the sequence, that is, in the case of the sequence of t1 with the sequence of t2 and t3 (line number 02.07, step 27), the result set of the compute (t) of which argument is the sequence of t1 and t2 with the sequence of t3 is returned as the return value (line number 02.08, steps 28).

[0097] If t is the sequence and the term on the right thereof is repetition of an arbitrary number of times (star), that is, in the case of the sequence of the repetitions of t1 and t2 (line number 02.09, step 29), the sum set of the result set of the compute (t) of which argument is the sequence of the repetitions of t1 and t2 and the sequence of t2 and the result set of the compute (t) of which argument is t1 is returned as the return value (line number 02.10, step 30).

[0098] If t is the sequence and the term on the right thereof is a terminal symbol, that is, if t is the sequence of t1 and (line number 02.11, steps 31), the result set of the compute (t) of which argument is t1 is returned as the return value (line number 02.12, step 32).

[0099] If t is the sequence and the term on the right thereof is the element, that is, if t is the sequence of t1 and (line number 02.13, step 33), and a state element (GX) corresponding to t1 and t is added to Q (line number 02.14), and (t1, GX) is returned as the return value (line number 02.14, step 34).

[0100] If t is other than the above (line number 02.15, step 35), the compute (t) of which argument is the sequence of and t is recursively called (line number 02.16, step 36). To be more specific, is added to t as a dummy to take form of the sequence and recursively call the compute (t) so as to apply to other cases.

[0101] The recursive call function compute as above is executed to take the element out of t and rewrite t to t1. And this is added to Q which is a global variable. Thus, Q increases in conjunction with execution of the compute. However, Q stops increasing before long, and the compute (t) will be calculated for all the elements t of Q.

[0102] 2.3 Determination

[0103] Now the determination process is described. Determination is the process of constructing the deterministic binary tree automaton from the non-deterministic binary tree automaton. The deterministic binary tree automaton is created from the state set Q, the transition function and the set of final states F (subset of Q) of the non-deterministic binary tree automaton. The basic idea is to regard the set of the states which the non-deterministic binary tree automaton can take as the state. To be more specific, the state of the deterministic binary tree automaton is the subset of Q.

[0104] FIG. 4 is a flowchart showing an example of the procedure of the determination. In addition, a pseudocode 3 shown below shows an example of the program for implementing the procedure for acquiring the deterministic binary tree automaton <, Q, , q0, F> from the non-deterministic binary tree automaton <, Q, , q0, F>. As there is no change in and q0, a set of three terms of (Q, , F) can be acquired from the set of three terms of (Q, , F).

(Pseudocode 3)
	(03.01)	q0 :I
	(03.02)	Q : I
	(03.03)	for (S1,S2) in QQ
	(03.04)	for in do
	(03.05)	target :
	(03.06)	for each element s1 in S1 do
	(03.07)	for each element s2 in S2 do
	(03.08)	target : target ,s1,s2
	(03.09)	rof
	(03.10)	rof
	(03.11)	if target F is not empty
	(03.12)	then F : F target
	(03.13)	Q : Q target
	(03.14)	,S1,S2 : target
	(03.15)	rof
	(03.16)	rof

[0105] First, as shown at the line numbers 03.01 and 03.02, the initialization is performed (step 37). The initialization at the line number 03.01 means that the set comprised of the entire start state is the start state, and the line number 03.02 means that the state acquired at this point in time is only the start state.

[0106] As for QQ, that is, each of the sibling element row information and the child element row information, any unexamined pair (S1, S2) of the element thereof is taken out (line number 03.03, step 38). A set target is prepared for an arbitrary symbol in the alphabet (line number 03.04, step 39). First, the element of the target is rendered empty (line number 03.05, step 40). Next, the following operation is repeated as to each element of a state s1 belonging to S1 and further a state s2 belonging to S2. To be more specific, all the states reachable from (, s1, s2) are added to the target (line number 03.06 to 3.10, steps 41 to 45). Next, it is determined whether an intersection of the target and F is empty (line number 03.11, steps 46), and the target is added to F if the determination is true (line number 03.12, step 47). If the above described determination is false, it proceeds to a step 48. In the step 48, the target is added to Q (line number 03.13), and a destination to be reached from (, S1, S2) is rendered as the target (line number 03.14, step 48).

[0107] (Q, , F) can thus be acquired, and the deterministic automaton <, Q, , q0, F> is acquired.

[0108] 2.4 Minimization

[0109] Minimization is, of the states of the deterministic automaton generated by the above described determination, to find the identifiable states and simplify the state transition function. FIG. 5 is an overview flowchart showing an example of the procedure of the minimization. The procedure of the minimization includes the following steps. (1) Determination of the identifiable state (step 51), (2) calculation of the representative source (step 52), and (3) calculation of the new transition function (step 53).

[0110] (1) Determination of the Identifiable State

[0111] FIG. 6 is a flowchart showing an example of the procedure for determining the identifiable state. In addition, a pseudocode 4 shown below shows an example of the program for implementing the process of determining the identifiable state. First, the number of states is assumed to be n. In addition, the states of the automaton are assumed to be represented by integer values from 0 to n1. The basic idea is to find the identifiable states. The procedure described below gradually determines those which are not identifiable. The following procedure creates a two-dimensional array Rn, n, and if it turns out that a certain state i and a state j are not identifiable, it sets both Ri, j and Rj, i as false.

(Pseudocode 4)
	(04.01)	for i : 1 to n do
	(04.02)	for j : 1 to n do
	(04.03)	if only one of qi and qj is final state
	(04.04)	Ri,j : false
	(04.05)	Rj,i : false
	(04.06)	fi
	(04.07)	rof
	(04.08)	rof
	(04.09)	loop
	(04.10)	noChange : true
	(04.11)	for a in do
	(04.12)	for i : 1 to n do
	(04.13)	for j : 1 to n do
	(04.14)	for k : 1 to n do
	(04.15)	if (not Ra,i,k, a,j,k
	(04.16)	or not Ra,k,i, a,k,j)
	(04.17)	then Ri,j : false ;
	(04.18)	Rj,i : false ;
	(04.19)	noChange : false
	(04.20)	fi
	(04.21)	rof
	(04.22)	rof
	(04.23)	rof
	(04.24)	rof
	(04.25)	exit if noChange
	(04.26)	pool

[0112] First, all the sources of R are initialized as true (step 54). To be more specific, none of them is clearly unidentifiable at the beginning.

[0113] A for loop at the line numbers 04.01 to 04.08 performs the process wherein the final state is not identifiable with the state which is not the final state. To be more specific, the following operation is repeated for i of 1 to n (line number 04.01, step 55) and further for j of 1 to n (line numbers 04.02, steps 56) (line numbers 04.07 and 04.08, steps 59 and 60). It is determined whether only one of qi and qj is the final state (line number 04.03, step 57). If the above described determination is true, it sets Ri, j and Rj, i as false (line numbers 04.04 and 04.05, step 58).

[0114] Next, two states which reach the two states apparently unidentifiable are not identifiable, either. The loop at the line numbers 04.09 to 04.26 performs that determination. To be more specific, at the line numbers 04.10, noChange flag signifying whether or not the status of R is changed is set as true (step 62), the following operation is repeated for a in , i of 1 to n, further for j of 1 to n, and further for k of 1 to n (line number 04.11 to 04.24, steps 63 to 72). To be more specific, it is determined, as to arbitrary i, j, k and , whether the two states , i, k and , j, k are distinguished by R, or whether the two states , k, i and , k, j are distinguished by R (line number 04.15 to 04.16, step 67). When this determination is true, it renews R to distinguish the states i and j. To be more specific, it sets Ri, j and Rj, i as false, and also sets noChange as false (line number 04.17 to 04.19, steps 68). And if noChange is true, it gets out of the loop (line number 04.05, step 73). When this loop is terminated, the identifiable state is determined.

[0115] (2) Calculation of the Representative Source

[0116] Next, an array Repn is created. This is the array for indicating the representative source (the one of the lowest number of the identifiable states). FIG. 7 is a flowchart showing an example of the procedure for calculating the representative source. In addition, a pseudocode 5 shown below shows an example of the program for implementing the calculation of the representative source.

(Pseudocode 5)
	(05.01)	for every i from 1 to n
	(05.02)	Repi: 0
	(05.03)	rof
	(05.04)	for i : 1 to n do
	(05.05)	if Repi 0 then
	(05.06)	for j : 1 to n do
	(05.07)	if Ri,j then Repj : i
	(05.08)	rof
	(05.09)	fi
	(05.10)	rof

[0117] First, Repi is initialized by 0 for all i of 1 to n (line number 05.01 to 05.03, step 75). It indicates that the representative source is unknown in the initial state. Next, it is determined whether Repi is 0 for i of 1 to n (line number 05.05, step 77), so that i itself becomes the representative source if it is 0. And in this case (if it is 0), it is determined whether Repi, j is true as to j of 1 to n (step 79), and i is substituted into Repj if it is true (line number 05.07, step 80). To be more specific, i is written as the representative source to other states which are identifiable.

[0118] (3) Calculation of the New Transition Function

[0119] FIG. 8 is a flowchart showing an example of the procedure of the calculation of the new transition function . In addition, a pseudocode 6 shown below shows an example of the program for implementing the calculation of the new transition function .

(Pseudocode 6)
	(06.01)	for i : 1 to n do
	(06.02)	if Repi i then
	(06.03)	for j : 1 to n do
	(06.04)	if Repj j then
	(06.05)	for a in do
	(06.06)	a,i,j : Repa,i,j
	(06.07)	rof
	(06.08)	fi
	(06.09)	rof
	(06.10)	fi
	(06.11)	rof

[0120] As shown above, if Repi is i for i of 1 to n (line number 06.02, step 84) and Repj is j for j of 1 to n (line number 06.04, step 86), Repa, i, j is substituted into a, i, j for each element a in (line number 06.06, step 88). As a, i, j may not be the representative source, the representative source is obtained by using Rep. This is repeated for all the i and j.

[0121] The procedures described in the above 2.1 to 2.4 are performed so as to generate the minimum deterministic binary tree automaton 8 from the document type definition described in the hedge grammar.

[0122] 2.5 Concrete Example of the Minimum Deterministic Binary Tree Automaton

[0123] The automaton generated by the procedures of the above 2.1 to 2.4 is shown below by taking the aforementioned sample DTD as an example. The minimum deterministic binary tree automaton is represented by the above described set of five terms of <, Q, , q0, F>. doc, title, section, para, Q0, 1, 2, 3, 4, q00, F4, and is as shown in Table 4.

	TABLE 4
	doc	title	section	para
	0I	1	2	3	4F	0I	1	2	3	4F	0I	1	2	3	4F	0I	1	2	3	4F
0I				4		1
1													3	3		2
2
3													3	3
4F

[0124] Thus, the automaton of this embodiment is represented by a single table. For this reason, the procedures of the validation of the XML document described below are simplified. In addition, the memory area (stack capacity) for the validation can be rendered smaller. Moreover, in Table 4, the top side corresponds to the tag name and the child element row information, and the left side corresponds to the sibling element row information. In addition, the table of Table 4 can be implemented by a hash table since it is generally loose.

[0125] 2.6 Validation of the XML Document

[0126] The procedures for validating the XML document by using the above described minimum deterministic binary tree automaton will be described below. FIG. 9 is a flowchart showing an example of the procedure of the validation of this embodiment. In addition, a pseudocode 7 is an example of the program for implementing the procedure of the validation. Moreover, the automaton is represented by <, Q, , I, F>, and the transitional relationship among the states q1, q2 and q3 is , q1, q2->q3. The structure of the XML document is associated with the occurrence rows of the following two events by a SAX parser for instance. To be more specific, startElement (String tag) is executed if a start tag is read, and endElement (String tag) is executed if an end tag is read.

(Pseudocode 7)
	(07.01)	global stack : q0
	(07.02)	proc startElement(tag)
	(07.03)	stack.push(q0)
	(07.04)	corp
	(07.05)	proc endElement(tag)
	(07.06)	q1 : stack.pop( )
	(07.07)	q2 : stack.pop( )
	(07.08)	q3 : binarysearch(,q1,q2)
	(07.09)	stack.push(q3)
	(07.10)	corp

[0127] First, a stack structure stack is prepared, and the initial state of the automaton is rendered as q0 (line number 07.01, step 92). The tag is read (step 93) to determine whether is an open tag or a closed tag (step 94). As described above, the startElement (String tag) method is executed in the case of the open tag. In the startElement ( ) method, the initial state q0 is stacked on the stack (line number 07.03, step 95). Thereafter, it returns to the step 93. The endElement (String tag) method is executed in the case of the closed tag. In the endElement ( ) method, q1 and q2 are sequentially taken out of the head of the stack (line numbers 07.06 to 07.07, step 96), and the table 6 is examined by (, q1, q2) (line number 07.08, step 97). It is determined whether or not there is a transition in the table (step 98), and the validation is a failure if there is no transition (step 99). Moreover, the return value of binarysearch( ) is assumed to be q3 (line number 07.08). Next, q3 is stacked on the stack (line number 07.09, step 100), and it is determined whether the XML document has ended (step 101). If it has not ended (if there is an unread tag), it returns to the step 93. If the XML document has ended, it is determined whether q3 is included in the final state F (step 102). When q3 is included in the final state, the XML document is accepted and is determined as reasonable. On the other hand, if q3 is not included in the final state, the validation is a failure (step 103). The XML document can be validated as described above.

[0128] The above procedures will be described in detail below by taking the above described XML document as an example.

[0129] i) First, the initial state 0 is stacked on a stack , and an open tag <doc> is read by a stack 0. A copy of the initial state is stacked on the stack, and the stack becomes 0, 0.

[0130] ii) An open tag <title> is read by the stack 0, 0. The stack becomes 0, 0, 0.

[0131] iii) A closed tag </title> is read by the stack 0, 0, 0. Two of the stack contents are taken out. If is examined by a rule of (title, 0, 0), the state consequently transitions to 1. 1 is stacked on the stack, and the stack becomes 1, 0.

[0132] iv) An open tag <section> is read by the stack 1, 0. The stack becomes 0, 1, 0. Furthermore, the open tag <title> is read. The stack becomes 0, 0, 1, 0.

[0133] v) The closed tag </title> is read by the stack 0, 0, 1, 0. Two of the stack contents are taken out. As it transitions by the rule of (title, 0, 0), the state transitions to 1 and it is stacked on the stack. The stack becomes 1, 1, 0.

[0134] vi) An open tag <para> is read by the stack 1, 1, 0. The stack becomes 0, 1, 1, 0.

[0135] vii) A closed tag </para> is read by the stack 0, 1, 1, 0. Two of the stack contents are taken out. As it transitions by the rule of (para, 1, 0), the state transitions to 2 and it is stacked on the stack. The stack becomes 2, 1, 0.

[0136] viii) A closed tag </section> is read by the stack 2, 1, 0. Two of the stack contents are taken out. As it transitions by the rule of para (1, 2), the state consequently transitions to 3. It is stacked on the stack. The stack becomes 3, 0.

[0137] ix) A closed tag </doc> is read by the stack 3, 0. As it transitions by the rule of doc (0, 3), the state transitions to 4. 4 is the final state, and the document is accepted.

[0138] According to the procedures of this embodiment, an amount of calculation is O (n) against a document size n. While this is the same sequence as the past technology, it is implemented by a simpler operation than the past technology. According to this embodiment, the automaton for validating the XML document is represented by the single transition function, so that the program for validating the XML document can be simplified. Thus, it is possible, by rendering the program size smaller, to perform sufficiently practical validation of the XML document even with a small computer (small information processing apparatus) of which hardware resources are scarce. In addition, it is possible to render the stack capacity smaller since the validation can be performed by referring to the single automaton. The merit of implementing the present invention with the small computer is also significant on this point.

[0139] Moreover, if the transition function of the minimum deterministic binary tree automaton is represented by a four-term set (array) of (, q1, q2, q3), and if the array is sorted, the procedure binarysearch can efficiently calculate , q1, q2 by a binary search. In this case, it is possible to reduce the memory amount to be used although efficiency of calculation is slightly lower than the above described example using the three-dimensional array.

[0140] (Embodiment 2)

[0141] FIG. 10 is a block diagram showing the functions as to an example of the automaton generation system and the validation system as another embodiment of the present invention. Components thereof are the same as the embodiment 1 except a transitional relationship array division module 104 and a validation module 106 shown in FIG. 10. In addition, a binary tree automaton 105 generated by the system for generating automata of this embodiment is also different from the embodiment 1. Hereafter, only the configurations different from the embodiment 1 will be described.

[0142] The transitional relationship array division module 104 has the function of dividing the transition function of the binary tree automaton 8 generated by the above described binary tree automaton 1, determination module 2 and minimization module 3. It is possible, by dividing the transition function, to further contract the size thereof. The validation module 106 implements the validation suited to the automaton of which state transitional relationship is represented by such a divided transition function. Hereafter, the method of this embodiment will be described.

[0143] FIG. 11 is a flowchart showing an example of the procedure of the transitional relationship array division of this embodiment. In addition, a pseudocode 8 shows an example of the program for implementing the division of the transitional relationship array. The following procedure acquires the minimum and which make , i, j, i, j.

(Pseudocode 8)
(08.01)	for i : 1 to n do
(08.02)	for j : 1 to n do
(08.03)	for k : 1 to n do
(08.04)	for in do
(08.05)	for in do
(08.06)	if (,i,k ,j,k)
(08.07)	R,i,,j false
(08.08)	rof
(08.09)	rof
(08.10)	rof
(08.11)	rof
(08.12)	rof
(08.13)	for in do
(08.14)	for i : 1 to n do
(08.15)	if ,i 0 then
(08.16)	val : cnt
(08.17)	for in do
(08.18)	for j : 1 to n do
(08.19)	if R,i,,j then ,j : val
(08.20)	fi
(08.21)	rof
(08.22)	rof
(08.23)	for k : 1 to n do
(08.24)	val,k : ,i,k
(08.25)	rof
(08.26)	fi
(08.27)	rof
(08.28)	rof

[0144] As described in the embodiment 1, it is assumed that the generation, determination and minimization of the non-deterministic binary tree automaton are finished, and the minimum deterministic binary tree automaton of which transitional relationship is represented by the single table is sought.

[0145] A four-dimensional array R, i, , j (, are the sources of , and i, j are integers from 1 to n) is created, and all the sources are initialized as true (step 107). This four-dimensional array shows that the pairs (, i) and (, j) are not distinguishable if seen from , that is, , i and , j can return the same value.

[0146] Next, the following operation is repeated for i, j and k of 1 to n, and further for the elements , in (line numbers 08.01 to 08.12, steps 108 to 120). It is determined whether , i, k and , j, k are a mismatch (line number 08.06, step 114), and if they are a mismatch, Ri, , j is set as false (line number 08.07, step 115). To be more specific, R is set as false for the pairs (, i) and (, j) which are distinguishable if seen from .

[0147] Next, a unique value is established to the set of (, i) to which the same value may be returned, and it is set as the value of , i. In addition, the value of , i is used to establish so as to imitate the result of the original (line numbers 08.13 to 08.28, steps 121 to 135). Moreover, it is assumed that every , i is initialized by 0, and a counter variable cnt is initialized by 0.

[0148] The following operation is repeated for in and further for i of 1 to n (line numbers 08.13 to 08.23, steps 121 to 135). It is determined whether , i is 0 (line number 08.15, step 123), and if it is 0, it will be the representative source. cnt is substituted into a variable val (line number 08.16, step 124). Moreover, val is a value showing a new state, and it becomes the return value of . Moreover, cnt increases by 1. Furthermore, the following operation is repeated for in and further for j of 1 to n (line numbers 08.17 to 08.22, steps 125 to 130). It is determined whether R, i, , j is true (steps 127), and val is substituted into , j if it is true (step 128, line number 08.19). To be more specific, always returns the same value val to (, j) which is not distinguished from (, i). Next, for k of 1 to n, , i, k is substituted into val, k. To be more specific, the transition of a by val is set.

[0149] New tables and are outputted by such an operation. To be more specific, the binary tree automaton 105 generated by this embodiment is represented by a set of six terms of <, Q, , , I, F>. Such an automaton allows the size to be smaller than the case of the embodiment 1 wherein the arrays and representing the transitional relationship are represented by the single array (table).

[0150] The automaton generated by the procedure of this embodiment is shown below by taking the above described sample DTD as an example. To be more specific, it is doc, title, section, para, Q0, 1, 2, 3, 4, I0, F4, and is as shown in Table 5 and is as shown in Table 6. Moreover, shows the transitional relationship of QR>Q, and shows the transitional relationship of Q>R. It is assumed to be Ri, ii, iii, iv

	TABLE 5
	doc	title	section	para
0I		ii		iv
1
2			iii
3	i		iii
4F

[0151]

	TABLE 6
	i	ii	iii	iv
0I	4	1
1			3	2
2
3			3
4F

[0152] Moreover, while the number of transitions, that is, the size of a domain of the table is increased compared to the case of the embodiment 1, it will be rendered less than this embodiment for a larger automaton.

[0153] Next, the procedure of the validation of this embodiment will be described. FIG. 12 is a flowchart showing an example of the procedure of the validation of this embodiment. The steps 136 to 140 are the same as the steps 92 to 96 in FIG. 9 of the embodiment 1.

[0154] The table is examined by (, q1) by using q1 and q2 taken out in the step 140 (step 141). It is determined whether or not there is a transition in the table (step 142), and the validation is a failure if there is no transition (step 143). If there is the transition, the results are rendered as m, and the table is examined by (m, q2) (step 144). It is determined whether or not there is the transition in the table (step 145), and the validation is a failure if there is no transition (step 146). If there is the transition, the results are rendered as q3, and q3 is stacked on the stack (step 147), and it is determined whether or not the XML document has ended (step 148). If it has not ended (if there is an unread tag), it returns to the step 137. If the XML document has ended, it is determined whether q3 is included in the final state F (step 149).

[0155] When the state q3 is included in the final state, the XML document is accepted and is determined as reasonable. On the other hand, if the state q3 is not included in the final state, the validation is a failure (step 150). The XML document can be validated by using the automaton of a smaller table (array) size as described above.

[0156] Moreover, it is also possible to combine a binary search method with the above described method. In this case, the memory amount to be used can be further significantly reduced.

[0157] According to this embodiment, the transition function (a table or an array) of the automaton for validating the XML document is rendered smaller, and so the capacity of the required memory can be small. To be more specific, the present invention can exert its effects remarkably on the small information processing apparatus of which hardware resources are scarce.

[0158] In addition, according to a review by the inventors hereof, it has the effects that the program size of the validator of this embodiment 2 is contracted to approximately 86 percent of that of the corresponding portion of the validator in the past, the size of the automaton in the form of this embodiment is contracted to approximately 70 percent of that of the automaton in the past, and the time for the validation is reduced to approximately 43 percent thereof.

[0159] While the invention implemented by the inventors hereof was described above based on the embodiments, the present invention is not limited to the above described embodiments and is capable of various changes within the range not to deviate from the outline thereof.

[0160] For instance, it is possible to add a lookahead operation to the operation of the binary tree automaton. To be more specific, 0 of the initial state was always stacked on the stack, irrespective of what was read as the open tag in the validating operation in the above described embodiments. It is changed to the operation wherein the initial state is distinguished depending on what was read as the open tag. This change allows the table to be further contracted without altering the efficiency of the validation.

[0161] In addition, while the example of dividing the table into two after determining and minimizing the non-deterministic binary tree automaton was described in the above described embodiment 2, the determination and minimization are not essential. The effects of the present invention can also be expected by dividing a transition table of the non-deterministic binary tree automaton into two as in the embodiment 2.

[0162] Advantages of the Invention

[0163] Of the inventions disclosed herewith, the effects obtained by the representative ones are as follows. To be more specific, it is possible to simplify the processing for the validation of the XML document and improve the processing speed. In addition, it is possible to provide the means for generating the transitional relationship table capable of simplifying the validation. Furthermore, it is feasible to render the size of the program required for the validation smaller and reduce the necessary memory size.

[0164] The present invention can be realized in hardware, software, or a combination of hardware and software. A visualization tool according to the present invention can be realized in a centralized fashion in one computer system, or in a distributed fashion where different elements are spread across several interconnected computer systems. Any kind of computer systemor other apparatus adapted for carrying out the methods and/or functions described hereinis suitable. A typical combination of hardware and software could be a general purpose computer system with a computer program that, when being loaded and executed, controls the computer system such that it carries out the methods described herein. The present invention can also be embedded in a computer program product, which comprises all the features enabling the implementation of the methods described herein, and whichwhen loaded in a computer systemis able to carry out these methods.

[0165] Computer program means or computer program in the present context include any expression, in any language, code or notation, of a set of instructions intended to cause a system having an information processing capability to perform a particular function either directly or after conversion to another language, code or notation, and/or reproduction in a different material form.

[0166] Thus the invention includes an article of manufacture which comprises a computer usable medium having computer readable program code means embodied therein for causing a function described above. The computer readable program code means in the article of manufacture comprises computer readable program code means for causing a computer to effect the steps of a method of this invention. Similarly, the present invention may be implemented as a computer program product comprising a computer usable medium having computer readable program code means embodied therein for causing a a function described above. The computer readable program code means in the computer program product comprising computer readable program code means for causing a computer to effect one or more functions of this invention. Furthermore, the present invention may be implemented as a program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for causing one or more functions of this invention.

[0167] It is noted that the foregoing has outlined some of the more pertinent objects and embodiments of the present invention. This invention may be used for many applications. Thus, although the description is made for particular arrangements and methods, the intent and concept of the invention is suitable and applicable to other arrangements and applications. It will be clear to those skilled in the art that modifications to the disclosed embodiments can be effected without departing from the spirit and scope of the invention. The described embodiments ought to be construed to be merely illustrative of some of the more prominent features and applications of the invention. Other beneficial results can be realized by applying the disclosed invention in a different manner or modifying the invention in ways known to those familiar with the art.