1 Introduction Automata for XML — A Survey
---
paper_title: Typechecking for XML transformers

paper_content:

We study the typechecking problem for XML (eXtensible Markup Language) transformers: given an XML transformation program and a DTD for the input XML documents, check whether every result of the program conforms to a specified output DTD. We model XML transformers using a novel device called a k-pebble transducer, that can express most queries without data-value joins in XML-QL, XSLT, and other XML query languages. Types are modeled by regular tree languages, a robust extension of DTDs. The main result of the paper is that typechecking for k-pebble transducers is decidable. Consequently, typechecking can be performed for a broad range of XML transformation languages, including XML-QL and a fragment of XSLT.
---
paper_title: Typing and querying XML documents: some complexity bounds

paper_content:

We study the complexity bound of validating XML documents, viewed as labeled unranked ordered trees, against various typing systems like DTDs, XML schemas, tree automata ... We also consider query evaluation complexities for various fragments of XPath. For both problems, validation and query evaluation, we consider data and combined complexity bounds.
---
paper_title: On Recognizable Sets and Tree Automata

paper_content:

Publisher Summary This chapter discusses a few aspects of recognizability in general algebraic structures It presents the comparison of the two usual meanings of the term recognizable. The first one is algebraic and the second one is algorithmic. There is in addition a third use of the term recognizable in theories of sets of infinite words and of sets of infinite trees. This use corresponds to an extension of the algorithmic sense of recognizability: A word is accepted by an automaton if there exists an infinite computation of the automaton satisfying certain conditions concerning the states occurring infinitely many times. This notion of acceptance is not effective as it concerns infinite objects. It is not algebraic either as the corresponding sets of infinite trees or words are not recognizable with respect to any algebraic structure.
---
paper_title: Querying unranked trees with stepwise tree automata

paper_content:

The problem of selecting nodes in unranked trees is the most basic querying problem for XML. We propose stepwise tree automata for querying unranked trees. Stepwise tree automata can express the same monadic queries as monadic Datalog and monadic second-order logic. We prove this result by reduction to the ranked case, via a new systematic correspondence that relates unranked and ranked queries.
---
paper_title: Typechecking for XML transformers

paper_content:

We study the typechecking problem for XML (eXtensible Markup Language) transformers: given an XML transformation program and a DTD for the input XML documents, check whether every result of the program conforms to a specified output DTD. We model XML transformers using a novel device called a k-pebble transducer, that can express most queries without data-value joins in XML-QL, XSLT, and other XML query languages. Types are modeled by regular tree languages, a robust extension of DTDs. The main result of the paper is that typechecking for k-pebble transducers is decidable. Consequently, typechecking can be performed for a broad range of XML transformation languages, including XML-QL and a fragment of XSLT.
---
paper_title: Querying unranked trees with stepwise tree automata

paper_content:

The problem of selecting nodes in unranked trees is the most basic querying problem for XML. We propose stepwise tree automata for querying unranked trees. Stepwise tree automata can express the same monadic queries as monadic Datalog and monadic second-order logic. We prove this result by reduction to the ranked case, via a new systematic correspondence that relates unranked and ranked queries.
---
paper_title: Typechecking for Semistructured Data

paper_content:

Semistructured data is used in data exchange applications, like B2B and EAI, and represents data in a flexible format. Every data item has a unique tag (also called label), and data items can be nested. Formally, a semistructured data instance is a tree whose nodes are labeled with tags and leaves are labeled with data values. XML [Con98] is a standard syntax for describing such trees; Fig. 1 shows a tree representing a semistructured data instance and its XML syntax. We will refer interchangeably to semistructured data instances as trees or XML trees.
---
paper_title: Visibly pushdown languages

paper_content:

We propose the class of visibly pushdown languages as embeddings of context-free languages that is rich enough to model program analysis questions and yet is tractable and robust like the class of regular languages. In our definition, the input symbol determines when the pushdown automaton can push or pop, and thus the stack depth at every position. We show that the resulting class V pl of languages is closed under union, intersection, complementation, renaming, concatenation, and Kleene-*, and problems such as inclusion that are undecidable for context-free languages are E xptime -complete for visibly pushdown automata. Our framework explains, unifies, and generalizes many of the decision procedures in the program analysis literature, and allows algorithmic verification of recursive programs with respect to many context-free properties including access control properties via stack inspection and correctness of procedures with respect to pre and post conditions. We demonstrate that the class V pl is robust by giving two alternative characterizations: a logical characterization using the monadic second order (MSO) theory over words augmented with a binary matching predicate, and a correspondence to regular tree languages. We also consider visibly pushdown languages of infinite words and show that the closure properties, MSO-characterization and the characterization in terms of regular trees carry over. The main difference with respect to the case of finite words turns out to be determinizability: nondeterministic Buchi visibly pushdown automata are strictly more expressive than deterministic Muller visibly pushdown automata.
---
paper_title: Deterministic Automata on Unranked Trees

paper_content:

We investigate bottom-up and top-down deterministic automata on unranked trees. We show that for an appropriate definition of bottom-up deterministic automata it is possible to minimize the number of states efficiently and to obtain a unique canonical representative of the accepted tree language. For top-down deterministic automata it is well known that they are less expressive than the non-deterministic ones. By generalizing a corresponding proof from the theory of ranked tree automata we show that it is decidable whether a given regular language of unranked trees can be recognized by a top-down deterministic automaton. The standard deterministic top-down model is slightly weaker than the model we use, where at each node the automaton can scan the sequence of the labels of its successors before deciding its next move.
---
paper_title: Minimizing tree automata for unranked trees

paper_content:

Automata for unranked trees form a foundation for XML schemas, querying and pattern languages. We study the problem of efficiently minimizing such automata. We start with the unranked tree automata (UTAs) that are standard in database theory, assuming bottom-up determinism and that horizontal recursion is represented by deterministic finite automata. We show that minimal UTAs in that class are not unique and that minimization is np-hard. We then study more recent automata classes that do allow for polynomial time minimization. Among those, we show that bottom-up deterministic stepwise tree automata yield the most succinct representations.
---
paper_title: Tree acceptors and some of their applications

paper_content:

This paper concerns a generalization of finite automata, the ''tree acceptors,'' which have as their inputs finite trees of symbols rather than the usual sequences of symbols. Ordinary finite automata prove to be special cases of tree acceptors, and many of the results of finite automata theory continue to hold in their appropriately generalized forms. The tree acceptors provide new characterizations of the classes of regular sets and of context-free languages. The theory of tree acceptors is applied to a decision problem of mathematical logic. It is shown here that the weak secondorder theory of two successors is decidable, thus settling a problem of Buchi. This result is in turn applied to obtain positive solutions to the decision problems for various other theories, e.g., the weak second-order theories of order types built up from the finite types, @w, and @h (the type of the rationals) by finitely many applications of the operations of order type addition, multiplication, and converse; and the weak second-order theory of locally free algebras with only unary operations.
---
paper_title: Monadic datalog and the expressive power of languages for Web information extraction

paper_content:

Research on information extraction from Web pages (wrapping) has seen much activity in recent times (particularly systems implementations), but little work has been done on formally studying the expressiveness of the formalisms proposed or on the theoretical foundations of wrapping.In this paper, we first study monadic datalog as a wrapping language (over ranked or unranked tree structures). Using previous work by Neven and Schwentick, we show that this simple language is equivalent to full monadic second order logic (MSO) in its ability to specify wrappers. We believe that MSO has the right expressiveness required for Web information extraction and thus propose MSO as a yardstick for evaluating and comparing wrappers.Using the above result, we study the kernel fragment Elog- of the Elog wrapping language used in the Lixto system (a visual wrapper generator). The striking fact here is that Elog- exactly captures MSO, yet is easier to use. Indeed, programs in this language can be entirely visually specified. We also formally compare Elog to other wrapping languages proposed in the literature.
---
paper_title: Generalized finite automata theory with an application to a decision problem of second-order logic

paper_content:

Many of the important concepts and results of conventional finite automata theory are developed for a generalization in which finite algebras take the place of finite automata. The standard closure theorems are proved for the class of sets “recognizable” by finite algebras, and a generalization of Kleene's regularity theory is presented. The theorems of the generalized theory are then applied to obtain a positive solution to a decision problem of second-order logic.
---
paper_title: On the power of tree-walking automata

paper_content:

Tree-walking automata (TWAs) recently received new attention in the fields of formal languages and databases. To achieve a better understanding of their expressiveness, we characterize them in terms of transitive closure logic formulas in normal form. It is conjectured by Engelfriet and Hoogeboom that TWAs cannot define all regular tree languages, or equivalently, all of monadic second-order logic. We prove this conjecture for a restricted, but powerful, class of TWAs. In particular, we show that 1-bounded TWAs, that is TWAs that are only allowed to traverse every edge of the input tree at most once in every direction, cannot define all regular languages. We then extend this result to a class of TWAs that can simulate first-order logic (FO) and is capable of expressing properties not definable in FO extended with regular path expressions; the latter logic being a valid abstraction of current query languages for XML and semistructured data.
---
paper_title: Translations on a context free grammar

paper_content:

Two schemes for the specification of translations on a context-free grammar are proposed. The first scheme, called a generalized syntax directed translation (GSDT), consists of a context free grammar with a set of semantic rules associated with each production of the grammar. In a GSDT an input word is parsed according to the underlying context free grammar, and at each node of the tree, a finite number of translation strings are computed in terms of the translation strings defined at the descendants of that node. The functional relationship between the length of input and length of output for translations defined by GSDT's is investigated. The second method for the specification of translations is in terms of tree automata - finite automata with output, operating on derivation trees of a context free grammar. It is shown that tree automata provide an exact characterization for those GSDT's with a linear relationship between input and output length.
---
paper_title: Tree Transducers, L Systems, and Two-Way Machines

paper_content:

A relationship between parallel rewriting systems and two-way machines is investigated. Restrictions on the “copying power” of these devices endow them with rich structuring and give insight into the issues of determinism, parallelism, and copying. Among the parallel rewriting systems considered are the top-down tree transducer; the generalized syntax-directed translation scheme and the ETOL system, and among the two-way machines are the tree-walking automaton, the two-way finite-state transducer, and (generalizations of) the one-way checking stack automaton. The. relationship of these devices to macro grammars is also considered. An effort is made .to provide a systematic survey of a number of existing results.
---
paper_title: Parallel and two-way automata on directed ordered acyclic graphs

