Grammar vs. Rules

Diagnostics in XML document validation

Petr Nálevka

University of Economics, Prague Department of Information and Knowledge Engineering

W. Churchill Sq. 4
130 67 Praha 3
Czech Republic
petr@nalevka.com

Abstract

Regular grammars has been used over decades for different formal language validation tasks because of their relative easiness of expression but more important because of their low computing expenses. Validation using regular grammars is commonly used also for XML document validation. In this case human understandable grammar definitions are converted into regular expressions which are evaluated against the input document. This approach is fast, straightforward but it lacks good diagnostics. It is hard for the validator engine to track grammar errors back to the information domain and provide some useful error messages understandable for the author.
An alternative approach tends to be rule-based validation which is closely related to the modelled information domain. Rule-based approach gives very good diagnostics but it is more complicated to express simple parent-child relationships as in grammar-based languages. An interesting way how to gain advantages of both approaches is to support conversion from grammar-based schemes into rule-based schemes.

---

Table of Contents

Introduction

Validation with Grammar

Grammar-based XML Validation

Hedge

Regular Hedge Grammar

Automata-based Validation

Grammar and Diagnostics

Using Rules

Schematron

Expressiveness

From Grammar to Rules

Conclusions

Bibliography

Introduction

Regular grammar is a formal grammar which is defined by a set of terminal symbols, a set of non-terminals, and a set of production rules.
Production rules need to have the following form.

Regular grammar production rules

1. 
   X →x; where X is a non-terminal and x is a terminal symbol
   
2. 
   X →xY; where X and Y is a non-terminal and x is a terminal symbol.
   
3. 
   X →ε; where X is a non-terminal and ε is an empty word.
   

The previous is also known as right regular grammar. For a left regular grammar the second production rule takes the form of X →Yx.
Regular grammar describes all regular languages. They are in a sense equivalent to the finite state automaton. Form every regular grammar a FSA may be constructed. For each regular language a FSA can be constructed which accepts all words from this language but rejects all other words. A FSA is an algorithmic approach how to decide whether a particular language is generated by a particular regular grammar.
Regular languages may also be described by regular expressions. This task is information common practice in information technologies. There is an algorithmic way to create a FSA from a regular expression and thus a way how to automatically decide whether a word belongs into a regular language or not.

Validation with Grammar

Regular language theory is often used for validation of whether a string (a program or a document) matches a regular grammar. This is a typical task which is done during compilation of a computer program where the compiler checks whether the program has correct syntax and can be compiled. Another example is validation of an XML document against a schema. An XML schema may be converted into a regular grammar and then decided whether a document is generated by that particular grammar or not.
Keeping validation algorithm regular grammar-based is convenient in terms of computational complexity. For example regular expressions may be evaluated in a linear time by converting them into deterministic finite state automaton (DFSA). For any input word N of length n and a regular expression R of the lengthm; N may be matched against R in the time O(n+2^m) .

Grammar-based XML Validation

One of the concepts for XML document validation based on regular grammars is regular hedge grammar. In general, hedge is a sequence of trees. In the XML terminology, we would call them elements. Basically an XML document is an example of a hedge.

Hedge

Hedge over a finite set of symbols S and variables V is either:

• 
  an null hedge (ε),
  
• 
  a variable fromV,
  
• 
  s<h> where s is a symbol from S and h is again a hedge,
  
• 
  or a concatenation of two hedges i.j.
  

This text uses same hedge notation as used by Murata Makoto in [HEDGE].

Figure 1. Example hedge notation

a<b c<f g<χ>> d<ψ> e>

Alternatively we can depict hedges also using diagrams. The same hedge again in a different notation.

Note that symbols occur in hedges only in non-leaf nodes and variables in leafs.

Any XML document can simply be converted into the hedge notation. Tags are represented through symbols and their textual content as variables (In this case we abstract from XML attributes). Such conversion is demonstrated within the next example.

Figure 2. XML document as a hedge

Here is an simple HTML document.

<html>
  <head>
    <title>Example</title>
  </head>
  <body>
    <p>Foo</p>
  </body>
</html>

The following hedge is equivalent to the previous document.

html<head<title<'Example'> body<p<'Foo'>>

In this case the set of symbols S = { html, head, title, body, p } and V = { 'Foo', 'Example' }

Regular Hedge Grammar

