Regular expression types for XML
Authors:
Open Access
- 1 January 2005
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Programming Languages and Systems
- Vol. 27 (1) , 46-90
Abstract
We propose regular expression types as a foundation for statically typed XML processing languages. Regular expression types, like most schema languages for XML, introduce regular expression notations such as repetition (*), alternation (|), etc., to describe XML documents. The novelty of our type system is a semantic presentation of subtyping, as inclusion between the sets of documents denoted by two types. We give several examples illustrating the usefulness of this form of subtyping in XML processing.The decision problem for the subtype relation reduces to the inclusion problem between tree automata, which is known to be EXPTIME-complete. To avoid this high complexity in typical cases, we develop a practical algorithm that, unlike classical algorithms based on determinization of tree automata, checks the inclusion relation by a top-down traversal of the original type expressions. The main advantage of this algorithm is that it can exploit the property that type expressions being compared often share portions of their representations. Our algorithm is a variant of Aiken and Murphy's set-inclusion constraint solver, to which are added several new implementation techniques, correctness proofs, and preliminary performance measurements on some small programs in the domain of typed XML processing.Keywords
This publication has 17 references indexed in Scilit:
- Regular expression pattern matching for XML2001
- DSD2000
- Set Constraints and AutomataInformation and Computation, 1999
- Using YAT to Build a Web ServerLecture Notes in Computer Science, 1999
- Adding structure to unstructured data1997
- Using multiset discrimination to solve language processing problems without hashingTheoretical Computer Science, 1995
- Subtyping with union types, intersection types and recursive typesLecture Notes in Computer Science, 1994
- Subtyping recursive typesACM Transactions on Programming Languages and Systems, 1993
- Deciding Equivalence of Finite Tree AutomataSIAM Journal on Computing, 1990
- Derivatives of Regular ExpressionsJournal of the ACM, 1964