paper_content:

In this paper we study automata which work on directed ordered acyclic graphs, in particular those graphs, called derivation dags ( d -dags), which model derivations of phrase-structure grammars. A rather complete characterization of the relative power of the following features of automata on d -dags is obtained: parallel versus sequential, deterministic versus nondeterministic and finite state versus a (restricted type of) pushdown store. New results concerning trees follows as special cases. Closure properties of classes of d -dag languages definable by various automata are studied for some basic operations. Characterization of general directed ordered acyclic graphs by these automata is also given. Contents. Abstract. 1. Introduction. 2. Definitions of the graphs. 3. Parallel dag automata. 4. Finite state relabeling. 5. Two-way dag-walking automata. 6. Comparison. 7. Closure properties of d -dag languages. 8. Recognition of doags. Acknowledgment. References.
---
paper_title: Automata with Nested Pebbles Capture First-Order Logic with Transitive Closure

paper_content:

String languages recognizable in (deterministic) log-space are characterized either by two-way (deterministic) multi-head automata, or following Immerman, by first- order logic with (deterministic) transitive closure. Here we elaborate this result, and match the number of heads to the arity of the transitive closure. More precisely, first-order logic with k-ary deterministic transitive closure has the same power as deterministic automata walking on their input with k heads, additionally using a finite set of nested pebbles. This result is valid for strings, ordered trees, and in general for families of graphs having a fixed automaton that can be used to traverse the nodes of each of the graphs in the family. Other examples of such families are grids, toruses, and rectangular mazes. For nondeterministic automata, the logic is restricted to positive occurrences of transitive closure. The special case of k = 1 for trees, shows that single-head deterministic tree-walking automata with nested pebbles are characterized by first-order logic with unary determin- istic transitive closure. This refines our earlier result that placed these automata between first-order and monadic second-order logic on trees.
---
paper_title: Validating streaming XML documents

paper_content:

This paper investigates the on-line validation of streaming XML documents with respect to a DTD, under memory constraints. We first consider validation using constant memory, formalized by a finite-state automaton ( FSA ). We examine two flavors of the problem, depending on whether or not the XML document is assumed to be well-formed. The main results of the paper provide conditions on the DTDs under which validation of either flavor can be done using an FSA . For DTDs that cannot be validated by an FSA , we investigate two alternatives. The first relaxes the constant memory requirement by allowing a stack bounded in the depth of the XML document, while maintaining the deterministic, one-pass requirement. The second approach consists in refining the DTD to provide additional information that allows validation by an FSA .
---
paper_title: Visibly pushdown languages

paper_content:

We propose the class of visibly pushdown languages as embeddings of context-free languages that is rich enough to model program analysis questions and yet is tractable and robust like the class of regular languages. In our definition, the input symbol determines when the pushdown automaton can push or pop, and thus the stack depth at every position. We show that the resulting class V pl of languages is closed under union, intersection, complementation, renaming, concatenation, and Kleene-*, and problems such as inclusion that are undecidable for context-free languages are E xptime -complete for visibly pushdown automata. Our framework explains, unifies, and generalizes many of the decision procedures in the program analysis literature, and allows algorithmic verification of recursive programs with respect to many context-free properties including access control properties via stack inspection and correctness of procedures with respect to pre and post conditions. We demonstrate that the class V pl is robust by giving two alternative characterizations: a logical characterization using the monadic second order (MSO) theory over words augmented with a binary matching predicate, and a correspondence to regular tree languages. We also consider visibly pushdown languages of infinite words and show that the closure properties, MSO-characterization and the characterization in terms of regular trees carry over. The main difference with respect to the case of finite words turns out to be determinizability: nondeterministic Buchi visibly pushdown automata are strictly more expressive than deterministic Muller visibly pushdown automata.
---
paper_title: Typing and querying XML documents: some complexity bounds

paper_content:

We study the complexity bound of validating XML documents, viewed as labeled unranked ordered trees, against various typing systems like DTDs, XML schemas, tree automata ... We also consider query evaluation complexities for various fragments of XPath. For both problems, validation and query evaluation, we consider data and combined complexity bounds.
---
paper_title: Typing and querying XML documents: some complexity bounds

paper_content:

We study the complexity bound of validating XML documents, viewed as labeled unranked ordered trees, against various typing systems like DTDs, XML schemas, tree automata ... We also consider query evaluation complexities for various fragments of XPath. For both problems, validation and query evaluation, we consider data and combined complexity bounds.
---
paper_title: Deciding equivalence of finite tree automata

paper_content:

We show: for every constant m it can be decided in polynomial time whether or not two m-ambiguous finite tree automata are equivalent. In general, inequivalence for finite tree automata is DEXPTIME-complete w.r.t. logspace reductions, and PSPACE-complete w.r.t. logspace reductions, if the automata in question are supposed to accept only finite languages. For finite tree automata with coefficients in a field R we give a polynomial time algorithm for deciding ambiguity-equivalence provided R-operations and R-tests for 0 can be performed in constant time. We apply this algorithm for deciding ambiguity-inequivalence of finite tree automata in randomized polynomial time.
---
paper_title: Efficient incremental validation of XML documents

paper_content:

We discuss incremental validation of XML documents with respect to DTDs and XML schema definitions. We consider insertions and deletions of subtrees, as opposed to leaf nodes only, and we also consider the validation of ID and IDREF attributes. For arbitrary schemas, we give a worst-case n log n time and linear space algorithm, and show that it often is far superior to revalidation from scratch. We present two classes of schemas, which capture most real-life DTDs, and show that they admit a logarithmic time incremental validation algorithm that, in many cases, requires only constant auxiliary space. We then discuss an implementation of these algorithms that is independent of, and can be customized for different storage mechanisms for XML. Finally, we present extensive experimental results showing that our approach is highly efficient and scalable.
---
paper_title: Regular tree languages definable in FO

paper_content:

We consider regular languages of ranked labeled trees. We give an algebraic characterization of the regular languages over such trees that are definable in first-order logic in the language of labeled graphs. These languages are the analog on ranked trees of the “locally threshold testable” languages on strings. We show that this characterization yields a decision procedure for determining whether a regular collection of trees is first-order definable: the procedure is polynomial time in the minimal automaton presenting the regular language.
---
paper_title: Checking potential validity of XML documents

paper_content:

The process of creation of document-centric XML documents often starts with a prepared textual content, into which the editor introduces markup. In such situations, intermediate XML is almost never valid with respect to the DTD/Schema used for the encoding. At the same time, it is important to ensure that at each moment of time, the editor is working with an XML document that can enriched with further markup to become valid. In this paper we introduce the notion of potential validity of XML documents, which allows us to distinguish between XML documents that are invalid because the encoding is simply incomplete and XML documents that are invalid because some of the DTD rules guiding the structure of the encoding were violated during the markup process. We give a linear-time algorithm for checking potential validity for documents.
---
paper_title: Deterministic Automata on Unranked Trees

paper_content:

We investigate bottom-up and top-down deterministic automata on unranked trees. We show that for an appropriate definition of bottom-up deterministic automata it is possible to minimize the number of states efficiently and to obtain a unique canonical representative of the accepted tree language. For top-down deterministic automata it is well known that they are less expressive than the non-deterministic ones. By generalizing a corresponding proof from the theory of ranked tree automata we show that it is decidable whether a given regular language of unranked trees can be recognized by a top-down deterministic automaton. The standard deterministic top-down model is slightly weaker than the model we use, where at each node the automaton can scan the sequence of the labels of its successors before deciding its next move.
---
paper_title: Minimizing tree automata for unranked trees

paper_content:

Automata for unranked trees form a foundation for XML schemas, querying and pattern languages. We study the problem of efficiently minimizing such automata. We start with the unranked tree automata (UTAs) that are standard in database theory, assuming bottom-up determinism and that horizontal recursion is represented by deterministic finite automata. We show that minimal UTAs in that class are not unique and that minimization is np-hard. We then study more recent automata classes that do allow for polynomial time minimization. Among those, we show that bottom-up deterministic stepwise tree automata yield the most succinct representations.
---
paper_title: Constructing Finite State Automata for High-Performance XML Web Services

paper_content:

This paper describes a validating XML parsing method based on deterministic finite state automata (DFA). XML parsing and validation is performed by a schema-specific XML parser that encodes the admissible parsing states as a DFA. This DFA is automatically constructed from the XML schemas of XML messages using a code generator. A twolevel DFA architecture is used to increase efficiency and to reduce the generated code size. The lower-level DFA efficiently parses syntactically well-formed XML messages. The higher-level DFA validates the messages and produces application events associated with transitions in the DFA. Two example case studies are presented and performance results are given to demonstrate that the approach supports the implementation of high-performance Web services.
---
paper_title: Counting in Trees for Free

paper_content:

It is known that MSO logic for ordered unranked trees is undecidable if Presburger constraints are allowed at children of nodes. We show here that a decidable logic is obtained if we use a modal fixpoint logic instead. We present a characterization of this logic by means of deterministic Presburger tree automata and show how it can be used to express numerical document queries. Surprisingly, the complexity of satisfiability for the extended logic is asymptotically the same as for the original fixpoint logic. The non-emptiness for Presburger tree automata (PTA) is pspace-complete, which is moderate given that it is already pspace-hard to test whether the complement of a regular expression is non-empty. We also identify a subclass of PTAs with a tractable non-emptiness problem. Further, to decide whether a tree t satisfies a formula ϕ is polynomial in the size of ϕ and linear in the size of t.
---
paper_title: DTDs versus XML schema: a practical study

paper_content:

Among the various proposals answering the shortcomings of Document Type Definitions (DTDs), XML Schema is the most widely used. Although DTDs and XML Schema Definitions (XSDs) differ syntactically, they are still quite related on an abstract level. Indeed, freed from all syntactic sugar, XML Schemas can be seen as an extension of DTDs with a restricted form of specialization. In the present paper, we inspect a number of DTDs and XSDs harvested from the web and try to answer the following questions: (1) which of the extra features/expressiveness of XML Schema not allowed by DTDs are effectively used in practice; and, (2) how sophisticated are the structural properties (i.e. the nature of regular expressions) of the two formalisms. It turns out that at present real-world XSDs only sparingly use the new features introduced by XML Schema: on a structural level the vast majority of them can already be defined by DTDs. Further, we introduce a class of simple regular expressions and obtain that a surprisingly high fraction of the content models belong to this class. The latter result sheds light on the justification of simplifying assumptions that sometimes have to be made in XML research.
---
paper_title: Minimal Ascending and Descending Tree Automata

paper_content:

We propose a generalization of the notion "deterministic" to "l-r-deterministic" for descending tree automata (also called root-to-frontier). The corresponding subclass of recognizable tree languages is characterized by a structural property that we name "homogeneous." Given a descending tree automaton recognizing a homogeneous tree language, it can be left-to-right (l-r) determinized and then minimized. The obtained minimal l-r-deterministic tree automaton is characterized algebraically. We exhibit a formal correspondence between the two evaluation modes on trees (ascending and descending) and the two on words (right-to-left and left-to-right). This is possible by embedding trees into the free monoid of pointed trees. We obtain a unified view of the theories of minimization of deterministic ascending and l-r-deterministic descending tree automata.
---
paper_title: Numerical document queries

paper_content:

A query against a database behind a site like Napster may search, e.g., for all users who have downloaded more jazz titles than pop music titles. In order to express such queries, we extend classical monadic second-order logic by Presburger predicates which pose numerical restrictions on the children (content) of an element node and provide a precise automata-theoretic characterization. While the existential fragment of the resulting logic is decidable, it turns out that satisfiability of the full logic is undecidable. Decidable satisfiability and a querying algorithm even with linear data complexity can be obtained if numerical constraints are only applied to those contents of elements where ordering is irrelevant. Finally, it is sketched how these techniques can be extended also to answer questions like, e.g., whether the total price of the jazz music downloaded so far exceeds a user's budget.
---
paper_title: Languages, Automata, and Logic

paper_content:

The subject of this chapter is the study of formal languages (mostly languages recognizable by finite automata) in the framework of mathematical logic.
---
paper_title: Cardinality Constraint Automata: A Core Technology for Efficient XML Schema-aware Parsers

paper_content:

A direct conversion receiver having a tri-phase architecture including three separate baseband signal channels. RF communications signals which are being tuned by the receiver are split into three equal and in-phase components which are mixed with three equal but substantially out-of-phase injection signals on frequency with the communications signal. The resulting baseband component signals are independently filtered and amplified on the three signal channels. The baseband components are then directed to a signal processing unit which corrects the baseband components for gain or phase mismatch errors between the signal channels based on the information carried by the three components and thereafter demodulates the signals in order to acquire the information carried by the RF communications signal. An automatic gain control system and a signal filtering system adapted for use with direct conversion receivers are also disclosed.
---
paper_title: Incremental validation of XML documents

paper_content:

We investigate the incremental validation of XML documents with respect to DTDs, specialized DTDs, and XML Schemas, under updates consisting of element tag renamings, insertions, and deletions. DTDs are modeled as extended context-free grammars. "Specialized DTDs" allow the decoupling of element types from element tags. XML Schemas are abstracted as specialized DTDs with limitations on the type assignment. For DTDs and XML Schemas, we exhibit an O(m log n) incremental validation algorithm using an auxiliary structure of size O(n), where n is the size of the document and m the number of updates. The algorithm does not handle the incremental validation of XML Schema wrt renaming of internal nodes, which is handled by the specialized DTDs incremental validation algorithm. For specialized DTDs, we provide an O(m log2 n) incremental algorithm, again using an auxiliary structure of size O(n). This is a significant improvement over brute-force re-validation from scratch.We exhibit a restricted class of DTDs called local that arise commonly in practice and for which incremental validation can be done in practically constant time by maintaining only a list of counters. We present implementations of both general incremental validation and local validation on an XML database built on top of a relational database.Our experimentation includes a study of the applicability of local validation in practice, results on the calibration of parameters of the auxiliary data structure, and results on the performance comparison between the general incremental validation technique, the local validation technique, and brute-force validation from scratch.
---
paper_title: XML schema, tree logic and sheaves automata

paper_content:

XML documents, and other forms of semi-structured data, may be roughly described as edge labeled trees; it is therefore natural to use tree automata to reason on them. This idea has already been successfully applied in the context of Document Type Definition (DTD), the simplest standard for defining XML documents validity, but additional work is needed to take into account XML Schema, a more advanced standard, for which regular tree automata are not satisfactory. In this paper, we define a tree logic that directly embeds XML Schema as a plain subset as well as a new class of automata for unranked trees, used to decide this logic, which is well-suited to the processing of XML documents and schemas.
---
paper_title: DTD Inference for Views of XML Data

paper_content:

We study the inference of Data Type Definitions (DTDs) for views of XML data, using an abstraction that focuses on document content structure. The views are defined by a query language that produces a list of documents selected from one or more input sources. The selection conditions involve vertical and horizontal navigation, thus querying explicitly the order present in input documents. We point several strong limitations in the descriptive ability of current DTDs and the need for extending them with (i) a subtyping mechanism and (ii) a more powerful specification mechanism than regular languages, such as context-free languages. With these extensions, we show that one can always infer tight DTDs, that precisely characterize a selection view on sources satisfying given DTDs. We also show important special cases where one can infer a tight DTD without requiring extension (ii). Finally we consider related problems such as verifying conformance of a view definition with a predefined DTD. Extensions to more powerful views that construct complex documents are also briefly discussed.
---
paper_title: Taxonomy of XML schema languages using formal language theory

paper_content:

On the basis of regular tree grammars, we present a formal framework for XML schema languages. This framework helps to describe, compare, and implement such schema languages in a rigorous manner. Our main results are as follows: (1) a simple framework to study three classes of tree languages (local, single-type, and regular); (2) classification and comparison of schema languages (DTD, W3C XML Schema, and RELAX NG) based on these classes; (3) efficient document validation algorithms for these classes; and (4) other grammatical concepts and advanced validation algorithms relevant to an XML model (e.g., binarization, derivative-based validation).
---
paper_title: Using regular tree automata as XML schemas

paper_content:

We address the problem of tight XML schemas and propose regular tree automata to model XML data. We show that the tree automata model is more powerful than the XML DTDs and is closed under main algebraic operations. We introduce the XML query algebra based on the tree automata model, and discuss the query optimization and query pruning techniques. Finally we show the conversion of tree automata schema into XML DTDs.
---
paper_title: DTD Inference for Views of XML Data

paper_content:

We study the inference of Data Type Definitions (DTDs) for views of XML data, using an abstraction that focuses on document content structure. The views are defined by a query language that produces a list of documents selected from one or more input sources. The selection conditions involve vertical and horizontal navigation, thus querying explicitly the order present in input documents. We point several strong limitations in the descriptive ability of current DTDs and the need for extending them with (i) a subtyping mechanism and (ii) a more powerful specification mechanism than regular languages, such as context-free languages. With these extensions, we show that one can always infer tight DTDs, that precisely characterize a selection view on sources satisfying given DTDs. We also show important special cases where one can infer a tight DTD without requiring extension (ii). Finally we consider related problems such as verifying conformance of a view definition with a predefined DTD. Extensions to more powerful views that construct complex documents are also briefly discussed.
---
paper_title: Regular expression pattern matching for XML

paper_content:

We propose regular expression pattern matching as a core feature for programming languages for manipulating XML (and similar tree-structured data formats). We extend conventional pattern-matching facilities with regular expression operators such as repetition (*), alternation (I), etc., that can match arbitrarily long sequences of subtrees, allowing a compact pattern to extract data from the middle of a complex sequence. We show how to check standard notions of exhaustiveness and redundancy for these patterns.Regular expression patterns are intended to be used in languages whose type systems are also based on the regular expression types. To avoid excessive type annotations, we develop a type inference scheme that propagates type constraints to pattern variables from the surrounding context. The type inference algorithm translates types and patterns into regular tree automata and then works in terms of standard closure operations (union, intersection, and difference) on tree automata. The main technical challenge is dealing with the interaction of repetition and alternation patterns with the first-match policy, which gives rise to subtleties concerning both the termination and the precision of the analysis. We address these issues by introducing a data structure representing closure operations lazily.
---
paper_title: Taxonomy of XML schema languages using formal language theory

paper_content:

On the basis of regular tree grammars, we present a formal framework for XML schema languages. This framework helps to describe, compare, and implement such schema languages in a rigorous manner. Our main results are as follows: (1) a simple framework to study three classes of tree languages (local, single-type, and regular); (2) classification and comparison of schema languages (DTD, W3C XML Schema, and RELAX NG) based on these classes; (3) efficient document validation algorithms for these classes; and (4) other grammatical concepts and advanced validation algorithms relevant to an XML model (e.g., binarization, derivative-based validation).
---
paper_title: Expressiveness of XSDs: from practice to theory, there and back again

paper_content:

On an abstract level, XML Schema increases the limited expressive power of Document Type Definitions (DTDs) by extending them with a recursive typing mechanism. However, an investigation of the XML Schema Definitions (XSDs) occurring in practice reveals that the vast majority of them are structurally equivalent to DTDs. This might be due to the complexity of the XML Schema specification and the difficulty to understand the effect of constraints on typing and validation of schemas. To shed some light on the actual expressive power of XSDs this paper studies the impact of the Element Declarations Consistent (EDC) and the Unique Particle Attribution (UPA) rule. An equivalent formalism based on contextual patterns rather than on recursive types is proposed which might serve as a light-weight front end for XML Schema. Finally, the effect of EDC and UPA on the way XML documents can be typed is discussed. It is argued that a cleaner, more robust, stronger but equally efficient class is obtained by replacing EDC and UPA with the notion of 1-pass preorder typing: schemas that allow to determine the type of an element of a streaming document when its opening tag is met. This notion can be defined in terms of restrained competition regular expressions and there is again an equivalent syntactical formalism based on contextual patterns.
---
paper_title: DTD Inference for Views of XML Data

paper_content:

