Thomas Schwentick
ABSTRACT
Formal languages play an important role for many aspects of XML processing. This is obvious for type specifications (as DTD) which use context-free grammars and for navigation in documents (as in XPath) which is based on regular expressions. But the investigation of query, typing, navigation and transformation languages for XML has used many more concepts from Formal Language Theory, in particular many different kinds of string and tree automata.The close connection between automata and logics helps to allow a declarative specification of queries and transformations that can be evaluated or performed by tree automata. This connection also facilitates the investigation of the expressive power of query and transformation languages. Furthermore, in many cases automata characterizations enable static analysis like containment and satisfiability tests for queries or type checking for transformations.The tutorial will give a gentle introduction into the connections between XML languages and various kinds of automata and it will survey some classical and recent results in this area.
Recommendations
Visibly pushdown automata for streaming XML
WWW '07: Proceedings of the 16th international conference on World Wide WebWe propose the study of visibly pushdown automata (VPA) for processing XML documents. VPAs are pushdown automata where the input determines the stack operation, and XML documents are naturally visibly pushdown with the VPA pushing onto the stack on open-...
On the minimization of XML Schemas and tree automata for unranked trees
Automata for unranked trees form a foundation for XML Schemas, querying and pattern languages. We study the problem of efficiently minimizing such automata. First, we study unranked tree automata that are standard in database theory, assuming bottom-up ...
Automata on Infinite Trees with Equality and Disequality Constraints Between Siblings
LICS '16: Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer ScienceThis article is inspired by two works from the early 90s. The first one is by Bogaert and Tison who considered a model of automata on finite ranked trees where one can check equality and disequality constraints between direct subtrees: they proved that ...
Comments