Sacha Berger:
An Automaton Model for Xcerpt Type Checking and XML Schema Validation.

Complete Text [
.pdf, 0.51MB]

An automaton model used for validation and type checking with languages defined using R2G2 is presented. First, tree-shaped data is considered to be handled by the automaton model, then the approach is extended to graph shaped data. The presented approach is based on specialized non-deterministic finite state automata. The specialisation copes with unranked tree shaped data. Graph shaped data will be treated as, possibly infinite in depth, trees. The choice of using non-deterministic automata is motivated by complexity issues: as the tree automata are based on regular expressions, non-deterministic automata are a necessary intermediate step. Arguably deterministic tree automata are more efficient on validating data, but the derivation of such automata from non-deterministic ones comes with potentially exponential costs. As all the needed algorithms can be achieved on non-deterministic automata in sub-exponential time and space complexity, no need for determinisation arises.



	author = {Sacha Berger},
	title = {An Automaton Model for Xcerpt Type Checking and XML Schema Validation},
	institution = {Institute for Informatics, University of Munich},
	year = {2007},
	type = {{research report, REWERSE-TR-2007-01}},
	number = {REWERSE-TR-2007-01},
	url = {}