We study the inference of Data Type Definitions (DTDs) for views of XML data, using an abstraction that focuses on document content structure. The views are defined by a query language that produces a list of documents selected from one or more input sources. The selection conditions involve vertical and horizontal navigation, thus querying explicitly the order present in input documents. We point several strong limitations in the descriptive ability of current DTDs and the need for extending them with (i) a subtyping mechanism and (ii) a more powerful specification mechanism than regular languages, such as context-free languages. With these extensions, we show that one can always infer tight DTDs, that precisely characterize a selection view on sources satisfying given DTDs. We also show important special cases where one can infer a tight DTD without requiring extension (ii). Finally we consider related problems such as verifying conformance of a view definition with a predefined DTD. Extensions to more powerful views that construct complex documents are also briefly discussed.
---
paper_title: Taxonomy of XML schema languages using formal language theory

paper_content:

On the basis of regular tree grammars, we present a formal framework for XML schema languages. This framework helps to describe, compare, and implement such schema languages in a rigorous manner. Our main results are as follows: (1) a simple framework to study three classes of tree languages (local, single-type, and regular); (2) classification and comparison of schema languages (DTD, W3C XML Schema, and RELAX NG) based on these classes; (3) efficient document validation algorithms for these classes; and (4) other grammatical concepts and advanced validation algorithms relevant to an XML model (e.g., binarization, derivative-based validation).
---
paper_title: Which XML schemas admit 1-pass preorder typing?

paper_content:

It is shown that the class of regular tree languages admitting one-pass preorder typing is exactly the class defined by restrained competition tree grammars introduced by Murata et al. [14]. In a streaming context, the former is the largest class of XSDs where every element in a document can be typed when its opening tag is met. The main technical machinery consists of semantical characterizations of restrained competition grammars and their subclasses. In particular, they can be characterized in terms of the context of nodes, closure properties, allowed patterns and guarded DTDs. It is further shown that deciding whether a schema is restrained competition is tractable. Deciding whether a schema is equivalent to a restrained competition tree grammar, or one of its subclasses, is much more difficult: it is complete for EXPTIME. We show that our semantical characterizations allow for easy optimization and minimization algorithms. Finally, we relate the notion of one-pass preorder typing to the existing XML Schema standard.
---
paper_title: Complexity of Decision Problems for Simple Regular Expressions

paper_content:

We study the complexity of the inclusion, equivalence, and intersection problem for simple regular expressions arising in practical XML schemas. These basically consist of the concatenation of factors where each factor is a disjunction of strings possibly extended with '*' or '?'. We obtain lower and upper bounds for various fragments of simple regular expressions. Although we show that inclusion and intersection are already intractable for very weak expressions, we also identify some tractable cases. For equivalence, we only prove an initial tractability result leaving the complexity of more general cases open. The main motivation for this research comes from database theory, or more specifically XML and semi-structured data. We namely show that all lower and upper bounds for inclusion and equivalence, carry over to the corresponding decision problems for extended context-free grammars and single-type tree grammars, which are abstractions of DTDs and XML Schemas, respectively. For intersection, we show that the complexity only carries over for DTDs.
---
paper_title: Which XML schemas admit 1-pass preorder typing?

paper_content:

It is shown that the class of regular tree languages admitting one-pass preorder typing is exactly the class defined by restrained competition tree grammars introduced by Murata et al. [14]. In a streaming context, the former is the largest class of XSDs where every element in a document can be typed when its opening tag is met. The main technical machinery consists of semantical characterizations of restrained competition grammars and their subclasses. In particular, they can be characterized in terms of the context of nodes, closure properties, allowed patterns and guarded DTDs. It is further shown that deciding whether a schema is restrained competition is tractable. Deciding whether a schema is equivalent to a restrained competition tree grammar, or one of its subclasses, is much more difficult: it is complete for EXPTIME. We show that our semantical characterizations allow for easy optimization and minimization algorithms. Finally, we relate the notion of one-pass preorder typing to the existing XML Schema standard.
---
paper_title: Validating streaming XML documents

paper_content:

This paper investigates the on-line validation of streaming XML documents with respect to a DTD, under memory constraints. We first consider validation using constant memory, formalized by a finite-state automaton ( FSA ). We examine two flavors of the problem, depending on whether or not the XML document is assumed to be well-formed. The main results of the paper provide conditions on the DTDs under which validation of either flavor can be done using an FSA . For DTDs that cannot be validated by an FSA , we investigate two alternatives. The first relaxes the constant memory requirement by allowing a stack bounded in the depth of the XML document, while maintaining the deterministic, one-pass requirement. The second approach consists in refining the DTD to provide additional information that allows validation by an FSA .
---
paper_title: Which XML schemas admit 1-pass preorder typing?

paper_content:

It is shown that the class of regular tree languages admitting one-pass preorder typing is exactly the class defined by restrained competition tree grammars introduced by Murata et al. [14]. In a streaming context, the former is the largest class of XSDs where every element in a document can be typed when its opening tag is met. The main technical machinery consists of semantical characterizations of restrained competition grammars and their subclasses. In particular, they can be characterized in terms of the context of nodes, closure properties, allowed patterns and guarded DTDs. It is further shown that deciding whether a schema is restrained competition is tractable. Deciding whether a schema is equivalent to a restrained competition tree grammar, or one of its subclasses, is much more difficult: it is complete for EXPTIME. We show that our semantical characterizations allow for easy optimization and minimization algorithms. Finally, we relate the notion of one-pass preorder typing to the existing XML Schema standard.
---
paper_title: TypEx: A Type Based Approach to XML Stream Querying

paper_content:

We consider the topic of query evaluation over semistructured information streams, and XML data streams in particular. Streaming evaluation methods are necessarily eventdriven, which is in tension with high-level query models; in general, the more expressive the query language, the harder it is to translate queries into an event-based implementation with finite resource bounds.
---
paper_title: On validation of XML streams using finite state machines

paper_content:

We study validation of streamed XML documents by means of finite state machines. Previous work has shown that validation is in principle possible by finite state automata, but the construction was prohibitively expensive, giving an exponential-size nondeterministic automaton. Instead, we want to find deterministic automata for validating streamed documents: for them, the complexity of validation is constant per tag. We show that for a reading window of size one and nonrecursive DTDs with one-unambiguous content (i.e. conforming to the current XML standard) there is an algorithm producing a deterministic automaton that validates documents with respect to that DTD. The size of the automaton is at most exponential and we give matching lower bounds. To capture the possible advantages offered by reading windows of size k, we introduce k-unambiguity as a generalization of one-unambiguity, and study the validation against DTDs with k-unambiguous content. We also consider recursive DTDs and give conditions under which they can be validated against by using one-counter automata.
---
paper_title: Querying unranked trees with stepwise tree automata

paper_content:

The problem of selecting nodes in unranked trees is the most basic querying problem for XML. We propose stepwise tree automata for querying unranked trees. Stepwise tree automata can express the same monadic queries as monadic Datalog and monadic second-order logic. We prove this result by reduction to the ranked case, via a new systematic correspondence that relates unranked and ranked queries.
---
paper_title: Locating Matches of Tree Patterns in Forests

paper_content:

We deal with matching and locating of patterns in forests of variable arity. A pattern consists of a structural and a contextual condition for subtrees of a forest, both of which are given as tree or forest regular languages. We use the notation of constraint systems to uniformly specify both kinds of conditions. In order to implement pattern matching we introduce the class of pushdown forest automata. We identify a special class of contexts such that not only pattern matching but also locating all of a forest’s subtrees matching in context can be performed in a single traversal. We also give a method for computing the reachable states of an automaton in order to minimize the size of transition tables.
---
paper_title: Expressiveness of structured document query languages based on attribute grammars

paper_content:

Structured document databases can be naturally viewed as derivation trees of a context-free grammar. Under this view, the classical formalism of attribute grammars becomes a formalism for structured document query languages. From this perspective, we study the expressive power of BAGs: Boolean-valued attribute grammars with propositional logic formulas as semantic rules, and RAGs: relation-valued attribute grammars with first-order logic formulas as semantic rules. BAGs can express only unary queries; RAGs can express queries of any arity. We first show that the (unary) queries expressible by BAGs are precisely those definable in monadic second-order logic. We then show that the queries expressible by RAGs are precisely those definable by first-order inductions of linear depth, or, equivalently, those computable in linear time on a parallel machine with polynomially many processors. Further, we show that RAGs that only use synthesized attributes are strictly weaker than RAGs that use both synthesized and inherited attributes. We show that RAGs are more expressive than monadic second-order logic for queries of any arity. Finally, we discuss relational attribute grammars in the context of BAGs and RAGs. We show that in the case of BAGs this does not increase the expressive power, while different semantics for relational RAGs capture the complexity classes NP, coNP and UP ∩ coUP.
---
paper_title: Comparing the succinctness of monadic query languages over finite trees

paper_content:

We study the succinctness of monadic second-order logic and a variety of monadic fixed point logics on trees. All these languages are known to have the same expressive power on trees, but some can express the same queries much more succinctly than others. For example, we show that, under some complexity theoretic assumption, monadic second-order logic is non-elementarily more succinct than monadic least fixed point logic, which in turn is non-elementarily more succinct than monadic datalog.
---
paper_title: Attribute Grammars for Unranked Trees as a query language for structured documents

paper_content:

Document specification languages, like for instance XML, model documents using extended context-free grammars. These differ from standard context-free grammars in that they allow arbitrary regular expressions on the right-hand side of productions. To query such documents, we introduce a new form of attribute grammars (extended AGs) that work directly over extended context-free grammars rather than over standard context-free grammars. Viewed as a query language, extended AGs are particularly relevant as they can take into account the inherent order of the children of a node in a document. We show that non-circularity remains decidable in EXPTIME and establish the complexity of the non-emptiness and equivalence problem of extended AGs to be complete for EXPTIME. As an application we show that the Region Algebra expressions can be efficiently translated into extended AGs. This translation drastically improves the known upper bound on the complexity of the emptiness and equivalence test for Region Algebra expressions from non-elementary to EXPTIME. Finally, we characterize the expressiveness of extended AGs in terms of monadic second-order logic.
---
paper_title: The Regularity of Two-Way Nondeterministic Tree Automata Languages

