Abstract
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.

URL:
http://rewerse.net/publications/rewerse-publications.html#REWERSE-TR-2007-01

BibTeX:

@techreport{REWERSE-TR-2007-01,
	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 = {http://rewerse.net/publications/rewerse-publications.html#REWERSE-TR-2007-01}
}