Now it is the right time to introduce the Regular Hedge Grammar (RHG) which is a mechanism for generation of different hedges. For a grammar there is an algorithmic way how to decide whether a particular word belongs to a language generated by that grammar.
This process in called validation in the XML terminology and any particular RHG which generates a set of hedges may be understood as a schema which defines all valid XML documents.
Validation of an XML document against a schema is a task of converting a RHG into a hedge automaton and try whether it accepts the input document or not.
Formal definition of RHG is very similar to the regular grammar definition described in the section called “Introduction”.
Regular hedge grammar is a formal grammar which is defined in [HEDGE] as a finite set of terminal symbols S, a finite set of non-terminals N, a finite set of variables V a set of production rules P and r which is a regular expression composed of non-terminals.

RHG production rules

Production rules in P are only of the following form.

1. 
   n →v; where n is a non-terminal and v is a variable. Applying this production rules means a non-terminal is replaced by a variable.
   
2. 
   n →s<r>; where n is a non-terminal, s is a symbol and r is a regular expression composed of non-terminal symbols. If this production rule gets applied a non-terminal is replaced by a terminal symbol which contains a sequence of non-terminals matching the regular expression r.
   

The language generated by the RHG is a set of hedges generated by applying the production rules to a set non-terminals which match the regular expression r.
The use of RHGs as a schema can be demonstrated on a simple example. Imagine, we like to define an simplification of the HTML language, where the root element is html which must contain one head and one body element in a sequence. Further, there is one title element in head and an unlimited amount of p or img in the body in any order.

Figure 3. Schema in RHG

The verbal definition may be expressed formally in DTD as follows.

