Hedge automata: a formal model for XML schemata

MURATA Makoto (FAMILY Given) Fuji Xerox Information Systems Introduction This note shows preliminaries of the hedge automaton theory. In the XML community, this theory has been recently recognized as a simple but powerful model for XML schemata. In particular, the design of RELAX (REgular LAnguage for XML) is directly based on this theory. Hedges First, we introduce hedges. Informally, a hedge is