Section: Overall Objectives

Highlights of the Year

Our paper `A trichotomy for regular simple path queries on graphs' has been accepted for publication in the Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2013, the top conference in the field of theoretical databases. The paper addresses an open problem, i.e. giving a complete classification of regular languages with respect to regular simple path queries (RSPQs), the latter being regular path queries (RPQs) with an additional constraint that prevents traversing two nodes multiple times. In particular, we have characterized the boundary between tractability and intractability, and proved a trichotomy: the evaluation of RSPQs is either AC0 , NL-complete or NP-complete in data complexity.

Pierre Bourhis has been recruited as CNRS researcher at LIFL and joined the team in October.