paper_content:

We establish that regularly extended two-way nondeterministic tree automata with unranked alphabets have the same expressive power as regularly extended nondeterministic tree automata with unranked alphabets alphabets. We obtain this results by establishing regularly extended versions of a congruence on trees and of a congruence on, so called, views. Our motivation for the study of these tree models is the Extensible Markup Language (XML), a metalanguage for defining document grammars. Such grammars have regular sets of right-hand sides for their productions and tree automata provide an alternative and useful modeling tool for them. In particular, we believe that they provide a useful computational model for what we call caterpillar expressions.
---
paper_title: Monadic datalog and the expressive power of languages for Web information extraction

paper_content:

Research on information extraction from Web pages (wrapping) has seen much activity in recent times (particularly systems implementations), but little work has been done on formally studying the expressiveness of the formalisms proposed or on the theoretical foundations of wrapping.In this paper, we first study monadic datalog as a wrapping language (over ranked or unranked tree structures). Using previous work by Neven and Schwentick, we show that this simple language is equivalent to full monadic second order logic (MSO) in its ability to specify wrappers. We believe that MSO has the right expressiveness required for Web information extraction and thus propose MSO as a yardstick for evaluating and comparing wrappers.Using the above result, we study the kernel fragment Elog- of the Elog wrapping language used in the Lixto system (a visual wrapper generator). The striking fact here is that Elog- exactly captures MSO, yet is easier to use. Indeed, programs in this language can be entirely visually specified. We also formally compare Elog to other wrapping languages proposed in the literature.
---
paper_title: Satisfiability of XPath Expressions

paper_content:

In this paper, we investigate the complexity of deciding the satisfiability of XPath 2.0 expressions, i.e., whether there is an XML document for which their result is nonempty. Several fragments that allow certain types of expressions are classified as either in PTIME or NP-hard to see which type of expression make this a hard problem. Finally, we establish a link between XPath expressions and partial tree descriptions which are studied in computational linguistics.
---
paper_title: Monadic datalog and the expressive power of languages for Web information extraction

paper_content:

Research on information extraction from Web pages (wrapping) has seen much activity in recent times (particularly systems implementations), but little work has been done on formally studying the expressiveness of the formalisms proposed or on the theoretical foundations of wrapping.In this paper, we first study monadic datalog as a wrapping language (over ranked or unranked tree structures). Using previous work by Neven and Schwentick, we show that this simple language is equivalent to full monadic second order logic (MSO) in its ability to specify wrappers. We believe that MSO has the right expressiveness required for Web information extraction and thus propose MSO as a yardstick for evaluating and comparing wrappers.Using the above result, we study the kernel fragment Elog- of the Elog wrapping language used in the Lixto system (a visual wrapper generator). The striking fact here is that Elog- exactly captures MSO, yet is easier to use. Indeed, programs in this language can be entirely visually specified. We also formally compare Elog to other wrapping languages proposed in the literature.
---
paper_title: DTDs versus XML schema: a practical study

paper_content:

Among the various proposals answering the shortcomings of Document Type Definitions (DTDs), XML Schema is the most widely used. Although DTDs and XML Schema Definitions (XSDs) differ syntactically, they are still quite related on an abstract level. Indeed, freed from all syntactic sugar, XML Schemas can be seen as an extension of DTDs with a restricted form of specialization. In the present paper, we inspect a number of DTDs and XSDs harvested from the web and try to answer the following questions: (1) which of the extra features/expressiveness of XML Schema not allowed by DTDs are effectively used in practice; and, (2) how sophisticated are the structural properties (i.e. the nature of regular expressions) of the two formalisms. It turns out that at present real-world XSDs only sparingly use the new features introduced by XML Schema: on a structural level the vast majority of them can already be defined by DTDs. Further, we introduce a class of simple regular expressions and obtain that a surprisingly high fraction of the content models belong to this class. The latter result sheds light on the justification of simplifying assumptions that sometimes have to be made in XML research.
---
paper_title: First order paths in ordered trees

paper_content:

We give two sufficient conditions on XPath like languages for having first order expressivity, meaning that every first order definable set of paths in an ordered node-labeled tree is definable in that XPath language. They are phrased in terms of expansions of navigational (sometimes called “Core”) XPath. Adding either complementation, or the more elegant conditional paths is sufficient. A conditional path is an axis relation of the form (one_step_axis::n[F])+, denoting the transitive closure of the relation expressed by one_step_axis::n[F]. As neither is expressible in navigational XPath we also give characterizations in terms of first order logic of the answer sets and the sets of paths navigational XPath can define. The first in terms of a suitable two variable fragment, the second in terms of unions of conjunctive queries.
---
paper_title: Satisfiability of XPath Expressions

paper_content:

In this paper, we investigate the complexity of deciding the satisfiability of XPath 2.0 expressions, i.e., whether there is an XML document for which their result is nonempty. Several fragments that allow certain types of expressions are classified as either in PTIME or NP-hard to see which type of expression make this a hard problem. Finally, we establish a link between XPath expressions and partial tree descriptions which are studied in computational linguistics.
---
paper_title: Efficient algorithms for processing XPath queries

paper_content:

Our experimental analysis of several popular XPath processors reveals a striking fact: Query evaluation in each of the systems requires time exponential in the size of queries in the worst case. We show that XPath can be processed much more efficiently, and propose main-memory algorithms for this problem with polynomial-time combined query evaluation complexity. Moreover, we show how the main ideas of our algorithm can be profitably integrated into existing XPath processors. Finally, we present two fragments of XPath for which linear-time query processing algorithms exist and another fragment with linear-space/quadratic-time query processing.
---
paper_title: Containment and Integrity Constraints for XPath Fragments

paper_content:

XPath is a W3C standard that plays a crucial role in several influential query, transformation, and schema standards for XML. Motivated by the larger challenge of XML query optimization, we investigate the problem of containment of XPath expressions under integrity constraints that are in turn formulated with the help of XPath expressions. Our core formalism consists of a fragment of XPath that we call simple and a corresponding class of integrity constraints that we call simple XPath integrity constraints (SXIC). SXIC's can express many database-style constraints, including key and foreign key constraints specified in the XML Schema standard proposal, as well as many constraints implied by DTDs. We identify a subclass of bounded SXIC's under which containment of simple XPath expressions is decidable, but we show that even modest use of unbounded SXIC's makes the problem undecidable. In particular, the addition of (unbounded) constraints implied by DTDs leads to undecidability. We give tight Πp2 bounds for the simple XPath containment problem and tight NP bounds for the disjunction-free subfragment, while even identifying a PTIME subcase. We also show that decidability of containment under SXIC's still holds if the expressions contain certain additional features (e.g., wildcard) although the complexity jumps to Πp2 even for the disjunction-free subfragment. We know that our results can be extended to some but not all of the XPath features that depend on document order. The decidability of containment of simple XPath expressions in the presence of DTDs only remains open (although we can show that the problem is PSPACE-hard) as well as the problem for full-fledged XPath expressions, even in the absence of integrity constraints.
---
paper_title: Comparing the succinctness of monadic query languages over finite trees

paper_content:

We study the succinctness of monadic second-order logic and a variety of monadic fixed point logics on trees. All these languages are known to have the same expressive power on trees, but some can express the same queries much more succinctly than others. For example, we show that, under some complexity theoretic assumption, monadic second-order logic is non-elementarily more succinct than monadic least fixed point logic, which in turn is non-elementarily more succinct than monadic datalog.
---
paper_title: Cache-conscious automata for XML filtering

paper_content:

Hardware cache behavior is an important factor in the performance of memory-resident, data-intensive systems such as XML filtering engines. A key data structure in several recent XML filters is the automaton, which is used to represent the long-running XML queries in the main memory. In this paper, we study the cache performance of automaton-based XML filtering through analytical modeling and system measurement. Furthermore, we propose a cache-conscious automaton organization technique, called the hot buffer, to improve the locality of automaton state transitions. Our results show that (1) our cache performance model for XML filtering automata is highly accurate and (2) the hot buffer improves the cache performance as well as the overall performance of automaton-based XML filtering.
---
paper_title: XPath processing in a nutshell

paper_content:

We provide a concise yet complete formal definition of the semantics of XPath 1 and summarize efficient algorithms for processing queries in this language. Our presentation is intended both for the reader who is looking for a short but comprehensive formal account of XPath as well as the software developer in need of material that facilitates the rapid implementation of XPath engines.
---
paper_title: XPath Containment in the Presence of Disjunction, DTDs, and Variables

paper_content:

XPath is a simple language for navigating an XML tree and returning a set of answer nodes. The focus in this paper is on the complexity of the containment problem for various fragments of XPath. In addition to the basic operations (child, descendant, filter, and wildcard), we consider disjunction, DTDs and variables. W.r.t. variables we study two semantics: (1) the value of variables is given by an outer context; (2) the value of variables is defined existentially. We establish an almost complete classification of the complexity of the containment problem w.r.t. these fragments.
---
paper_title: Containment and equivalence for a fragment of XPath

paper_content:

XPath is a language for navigating an XML document and selecting a set of element nodes. XPath expressions are used to query XML data, describe key constraints, express transformations, and reference elements in remote documents. This article studies the containment and equivalence problems for a fragment of the XPath query language, with applications in all these contexts.In particular, we study a class of XPath queries that contain branching, label wildcards and can express descendant relationships between nodes. Prior work has shown that languages that combine any two of these three features have efficient containment algorithms. However, we show that for the combination of features, containment is coNP-complete. We provide a sound and complete algorithm for containment that runs in exponential time, and study parameterized PTIME special cases. While we identify one parameterized class of queries for which containment can be decided efficiently, we also show that even with some bounded parameters, containment remains coNP-complete. In response to these negative results, we describe a sound algorithm that is efficient for all queries, but may return false negatives in some cases.
---
paper_title: The complexity of XPath query evaluation

paper_content:

