| Links' Seminars and Public Events |   |
Fri, September 10, 2021 10:00 am 11:00 am | Séminaire de Patrick Baillot titre: Type-based complexity analysis in a parallel process calculus Abstract: Some type systems have been designed to analyse statically the time coplexity of functional languages. A natural question is whether this approach can be extended to parallel languages. We address this problem for the Pi-calculus, a paradigmatic calculus for parallel and concurrent computation. In Pi-calculus, processes communicate through channels that can carry values and channel names. We will define notions of sequential and parallel complexity for Pi-calculus, and present a type system that provides an upper bound on the time complexity of processes. This is based on joint work with Alexis Ghyselen (ESOP 2021). Based on: link.springer.com/chap.....9-3_3  |
Fri, July 9, 2021 all day | Seminar - Antonio AL SERHALI 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. |