<!ELEMENT  html (head, body)>
<!ELEMENT  body (p|img)*>
<!ELEMENT  head  (title)>
<!ELEMENT  title   (#PCDATA)>
<!ELEMENT  p   (#PCDATA)>
<!ELEMENT  img  EMPTY>

The same definition in the RHG notation.

S = {html, head, body, title, p, img }
V = { "#PCDATA" }
N = { N(html), N(head), N(body), N(title), N(p), N(img), N(pcdata) }
P = { N(html)  →  html<N(head), N(body)>
      N(head)  →  head<N(title)>
      N(body)  →  body<(N(p) | N(img))*>
      N(title) →  title<N(pcdata)>
      N(p)     →  p<N(pcdata)>
      N(img)   →  img<ε>
      N(pcdata)→  #PCDATA }

Automata-based Validation

The validation task for a particular schema (RHG) and a particular XML document (input word) is equivalent to a task to construct a Deterministic Hedge Automaton (DHA) and find out whether it accepts the input.
DHA is a finite state automaton (FSA) and as such it is defined with a finite set of symbols, states and transitional function which transit the automaton from one state to another, depending on the input symbol.
DHA have just few slight modifications; there are two transition functions, one for symbols ( Fs) and other for variables (Fv) and the result of Fs depends not only on the current state and the input symbol, but it depends on a set of states which are the target states for the child symbols or values in the hedge.

Here is the formal definition of a DHA taken from [HEDGE]. DHA is a sextuple (S, V, Q, F, Fs, Fv), where:

1. 
   S is a finite set of symbols,
   
2. 
   V is a finite set of values,
   
3. 
   Q is a finite set of states,
   
4. 
   F is a set of terminal states, a regular set over Q,
   
5. 
   Fs is a function from S × Q* → Q such that for every q in Q and s in S, {q1 q2 ... qk | k >= 0, α(x, q1 q2 ... qk ) = q } is a regular set,
   
6. 
   Fv is a function from V → Q
   

Figure 4. Example of the DHA process

Here is the very same HTML document which we created grammar for in Figure 3, “Schema in RHG”.

<html>
  <head><title>Test</title></head>
  <body>
    <img/>
  </body>
</html>

And this is how a DHA evaluates the transition functions.

Fs(html, Fs(head, Fs(title,Fv('Test')))Fs(body, Fs(img, ε)))

Fs(head, Fs(title,Fv('Test')))Fs(body, Fs(img, ε)) → Fs(head, Fs(title,Fv('Test')))
Fs(head, Fs(title,Fv('Test')))Fs(body, Fs(img, ε)) → Fs(body, Fs(img, ε))

Fs(head, Fs(title,Fv('Test'))) → Fs(title,Fv('Test'))

Fs(body, Fs(img, ε)) → Fs(img, ε)

Fs(title,Fv('Test')) → Fv('Test')

Fs(img, ε) → ε

Note that validation using RHG is used withing one of the current mainstream validation languages Relax NG, see [RNG].
The Fs function which accepts multiple states as parameters makes it difficult to depict a finite hedge automaton in a diagram, thus in the later text we will use a classical finite state automaton to demonstrate regular grammar-based XML validation process. The expressive power is the same and we may depict such automata more easily and make the diagrams more understandable.

Figure 5. XML Validating FSA

In the diagram you can see a FSA which validates XML documents against the schema described in Figure 3, “Schema in RHG”. For any symbol which has no explicit transition in the diagram the target state is ERROR. ERROR is not part of the final state set and thus any input document which leads the DHA to ERROR is considered to be invalid. Only FIN belongs to F; the set of terminal states.

Note, there are tree different arrows pointing from the B1 state, because body may contain p | img | ε.
The final state for an invalid document doesn't need to be ERROR. For example a document which would be missing the html end tag but otherwise it is correct will finish in the B3 state and thus the automaton won't accept it.
Using FSA we can express many common restrictions within XML trees, thus it is a suitable model for us at this stage. For example a sequence of head and body elements which has a strict order is expressed with the transition from H5 → H6 → B1.
In case we like to express an arbitrary order of child elements withing a parent we can use multiple transitions from one state as demonstrated in the B1 state pointing to P1 and I1.

Grammar and Diagnostics

Regular grammar-based validation is fast and straight forward, but does it really give suitable validation outputs? Experiences from the SGML/XML world shows that not always. With grammars it is easy to find out that something is wrong in the document, but it is more difficult to explain where exactly the problem occurred and extremely difficult to guide the author to resolve the issue or to explain the issue in a human understandable form.
One sort of problems with diagnostics can be explained with a example grammar for a simple Member of Parliament evidence. MPs are identified by name which is required and also each MP must have one assistant. The only exception is the Speaker of the Parliament who has two assistants. The door number of the MPs office is optional.

Figure 6. Schema for MPs evidence

<!ELEMENT  MP (name, (speaker, assistant)?, assistant, office?)
<!ELEMENT  office    (#PCDATA)>
<!ELEMENT  assistant (#PCDATA)>
<!ELEMENT  speaker  EMPTY>

Next we construct a FSA automaton to validate such grammar. Such automaton is depicted in the next diagram.

Figure 7. Validator for the MPs evidence grammar

Next consider several example of instances, their validation flow and the validation results.

Instances and validation

Nr	Document	Flow	Error	Explanation	Result
1	<MP> <name>Miloslav Vlcek</name> <speaker/> <assistant>Petr Mazalek</assistant> <assistant>Veronika Soumanova</assistant> <office>56</office> </MP>	START ↓ Q1 ↓ Q2 ↓ Q3 ↓ Q7 ↓ Q4 ↓ Q4 ↓ Q5 ↓ Q6 ↓ Q4 ↓ FIN			VALID
2	<MP> <name>Petr Bradsky</name> <assistant>Jaroslava Pokorna</assistant> <office>121</office> </MP>	START ↓ Q1 ↓ Q2 ↓ Q4 ↓ Q5 ↓ Q6 ↓ Q4 ↓ FIN			VALID
3	<MP> <name>Petr Bradsky</name> <assistant>Jaroslava Pokorna</assistant> </MP>	START ↓ Q1 ↓ Q2 ↓ Q4 ↓ FIN			VALID
4	<MP> <name>Miloslav Vlcek</name> <speaker/> <assistant>Petr Mazalek</assistant> </MP>	START ↓ Q1 ↓ Q2 ↓ Q3 ↓ Q7 ↓ ERROR	Expected <assistant> but was </MP>	In Q4, to transit to FIN the only non-error input could have been </MP> or <office>	INVALID
5	<MP> <name>Miloslav Vlcek</name> <assistant>Petr Mazalek</assistant> <assistant>Veronika Soumanova</assistant> </MP>	START ↓ Q1 ↓ Q2 ↓ Q4 ↓ ERROR	Expected </MP> or <office> but was <assistant>	In Q4, to transit to FIN the only non-error input could have been </MP> or <office>	INVALID

In the table above, the diagnostics for instance number 4 is appropriate. The validation engine expected a assistant tag but in the instance the MP tag has already been closed. The fix is quite obvious and clearly explained in the diagnostics. The author shall provide a second sibling assistant element.
A real problem occurs in the instance number 5 validation example. In this case somebody did obviously forgotten to mark the MP as the Speaker of the Parliament as nobody else may have two assistants assigned. The regular grammar-based diagnostics does not help to resolve such issue.
The location of the error is the second assistant element, but in reality the error is the missing speaker element after name. The error message claims we have a redundant assistant element, but in this case we are talking about the Speaker's document and we just forgot to add the speaker element indicator. In this case the validation result gives us no clue how to resolve the issue, as it does not mention the missing speaker element at all.
Moreover, the validation result guides us to delete the second assistant element which is completely wrong and in addition we would loose important information in order to make the document pass the validation.
There are many more examples where regular grammar-based validation diagnostics leads to misleading error messages, but this is not the only problem. As grammar-based validation is completely unaware of the semantics of the validated language there is no way how to attach reasonable domain specific diagnostics which would help the authors resolve issues more easily.

Quality of diagnostics

Compare the following two validation diagnostics

1. 
   “Expected MP end tag or office but was assistant”.
   
2. 
   “Missing speaker element. 'Miloslav Vlcek' has 2 assistants defined but he is not marked as the Speaker of the Parliament using the speaker tag. Only the Speaker is entitled to have two assistants, regular members may have only one. Either add the speaker element as the first child of the MP element or remove one of the assistants.”.
   

It is obvious that the second error massage gives a reasonable resolution to the user but the first message is completely useless, misleading and wrongly positioned. In the rest of the text we will learn possible approaches to get to the quality of diagnostics demonstrated in the second sentence in Quality of diagnostics.

Using Rules

Fortunately grammar-based validation is not the only validation approach which exists today. Rule-based validation languages are becoming more and more popular.
In principle, rule-based validation matches an input document against a set of patterns which are called rules. The result of such matching is a set of assertions and diagnostics. [RJ] stresses the distinction between the assertion text, which is a positive statement of what should be true in the document, and the diagnostics, which contains specific messages for describing, locating and correcting the problem.
To illustrate the difference, in Quality of diagnostics the Missing speaker element. message is the assertion and the rest of the message is diagnostics.
The rule-based approach is quite double-edged. At one side, when designing the schema we have a more low level control over the validation process and that is the reason we are able to attach domain specific diagnostics, but on the other hand, some definitions which are implicitly expressed by declaring an element in a grammar-based language need to be expressed in the rule-based approach explicitly, sometimes with more rules.
This is definitely error-prone, because forgetting one of the rules means we have an incomplete schema and there is no easy way how to detect it.
Another problem of the rule-based approach is performance. Where grammar-based validation can be performed in a linear time, in rule-based validation the execution time depends on the expressions we use within our rule assertions. We can easily get into the world of context-sensitive tasks and in case, performance is a important factor in a certain application, it is necessary to judge each individual rule in terms of performance. In contrast, schema designers who are using the regular grammar-based approach are free of expression. They may use any language constructs they like and keep their validation tasks in linear time.
Even there are downsides of the rule-based approach, it is worth studying it. Grammar-based validation did already reach its limits in terms of diagnostics and there are many real life validation problems were diagnostics is far more important than performance. For example validation of complex XML languages with hundreds of pages of specification like for example HTML, SVG, DocBook and others. In this case authors validate relatively small documents, but correct diagnostics is very important for them as they did not read the whole specification.
Moreover, there is a huge area of possibilities for future performance optimisation for rule-based languages. In the time when they are used as long as grammar based languages are used now, I sure there will be effective optimisation techniques which will minimize the performance handicap.

Schematron

To demonstrate the rule-based approach on a few examples, in this section we will have closer look into Schematron; the major standardized rule-based validation language.
Schematron is a simple XML-based schema language composed just of a few elements and attribute. There are only six main elements in Schematron which makes it very easy to learn. In this short introduction to Schematron we will mention just the six most important elements and their semantics which will allow us to understand how are rules being constructed.

Four most important Schematron elements

schema

the root container for patterns.

pattern

a named container for a set of rules

rule

a particular rule with a defined context within the validated document. Rules contain mixed assert and report elements.

assert

Assertion contains a statement about the document in a formal language which may be automatically evaluated against the document from within the rules context. In case the assertion is not satisfied, an attached plain text explanation of the problem is displayed to the end-user.

report

Report is equivalent to assertion, but the attached plain text is invoked in case the report's test expression is evaluated as TRUE (opposite to the assertion).

value-of

This element allows to enrich the diagnostics with values from withing the current rule context of the document to enhance the diagnostics with additional guidance for the author to resolve the reported issue.

Although Schematron uses XPath as the preferred formal language to evaluate assertions and reports against XML document, it is possible to use also other languages able to address nodes and values within the XML DOM tree; for example JavaScript is a good candidate.

Figure 8. Schematron rule example

Now we can return to our MP evidence problem and try to reach the level of diagnostics shown in the second message in Quality of diagnostics.

<sch:pattern name="MP Evidence">
    <sch:rule context="MP">
        <sch:assert report="count(assistant) > 0 and not(speaker)">
                Missing speaker element.
                '<sch:value-of select="name"/>' has <sch:value-of select="count(assistant)"/> assistant(s) defined but he is not marked as the Speaker of the Parliament using the speaker tag. Only the Speaker is entitled to have two assistants, regular members may have only one. Either add the speaker element as the first child of the MP element or remove one of the assistants.
        </sch:assert>
    </sch:rule>
</sch:pattern>

Note that in Schematron there is a way how to logically split assertion texts and diagnostics. To simplify the example, those two distinct parts of the error message has been put together as the report text.
In terms of performance optimisation, Schematron features the phases construct. Patterns may be organized into phases and during validation only a certain phase may be evaluated. Just in case there are no errors the next phase gets processed.

Expressiveness

It is difficult to say which approach (rules or grammar) is more expressive. The set of documents able to be described by a rule-based approach (Schematron) and a regular grammar-based approach are two distinct sets with a significant intersection. But there are documents which may be described with one approach but cannot be described with the other.
On the other hand there are many real life use-cases where Schematron can be used to model some restrictions which are really useful but they can't be expressed using regular grammar-based validation. This is caused by the fact that Schematron can operate with multiple contexts across the documents where grammar-based languages usually model just simple parent-child relationships withing the context of the current parent element. With Schematron we may for example condition the occurrence of an element by the values of an attribute in a completely different branch of the document. This is very powerful and has many real life use-cases. For example, using Schematron I was able to formalize additional restrictions expressed in the HTML specification only verbally; thus improving validation results and diagnostics for HTML document validation, see [PN1].

Figure 9. Schematron rule not expressible using a regular grammar-based approach

This example was taken from [PN1] and is based in my Schematron schema for W3C WCAG 1.0 specification.

<sch:rule context="html:abbr">
  <sch:report test="not(@title) and not(preceding::html:abbr[. = string(current())][@title])">
   WCAG 1.0 Checkpoint 4.2 (Priority 3) First occurrence of abbreviation in a document needs to have an title defined.
  </sch:report>
</sch:rule>

When thinking about suitability of grammar or rules for different validation tasks, we can easily come to a conclusion that a mixture of both approaches would bring the best of both worlds. This is the approach proposed in [PN1]. Such approach encourages to use a grammar-based language to enumerate elements and attributes and define their content model easily and to use rules to define advanced multi-context assertions with enhanced diagnostics. This approach was used to model extended HTML schemas in [PN1].

From Grammar to Rules

Another approach to combine rules and grammar is a to convert grammar-based schemas to Schematron rules. Such conversion may slightly enhance diagnostics by keeping simplicity of expression. Also such generated schemas become really platform/programming language independent as we don't need any validation engine for our specific schema language, but validation becomes a simple XSLT transformation and today an XSLT processor is present in vast majority of environments (even a web browser can be used as an XSLT processor).
Converting grammar to rules makes also integration of grammar-based language with Schematron easy as the generated rules may be simply merged with some additional rules defined.
There are clearly advantages to convert grammar-based schemas to rules, but how to achieve that? As we stated, those two approaches are not equally expressive, we already know that this conversion cannot be exhaustive. But in real life this may not be a big problem, because most of the reasonable constructs defined in regular grammar-based schema languages can be expressed using rules. But there is no simple algorithmic way how to convert a FSA into a set of XPath rules. So the task here is to go through different constructs of a particular grammar-based language and invent templates to convert them into Schematron patterns.

Figure 10. Grammar validation using pure rules

The following diagram show the validation process including conversion. A grammar-based schema is first converted to rules, rules are merged with other restrictions already defined using rules, rules are grouped into phases to optimise performance and enhance diagnostics. Finally, an input document is validated against the generated and merged rules.
The conversion as well as the validation process may be nothing else than a standard XSLT transformation.

The most tricky part of the diagram above is of course conversion to Schematron. There is currently no such converter and implementation of such conversion is under research. In the simplest case, [RJ] mentions a straightforward way how to get grammars into XSLT using the XSLT 2 build-in regular expression engine. With regular expressions we can express cardinality, sequence, choice and other constructs common in grammar-based schemas. The advantage is, with such conversion we can do validation tasks using a standard XSLT 2 transformer, but on the other hand, there is no improvement in diagnostics. Again we are just doing a regular grammar-based validation with a FSA.
Another approach is to break individual grammar-based restrictions into different kind or rule types. For example the grammar-based schema enumerates all allowed element and attributes. This may be converted into Schematron rule which checks that for every element and attribute in the input document the element or attribute names belong into a set of allowed names, otherwise an unknown element error is reported.
Also it is easy to extract content models for each element (what different children it is allowed to contain) and for each element create a rule that checks that all children belong to a particular set of allowed child elements for that particular parent.
Having such rules does not really bring domain related explanations, but on the other hand, grammar-based validators are usually not able to show all violated rules in a sub-tree as they already die on the first error occurrence as they move to a ERROR state and there is no way out. In contrast Schematron rules will show all diagnostics of all violated assertions in one validation run which is a diagnostic improvement. Also it is possible to group certain type of checks into phases and systematically point our validation effort at some sort of issues.
As result, we can have phases for validation of mistakes in element or attribute names, for broken content models, for required elements or attribute if whether they are present and for all sort of different groups of problems.
Moreover, one part of our rule-based schema may be auto-generated from a grammar schema, not forcing us doing a lot of implicit rules manually, but another part of the rules may be defined explicitly with domain specific diagnostics. Another big challenge of the converting method is to find effective ways how to merge the generated implicit rules with the explicit one and thus enriching the validation results with highly specific and domain related diagnostics.

Conclusions

This article explains principles of XML document validation. Regular grammar-based validation is explained in detail using examples and diagrams. One of the examples demonstrates limits of regular grammar-based validation diagnostics.
The aim of this article is to show that despite its efficiency, regular grammar-based validation diagnostics is inappropriate for some applications. Error messages may be located wrongly and their explanation may be confusing for the XML document author.
One of the options to overcome such limitations is to use rule-based systems instead. Rule-based languages are more expressive for some sort of restrictions and they have much better diagnostics as they allow to control the error message form by the schema author. On the other hand it is more difficult to model some sort of simple relationships and a big issue is optimization. It is difficult to judge the computing price of different rules. But although there are drawbacks it is necessary to investigate new ways in validation because classical grammar-based approach did reach its limit already long time ago in terms of diagnostics and currently it is insufficient for some sort of tasks.
Very promising seems a hybrid approach exploiting the best of grammars and the best of rules in one validation process. Rules may be directly embedded into grammar-based schemas.
Another way is to get simplicity of expression using the grammar approach but enhance diagnostics through converting grammar definitions to rules before validation.
All approaches have their pros and cons and they are more or less suitable for different purposes. But the lack of good diagnostics in grammar-based validation is an outstanding issue which needs to be coped with. That's why exploring novel ways in XML document validation is important.

Bibliography

[HEDGE] Murata, M.:Hedge automata: a formal model for XML schemata. Fuji Xerox Information Systems. 2000. Available at: http://www.xml.gr.jp/relax/hedge_nice.html

[PN1] Kosek, J., Nálevka, P.: Relaxed — on the Way Towards True Validation of Compound Documents. WWW2006, Edinburg, 2006. Available at: http://www2006.org/programme/files/pdf/4508.pdf

[PN2] Nálevka, P.: Doplňková validate HTML a XHTML dokumentů. University of Economics, Prague, 2003. Available at: http://nalevka.com/resources/thesis.pdf

[PN3] Nálevka, P., Kosek, J.: Advanced approaches to XML document validation. Extreme Mark-up Languages Conference, Montreal, 2007. Available at: http://www.idealliance.org/papers/extreme/proceedings/xslfo-pdf/2007/Nalevka01/EML2007Nalevka01.pdf

[RNG] Clark, J., Murata, M.: RELAX NG Specification. OASIS Committee Specification, 2001. Available at: http://www.relaxng.org/spec-20011203.html

[SCH] Jelliffe, R.: The Schematron Assertion Language 1.5. Academia Sinica Computing Centre, 2002. Available at: http://xml.ascc.net/resource/schematron/Schematron2000.html

[RJ] Jelliffe, R.: Converting XML Schemas to Schematron. O'Reilly XML Blog, 2007. Available at: http://www.oreillynet.com/xml/blog/2007/09/converting_xml_schemas_to_sche.html

[MI] Ivánek, J.: Základy matematické informatiky I: Informace a automaty. Státní pedagogické nakladatelství, 1991, Praha, ISBN: 80-7079-673-1.