In this paper, we study the precise complexity of XPath 1.0 query processing. Even though heavily used by its incorporation into a variety of XML-related standards, the precise cost of evaluating an XPath query is not yet wellunderstood. The first polynomial-time algorithm for XPath processing (with respect to combined complexity) was proposed only recently, and even to this day all major XPath engines take time exponential in the size of the input queries. From the standpoint of theory, the precise complexity of XPath query evaluation is open, and it is thus unknown whether the query evaluation problem can be parallelized.In this work, we show that both the data complexity and the query complexity of XPath 1.0 fall into lower (highly parallelizable) complexity classes, but that the combined complexity is PTIME-hard. Subsequently, we study the sources of this hardness and identify a large and practically important fragment of XPath 1.0 for which the combined complexity is LOGCFL-complete and, therefore, in the highly parallelizable complexity class NC 2 .
---
paper_title: XPath queries on streaming data

paper_content:

We present the design and implementation of the XSQ system for querying streaming XML data using XPath 1.0. Using a clean design based on a hierarchical arrangement of pushdown transducers augmented with buffers, XSQ supports features such as multiple predicates, closures, and aggregation. XSQ not only provides high throughput, but is also memory efficient: It buffers only data that must be buffered by any streaming XPath processor. We also present an empirical study of the performance characteristics of XPath features, as embodied by XSQ and several other systems.
---
paper_title: Monadic datalog and the expressive power of languages for Web information extraction

paper_content:

Research on information extraction from Web pages (wrapping) has seen much activity in recent times (particularly systems implementations), but little work has been done on formally studying the expressiveness of the formalisms proposed or on the theoretical foundations of wrapping.In this paper, we first study monadic datalog as a wrapping language (over ranked or unranked tree structures). Using previous work by Neven and Schwentick, we show that this simple language is equivalent to full monadic second order logic (MSO) in its ability to specify wrappers. We believe that MSO has the right expressiveness required for Web information extraction and thus propose MSO as a yardstick for evaluating and comparing wrappers.Using the above result, we study the kernel fragment Elog- of the Elog wrapping language used in the Lixto system (a visual wrapper generator). The striking fact here is that Elog- exactly captures MSO, yet is easier to use. Indeed, programs in this language can be entirely visually specified. We also formally compare Elog to other wrapping languages proposed in the literature.
---
paper_title: Processing XML Streams with Deterministic Automata

paper_content:

We consider the problem of evaluating a large number of XPath expressions on an XML stream. Our main contribution consists in showing that Deterministic Finite Automata (DFA) can be used effectively for this problem: in our experiments we achieve a throughput of about 5.4MB/s, independent of the number of XPath expressions (up to 1,000,000 in our tests). The major problem we face is that of the size of the DFA. Since the number of states grows exponentially with the number of XPath expressions, it was previously believed that DFAs cannot be used to process large sets of expressions. We make a theoretical analysis of the number of states in the DFA resulting from XPath expressions, and consider both the case when it is constructed eagerly, and when it is constructed lazily. Our analysis indicates that, when the automaton is constructed lazily, and under certain assumptions about the structure of the input XML data, the number of states in the lazy DFA is manageable. We also validate experimentally our findings, on both synthetic and real XML data sets.
---
paper_title: Containment for XPath Fragments under DTD Constraints

paper_content:

