Document Server@UHasselt >
Research >
Research publications >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/651

Title: Automata Theory for XML Researchers.
Authors: NEVEN, Frank
Issue Date: 2002
Publisher: AMC
Citation: SIGMOD Record, 31(3). p. 39-46
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.
URI: http://hdl.handle.net/1942/651
Link to publication: http://doi.acm.org/10.1145/601858.601869
ISI #: 000178732700004
ISSN: 0163-5808
Category: A1
Type: Journal Contribution
Appears in Collections: Research publications

Files in This Item:

Description SizeFormat
N/A128.42 kBAdobe PDF

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.