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 | 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: | http://hdl.handle.net/1942/651 | Link to publication/dataset: | http://doi.acm.org/10.1145/601858.601869 | 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 | Size | Format | |
---|---|---|---|---|
neven02automata.pdf | 128.42 kB | Adobe PDF | View/Open |
Google ScholarTM
Check
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.