The containment and equivalence problems for various fragments of XPath have been studied by a number of authors. For some fragments, deciding containment (and even minimisation) has been shown to be in PTIME, while for minor extensions containment has been shown to be CONP-complete. When containment is with respect to trees satisfying a set of constraints (such as a schema or DTD), the problem seems to be more difficult. For example, containment under DTDs is CONP-complete for an XPath fragment denoted XP{[ ]} for which containment is in PTIME. It is also undecidable for a larger class of XPath queries when the constraints are so-called simple XPath integrity constraints (SXICs). In this paper, we show that containment is decidable for an important fragment of XPath, denoted XP{[ ], *, //}, when the constraints are DTDs. We also identify XPath fragments for which containment under DTDs can be decided in PTIME.
---
paper_title: XPath with conditional axis relations

paper_content:

This paper is about the W3C standard node-addressing language for XML documents, called XPath. XPath is still under development. Version 2.0 appeared in 2001 while the theoretical foundations of Version 1.0 (dating from 1998) are still being widely studied. The paper aims at bringing XPath to a “stable fixed point” in its development: a version which is expressively complete, still manageable computationally, with a user-friendly syntax and a natural semantics. We focus on an important axis relation which is not expressible in XPath 1.0 and is very useful in practice: the conditional axis. With it we can express paths specified by for instance “do a child step, while test is true at the resulting node”. We study the effect of adding conditional axis relations to XPath on its expressive power and the complexity of the query evaluation and query equivalence problems. We define an XPath dialect \(\mathcal{X}\)CPath which is expressively complete, has a linear time query evaluation algorithm and for which query equivalence given a DTD can be decided in exponential time.
---
paper_title: XPath and Modal Logics of Finite DAG‘s

paper_content:

XPath, CTL and the modal logics proposed by Blackburn et al, Palm and Kracht are variable free formalisms to describe and reason about (finite) trees. XPath expressions evaluated at the root of a tree correspond to existential positive modal formulas. The models of XPath expressions are finite ordered trees, or in the presence of XML’s ID/IDREF mechanism graphs. The ID/IDREF mechanism can be seen as a device for naming nodes. Naming devices have been studied in hybrid logic by nominals. We add nominals to the modal logic of Palm and interpret the language on directed acyclic graphs. We give an algorithm which decides the consequence problem of this logic in exponential time. This yields a complexity result for query containment of the corresponding extension of XPath.
---
paper_title: The complexity of first-order and monadic second-order logic revisited

paper_content:

The model-checking problem for a logic L on a class C of structures asks whether a given L-sentence holds in a given structure in C. In this paper, we give super-exponential lower bounds for fixed-parameter tractable model-checking problems for first-order and monadic second-order logic. We show that unless PTIME=NP, the model-checking problem for monadic second-order logic on finite words is not solvable in time f(k)/spl middot/p(n), for any elementary function f and any polynomial p. Here k denotes the size of the input sentence and n the size of the input word. We prove the same result for first-order logic under a stronger complexity theoretic assumption from parameterized complexity theory. Furthermore, we prove that the model-checking problems for first-order logic on structures of degree 2 and of bounded degree d/spl ges/3 are not solvable in time 2(2/sup o(k)/)/spl middot/p(n) (for degree 2) and 2(2/sup 2o(k)/)/spl middot/p(n) (for degree d), for any polynomial p, again under an assumption from parameterized complexity theory. We match these lower bounds by corresponding upper bounds.
---
paper_title: N-ary Queries by Tree Automata

paper_content:

We investigate n-ary node selection queries in trees by successful runs of tree automata. We show that run-based n-ary queries capture MSO, contribute algorithms for enumerating answers of n-ary queries, and study the complexity of the problem. We investigate the subclass of run-based n-ary queries by unambiguous tree automata.
---
paper_title: Looping caterpillars

paper_content:

There are two main paradigms for querying semi structured data: regular path queries and XPath. The aim of this paper is to provide a synthesis between these two. This synthesis is given by a small addition to tree walk automata and the corresponding caterpillar expressions. These are evaluated on unranked finite sibling-ordered trees. At the expression level we add an operator whose meaning is intersection with the identity relation. This language can express every first-order definable relation and its expressive power is characterized by pebble tree walk automata that cannot inspect pebbles. We also define an expansion of the caterpillar expressions whose expressive power is characterized by ordinary pebble tree walk automata. Combining results from Bloem-Engelfriet and Gottlob-Koch, we also define an XPath like query language which is complete for all MSO definable binary relations.
---
paper_title: First order paths in ordered trees

paper_content:

We give two sufficient conditions on XPath like languages for having first order expressivity, meaning that every first order definable set of paths in an ordered node-labeled tree is definable in that XPath language. They are phrased in terms of expansions of navigational (sometimes called “Core”) XPath. Adding either complementation, or the more elegant conditional paths is sufficient. A conditional path is an axis relation of the form (one_step_axis::n[F])+, denoting the transitive closure of the relation expressed by one_step_axis::n[F]. As neither is expressible in navigational XPath we also give characterizations in terms of first order logic of the answer sets and the sets of paths navigational XPath can define. The first in terms of a suitable two variable fragment, the second in terms of unions of conjunctive queries.
---
paper_title: A Formal Model for an Expressive Fragment of XSLT

paper_content:

The aim of this paper is two-fold. First, we want to show that the recent extension of XSL with variables and passing of data values between template rules has increased its expressiveness beyond that of most other current XML query languages. Second, in an attempt to increase the understanding of this already wide-spread but not so transparent language, we provide an essential and powerful fragment with a formal syntax and a precise semantics.
---
paper_title: Typechecking Top-Down Uniform Unranked Tree Transducers

paper_content:

We investigate the typechecking problem for XML queries: statically verifying that every answer to a query conforms to a given output schema, for inputs satisfying a given input schema. As typechecking quickly turns undecidable for query languages capable of testing equality of data values, we return to the limited framework where we abstract XML documents as labeled ordered trees. We focus on simple top-down recursive transformations motivated by XSLT and structural recursion on trees. We parameterize the problem by several restrictions on the transformations (deleting, non-deleting, bounded width) and consider both tree automata and DTDs as output schemas. The complexity of the typechecking problems in this scenario range from PTIME to EXPTIME.
---
paper_title: Syntax-Directed Semantics: Formal Models Based on Tree Transducers

paper_content:

From the Publisher: ::: This is a motivated presentation of recent results on tree transducers, applied to studying the general properties of formal models and for providing semantics to context-free languages.
---
paper_title: Typechecking for Semistructured Data

paper_content:

Semistructured data is used in data exchange applications, like B2B and EAI, and represents data in a flexible format. Every data item has a unique tag (also called label), and data items can be nested. Formally, a semistructured data instance is a tree whose nodes are labeled with tags and leaves are labeled with data values. XML [Con98] is a standard syntax for describing such trees; Fig. 1 shows a tree representing a semistructured data instance and its XML syntax. We will refer interchangeably to semistructured data instances as trees or XML trees.
---
paper_title: A comparison of pebble tree transducers with macro tree transducers

paper_content:

The n-pebble tree transducer was recently proposed as a model for XML query languages. The four main results on deterministic transducers are: First, (1) the translation $\tau$ of an n-pebble tree transducer can be realized by a composition of n+1 0-pebble tree transducers. Next, the pebble tree transducer is compared with the macro tree transducer, a well-known model for syntax-directed semantics, with decidable type checking. The -pebble tree transducer can be simulated by the macro tree transducer, which, by the first result, implies that (2) $\tau$ can be realized by an (n+1)-fold composition of macro tree transducers. Conversely, every macro tree transducer can be simulated by a composition of 0-pebble tree transducers. Together these simulations prove that (3) the composition closure of n-pebble tree transducers equals that of macro tree transducers (and that of 0-pebble tree transducers). Similar results hold in the nondeterministic case. Finally, (4) the output languages of deterministic n-pebble tree transducers form a hierarchy with respect to the number n of pebbles.
---
paper_title: Typechecking for XML transformers

paper_content:

We study the typechecking problem for XML (eXtensible Markup Language) transformers: given an XML transformation program and a DTD for the input XML documents, check whether every result of the program conforms to a specified output DTD. We model XML transformers using a novel device called a k-pebble transducer, that can express most queries without data-value joins in XML-QL, XSLT, and other XML query languages. Types are modeled by regular tree languages, a robust extension of DTDs. The main result of the paper is that typechecking for k-pebble transducers is decidable. Consequently, typechecking can be performed for a broad range of XML transformation languages, including XML-QL and a fragment of XSLT.
---
paper_title: A comparison of pebble tree transducers with macro tree transducers

paper_content:

The n-pebble tree transducer was recently proposed as a model for XML query languages. The four main results on deterministic transducers are: First, (1) the translation $\tau$ of an n-pebble tree transducer can be realized by a composition of n+1 0-pebble tree transducers. Next, the pebble tree transducer is compared with the macro tree transducer, a well-known model for syntax-directed semantics, with decidable type checking. The -pebble tree transducer can be simulated by the macro tree transducer, which, by the first result, implies that (2) $\tau$ can be realized by an (n+1)-fold composition of macro tree transducers. Conversely, every macro tree transducer can be simulated by a composition of 0-pebble tree transducers. Together these simulations prove that (3) the composition closure of n-pebble tree transducers equals that of macro tree transducers (and that of 0-pebble tree transducers). Similar results hold in the nondeterministic case. Finally, (4) the output languages of deterministic n-pebble tree transducers form a hierarchy with respect to the number n of pebbles.
---
paper_title: The Macro Tree Transducer Hierarchy Collapses for Functions of Linear Size Increase

paper_content:

Every composition of macro tree transducers that is a function of linear size increase can be realized by just one macro tree transducer. For a given composition it is decidable whether or not it is of linear size increase; if it is, then an equivalent macro tree transducer can be constructed effectively.
---
paper_title: Transformation of XML data using an unranked tree transducer

paper_content:

Transformation of data documents is of special importance to use XML as the universal data interchange format on the Web. Data transformation is used in many tasks that require data to be transferred between existing, independently created Web-oriented applications. To perform such transformation one can use W3C’s XSLT or XQuery. But these languages are devoted to detailed programming of transformation procedures. In this paper we show how data transformation can by specify by means of high-level rule specifications based on uniform unranked tree transducers. We show that our approach is both descriptive and expressive, and we illustrate how it can be used to specify and perform transformations of XML documents.
---
paper_title: Structured document transformations based on XSL

paper_content:

Based on the recursion mechanism of the XML transformation language XSL, the document transformation language DTL is defined. First the instantiation DTLreg is considered that uses regular expressions as pattern language. This instantiation closely resembles the navigation mechanism of XSL. For DTLreg the complexity of relevant decision problems such as termination of programs, usefulness of rules and equivalence of selection patterns, is addressed. Next, a much more powerful abstraction of XSL is considered that uses monadic second-order logic formulas as pattern language (DTLmso). If DTLmso is restricted to top-down transformations (DTLdmso), then a computational model can be defined which is a natural generalization to unranked trees of topdown tree transducers with look-ahead. The look-ahead can be realized by a straightforward bottom-up pre-processing pass through the document. The size of the output of an XSL program is at most exponential in the size of the input. By restricting copying in XSL a decidable fragment of DTLdmso programs is obtained which induces transformations of linear size increase (safe DTLdmso). It is shown that the emptiness and finiteness problems are decidable for ranges of DTLdmso programs and that the ranges are closed under intersection with generalized Document Type Definitions (DTDs).
---
paper_title: A High-Level Language for Specifying XML Data Transformations

paper_content:

We propose a descriptive high-level language XDTrans devoted to specify transformations over XML data. The language is based on unranked tree automata approach. In contrast to W3C's XQuery or XSLT which require programming skills, our approach uses high-level ions reflecting intuitive understanding of tree oriented nature of XML data. XDTrans specifies transformations by means of rules which involve XPath expressions, node variables and non-terminal symbols denoting fragments of a constructed result. We propose syntax and semantics for the language as well as algorithms translating a class of transformations into XSLT.
---
paper_title: The equivalence problem for deterministic MSO tree transducers is decidable

paper_content:

It is decidable for deterministic MSO definable graph-to-string or graph-to-tree transducers whether they are equivalent on a context-free set of graphs.
---
paper_title: XML with data values: typechecking revisited

paper_content:

We investigate the type checking problem for XML queries: statically verifying that every answer to a query conforms to a given output DTD, for inputs satisfying a given input DTD. This problem had been studied by a subset of the authors in a simplified framework that captured the structure of XML documents but ignored data values. We revisit here the type checking problem in the more realistic case when data values are present in documents and tested by queries. In this extended framework, type checking quickly becomes undecidable. However, it remains decidable for large classes of queries and DTDs of practical interest. The main contribution of the present paper is to trace a fairly tight boundary of decidability for type checking with data values. The complexity of type checking in the decidable cases is also considered.
---
paper_title: Typechecking Top-Down Uniform Unranked Tree Transducers

paper_content:

We investigate the typechecking problem for XML queries: statically verifying that every answer to a query conforms to a given output schema, for inputs satisfying a given input schema. As typechecking quickly turns undecidable for query languages capable of testing equality of data values, we return to the limited framework where we abstract XML documents as labeled ordered trees. We focus on simple top-down recursive transformations motivated by XSLT and structural recursion on trees. We parameterize the problem by several restrictions on the transformations (deleting, non-deleting, bounded width) and consider both tree automata and DTDs as output schemas. The complexity of the typechecking problems in this scenario range from PTIME to EXPTIME.
---
paper_title: Typechecking XML views of relational databases

paper_content:

Motivated by the need to export relational databases as XML data in the context of the World Wide Web, we investigate the type-checking problem for transformations of relational data into tree data (i.e. XML). The problem consists of statically verifying that the output of every transformation belongs to a given output tree language (specified for XML by a document type definition), for input databases satisfying given integrity constraints. The type-checking problem is parameterized by the class of formulas defining the transformation, the class of output tree languages and the class of integrity constraints. While undecidable in its most general formulation, the type-checking problem has many special cases of practical interest that turn out to be decidable. The main contribution of this paper is to trace a fairly tight boundary of decidability for type-checking in this framework. In the decidable cases, we examine the complexity and show lower and upper bounds. We also exhibit a practically appealing restriction for which type-checking is in PTIME.
---
paper_title: Typechecking for XML transformers

paper_content:

We study the typechecking problem for XML (eXtensible Markup Language) transformers: given an XML transformation program and a DTD for the input XML documents, check whether every result of the program conforms to a specified output DTD. We model XML transformers using a novel device called a k-pebble transducer, that can express most queries without data-value joins in XML-QL, XSLT, and other XML query languages. Types are modeled by regular tree languages, a robust extension of DTDs. The main result of the paper is that typechecking for k-pebble transducers is decidable. Consequently, typechecking can be performed for a broad range of XML transformation languages, including XML-QL and a fragment of XSLT.
---
paper_title: The Complexity of Compositions of Deterministic Tree Transducers

paper_content:

Macro tree transducers can simulate most models of tree transducers (e.g., top-down and bottom-up tree transducers, attribute grammars, and pebble tree transducers which, in turn, can simulate all known models of XML transformers). The string languages generated by compositions of macro tree transducers (obtained by reading the leaves of the output trees) form a large class which contains, e.g., the IO hierarchy and the EDT0L control hierarchy. Consider an arbitrary composition ? of (deterministic) macro tree transducers. How difficult is it, for a given input tree s, to compute the translation t = ? (s)? It is shown that this problem can be solved (on a RAM) in time linear in the sum of the sizes of s and t. Moreover, the problem to determine, for a given t of size n, whether or not there is an input tree s such that t = ? (s) is in DSPACE(n); this means that output languages of compositions of macro tree transducers are deterministic context-sensitive. The involved technique of compressing intermediate results of the composition, also gives a new proof of the fact that the finiteness problem for ?'s range is decidable.
---
paper_title: Frontiers of tractability for typechecking simple XML transformations

paper_content:

Typechecking consists of statically verifying whether the output of an XML transformation is always conform to an output type for documents satisfying a given input type. We focus on complete algorithms which always produce the correct answer. We consider top-down XML transformations incorporating XPath expressions and abstract document types by grammars and tree automata. By restricting schema languages and transformations, we identify several practical settings for which typechecking can be done in polynomial time. Moreover, the resulting framework provides a rather complete picture as we show that most scenarios cannot be enlarged without rendering the typechecking problem intractable. So, the present research sheds light on when to use fast complete algorithms and when to reside to sound but incomplete ones.
---
paper_title: Conjunctive queries over trees

paper_content:

We study the complexity and expressive power of conjunctive queries over unranked labeled trees represented using a variety of structure relations such as “child”, “descendant”, and “following” as well as unary relations for node labels. We establish a framework for characterizing structures representing trees for which conjunctive queries can be evaluated efficiently. Then we completely chart the tractability frontier of the problem and establish a dichotomy theorem for our axis relations, that is, we find all subset-maximal sets of axes for which query evaluation is in polynomial time and show that for all other cases, query evaluation is NP-complete. All polynomial-time results are obtained immediately using the proof techniques from our framework. Finally, we study the expressiveness of conjunctive queries over trees and show that for each conjunctive query, there is an equivalent acyclic positive query (i.e., a set of acyclic conjunctive queries), but that in general this query is not of polynomial size.
---
paper_title: Expressiveness of structured document query languages based on attribute grammars

paper_content:

Structured document databases can be naturally viewed as derivation trees of a context-free grammar. Under this view, the classical formalism of attribute grammars becomes a formalism for structured document query languages. From this perspective, we study the expressive power of BAGs: Boolean-valued attribute grammars with propositional logic formulas as semantic rules, and RAGs: relation-valued attribute grammars with first-order logic formulas as semantic rules. BAGs can express only unary queries; RAGs can express queries of any arity. We first show that the (unary) queries expressible by BAGs are precisely those definable in monadic second-order logic. We then show that the queries expressible by RAGs are precisely those definable by first-order inductions of linear depth, or, equivalently, those computable in linear time on a parallel machine with polynomially many processors. Further, we show that RAGs that only use synthesized attributes are strictly weaker than RAGs that use both synthesized and inherited attributes. We show that RAGs are more expressive than monadic second-order logic for queries of any arity. Finally, we discuss relational attribute grammars in the context of BAGs and RAGs. We show that in the case of BAGs this does not increase the expressive power, while different semantics for relational RAGs capture the complexity classes NP, coNP and UP ∩ coUP.
---
paper_title: N-ary Queries by Tree Automata

paper_content:

We investigate n-ary node selection queries in trees by successful runs of tree automata. We show that run-based n-ary queries capture MSO, contribute algorithms for enumerating answers of n-ary queries, and study the complexity of the problem. We investigate the subclass of run-based n-ary queries by unambiguous tree automata.
---
paper_title: On diving in trees

paper_content:

The paper is concerned with queries on tree-structured data. It defines fragments of first-order logic (FO) and FO extended by regular expressions along paths. These fragments have the same expressive power as the full logics themselves. On the other hand, they can be evaluated reasonably efficient, even if the formula which represents the query is considered as part of the input.
---
paper_title: Finite state machines for strings over infinite alphabets

paper_content:

Motivated by formal models recently proposed in the context of XML, we study automata and logics on strings over infinite alphabets. These are conservative extensions of classical automata and logics defining the regular languages on finite alphabets. Specifically, we consider register and pebble automata, and extensions of first-order logic and monadic second-order logic. For each type of automaton we consider one-way and two-way variants, as well as deterministic, nondeterministic, and alternating control. We investigate the expressiveness and complexity of the automata and their connection to the logics, as well as standard decision problems. Some of our results answer open questions of Kaminski and Francez on register automata.
---
paper_title: Counting in Trees for Free

paper_content:

It is known that MSO logic for ordered unranked trees is undecidable if Presburger constraints are allowed at children of nodes. We show here that a decidable logic is obtained if we use a modal fixpoint logic instead. We present a characterization of this logic by means of deterministic Presburger tree automata and show how it can be used to express numerical document queries. Surprisingly, the complexity of satisfiability for the extended logic is asymptotically the same as for the original fixpoint logic. The non-emptiness for Presburger tree automata (PTA) is pspace-complete, which is moderate given that it is already pspace-hard to test whether the complement of a regular expression is non-empty. We also identify a subclass of PTAs with a tractable non-emptiness problem. Further, to decide whether a tree t satisfies a formula ϕ is polynomial in the size of ϕ and linear in the size of t.
---
paper_title: On the power of walking for querying tree-structured data

paper_content:

XSLT is the prime example of an XML query language based on tree-walking. Indeed, stripped down, XSLT is just a tree-walking tree-transducer equipped with registers and look-ahead. Motivated by this connection, we want to pinpoint the computational power of devices based on tree-walking. We show that in the absence of unique identifiers even very powerful extensions of the tree-walking paradigm are not relationally complete. That is, these extensions do not capture all of first-order logic. In contrast, when unique identifiers are available, we show that various restrictions allow to capture LOGSPACE, PTIME, PSPACE, and EXPTIME . These complexity classes are defined w.r.t. a Turing machine model working directly on (attributed) trees. When no attributes are present, relational storage does not add power; whether look-ahead adds power is related to the open question whether tree-walking captures the regular tree languages.
---
paper_title: Numerical document queries

paper_content:

A query against a database behind a site like Napster may search, e.g., for all users who have downloaded more jazz titles than pop music titles. In order to express such queries, we extend classical monadic second-order logic by Presburger predicates which pose numerical restrictions on the children (content) of an element node and provide a precise automata-theoretic characterization. While the existential fragment of the resulting logic is decidable, it turns out that satisfiability of the full logic is undecidable. Decidable satisfiability and a querying algorithm even with linear data complexity can be obtained if numerical constraints are only applied to those contents of elements where ordering is irrelevant. Finally, it is sketched how these techniques can be extended also to answer questions like, e.g., whether the total price of the jazz music downloaded so far exceeds a user's budget.
---
paper_title: An Algebraic Approach to Data Languages and Timed Languages

paper_content:

Algebra offers an elegant and powerful approach to understand regular languages and finite automata. Such framework has been notoriously lacking for timed languages and timed automata. We introduce the notion of monoid recognizability for data languages, which includes timed languages as special case, in a way that respects the spirit of the classical situation. We study closure properties and hierarchies in this model and prove that emptiness is decidable under natural hypotheses. Our class of recognizable languages properly includes many families of deterministic timed languages that have been proposed until now, and the same holds for non-deterministic versions.
---
paper_title: Finite-memory automata

paper_content:

A model of computation dealing with infinite alphabets is proposed. The model is based on replacing the equality test by unification. It appears to be a natural generalization of the classical Rabin-Scott finite-state automata and possesses many of their properties. >
---
paper_title: A Transducer-Based XML Query Processor

paper_content:

The XML Stream Machine (XSM) system is a novel XQuery processing paradigm that is tuned to the efficient processing of sequentially accessed XML data (streams). The system compiles a given XQuery into an XSM, which is an XML stream transducer, i.e., an abstract device that takes as input one or more XML data streams and produces one or more output streams, potentially using internal buffers. We present a systematic way to translate XQueries into efficient XSMs: First the XQuery is translated into a network of XSMs that correspond to the basic operators of the XQuery language and exchange streams. The network is reduced to a single XSM by repeated application of an XSM composition operation that is optimized to reduce the number of tests and actions that the XSM performs as well as the number of intermediate buffers that it uses. Finally, the optimized XSM is compiled into a C program. First empirical results illustrate the performance benefits of the XSM-based processor.
---
paper_title: Schema-based Scheduling of Event Processors and Buffer Minimization for Queries on Structured Data Streams

paper_content:

We introduce an extension of the XQuery language, FluX, that supports event-based query processing and the conscious handling of main memory buffers. Purely event-based queries of this language can be executed on streaming XML data in a very direct way. We then develop an algorithm that allows to efficiently rewrite XQueries into the event-based FluX language. This algorithm uses order constraints from a DTD to schedule event handlers and to thus minimize the amount of buffering required for evaluating a query. We discuss the various technical aspects of query optimization and query evaluation within our framework. This is complemented with an experimental evaluation of our approach.
---
paper_title: Automaton meets query algebra: Towards a unified model for XQuery evaluation over XML data streams

paper_content:

In this work, we address the efficient evaluation of XQuery expressions over continuous XML data streams, which is essential for a broad range of applications including monitoring systems and information dissemination systems. While previous work has shown that automata theory is suited for on-the-fly pattern retrieval over XML data streams, we find that automata-based approaches suffer from being not as flexibly optimizable as algebraic query systems. In fact, they enforce a rigid data-driven paradigm of execution. We thus now propose a unified query model to augment automata-style processing with algebra-based query optimization techniques. The proposed model has been successfully applied in the Raindrop stream processing system. Our experimental study confirms considerable performance gains with both established optimization techniques and our novel query rewrite rules.
---
paper_title: Attribute grammars for scalable query processing on XML streams

paper_content:

We introduce the new notion of XML Stream Attribute Grammars (XSAGs). XSAGs are the first scalable query language for XML streams (running strictly in linear time with bounded memory consumption independent of the size of the stream) that allows for actual data transformations rather than just document filtering. XSAGs are also relatively easy to use for humans. Moreover, the XSAG formalism provides a strong intuition for which queries can or cannot be processed scalably on streams. We introduce XSAGs together with the necessary language-theoretic machinery, study their theoretical properties such as their expressiveness and complexity, and discuss their implementation.
---

Title: Automata for XML — A Survey

Section 1: XML Processing Tasks
Description 1: This section describes the various processing tasks related to XML, including the different languages tailored to specific tasks like schema, navigation, query, and transformation languages.

Section 2: XML and Trees
Description 2: This section discusses how XML documents are represented as trees, introducing the concept of unranked trees and various methods like tree representation, terms representation, and binary encoding.

Section 3: Automata
Description 3: This section covers the three main categories of automata for XML processing: parallel tree automata, sequential tree automata, and document automata, including their definitions, expressive power, and complexity.

Section 4: Complexity of Algorithmic Problems Related to Tree Automata
Description 4: This section outlines the complexity of fundamental algorithmic problems such as membership, non-emptiness, containment, and equivalence for different types of tree automata.

Section 5: Related Issues
Description 5: This section delves into related topics like the minimization of automata, the decidability of expressibility in first-order logic, and cascading sequences of automata.

Section 6: Schemas
Description 6: This section examines different classes of schema languages for XML, including DTDs, regular tree languages, and XML Schema, focusing on validation and static analysis complexity.

Section 7: Navigation
Description 7: This section explains the distinction between querying and navigation, discussing regular node-selecting queries, XPath, complexity of navigational queries, and binary queries for stream processing of XML data.

Section 8: Transformations
Description 8: This section surveys various tree transformation languages and models like top-down transducers, pebble transducers, macro tree transducers, and logically defined transducers, along with complexity issues related to XML transformations.

Section 9: Queries
Description 9: This section addresses the foundations of general XML querying, higher-arity queries, the handling of data values and arithmetic, and the evaluation of queries on streaming XML data.

Section 10: Conclusion
Description 10: This section summarizes the importance of automata and formal language theory for XML processing, highlighting the robustness of regular tree languages, node-selecting and binary queries, and open questions regarding their utility for general querying.