Please use this identifier to cite or link to this item:
Title: Automata Theory for XML Researchers.
Authors: NEVEN, Frank 
Issue Date: 2002
Publisher: AMC
Source: 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.
Document URI:
Link to publication:
ISSN: 0163-5808
e-ISSN: 1943-5835
ISI #: 000178732700004
Category: A1
Type: Journal Contribution
Appears in Collections:Research publications

Files in This Item:
File Description SizeFormat 
neven02automata.pdf128.42 kBAdobe PDFView/Open
Show full item record


checked on May 14, 2022

Page view(s)

checked on May 20, 2022


checked on May 20, 2022

Google ScholarTM


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