Seminars

Title: Integrating Schema-Based Cleaning into Automata Determinization

Abstract : Schema-based cleaning for automata on trees or nested words
was proposed recently to compute smaller deterministic automata for
regular path queries on data trees. The idea is to remove all rules and
states, from an automaton for the query, that are not needed to recognize
any tree recognized by a given schema automaton. Unfortunately, how-
ever, deterministic automata for nested words may still grow large for au-
tomata for XPath queries, so that the much smaller schema-cleaned ver-
sion cannot always be computed in practice. We therefore propose a new
schema-based determinization algorithm that integrates schema-based
cleaning directly. We prove that schema-based determinization always
produces the same deterministic automaton as schema-based cleaning
after standard determinization. Nevertheless, the worst-case complex-
ity is considerably lower for schema-based determinization. Experiments
confirm the relevance of this result in practice.