Automata Theory for XML Researchers.

Abstract

The advent of XML initiated a symbiosis between document research, databases and formal languages. This symbiosis resulted, for instance, in the development of un- ranked tree automata. In brief, unranked trees are _nite labeled trees where nodes can have an arbitrary number of children. So, there is no _xed rank associated to each label. As the structure of XML documents can be adequately represented by unranked trees, unranked tree automata can serve XML research in four di_erent ways: (i ) as a basis of schema languages and validating of schemas; (ii ) as an evaluation mechanism for pattern languages; (iii ) as an algorithmic toolbox (e.g., XPath containment and typechecking); and (iv ) as a new paradigm: unranked tree automata use regular string languages to deal with unrankedness. The latter simple but e_ective paradigm found application in several formalisms. The present paper is an attempt to provide a gentle introduction to unranked tree automata and to give references to some applications. We mention that Vardi, already in 1989, wrote a paper demonstrating the usefulness of ranked tree automata for the static analysis of datalog programs.