Where:

Laboratoire Spécification et Vérification

École Normale Supérieure de Cachan

61, avenue du Président Wilson

94235 Cachan CEDEX

http://www.lsv.ens-cachan.fr

Title:

Quantitative properties of trees. Application to XML query languages.

Description:

 
XML (Extensible Markup Language) is a format recommended by the W3C to describe structured documents. An XML document is represented by a tree whose nodes carry information. Query languages such as XPath are used to perform queries in XML trees, in order to select nodes having certain desired property, and to extract the relevant information. In this framework, queries are Boolean: a node is selected or not by a query. In the same way that MSO properties on words are captured by finite automata, appropriate kinds of automata, walking in the trees along edges [Boj08], can capture properties expressed by query languages [tCS08].

In this internship, we propose to extend Boolean queries to quantitative ones, to express for instance the cost required to answer a query at a given node, or the probability that a node is selected by a query. The quantitative framework is already well developed for word languages. Several logics are designed to express quantitative properties on words [BG09]. The goal of this internship is to

• – find quantitative extensions of query languages, making it easy to express relevant properties,
• – find an equivalent automata model, in order to verify such quantitative properties. A starting question is to find a model of weighted tree walking automata on the semiring ⟨N∪{∞},min,+⟩ to compute the cost of a request.

Contact:

 

Benedikt Bollig, Paul Gastin et Marc Zeitoun

Tél: 01 47 40 - 75 38/75 60/77 87

Email: (bollig|gastin|mz)@lsv.ens-cachan.fr

Web: http://www.lsv.ens-cachan.fr/~(bollig|gastin|zeitoun)

References

[BG09]

Benedikt Bollig and Paul Gastin. Weighted versus probabilistic logics. In DLT'09, volume 5583 of LNCS, pages 18–38, 2009. Springer.
http://www.lsv.ens-cachan.fr/Publis/PAPERS/PDF/BG-dlt09.pdf.

[Boj08]

Mikolaj Bojanczyk. Tree-walking automata. In LATA, pages 1–2, 2008.
http://www.mimuw.edu.pl/~bojan/papers/twasurvey.pdf.

[tCS08]

Balder ten Cate and Luc Segoufin. Xpath, transitive closure logic, and nested tree walking automata. In PODS'08, 2008.
http://www.lsv.ens-cachan.fr/Publis/PAPERS/PDF/tCS-pods08.pdf.

This document was translated from L^AT_EX by H^EV^EA.