Paris ACTS has been created to reinforce the links between different research groups in the Paris area which are working on the connections between automata theory and concurrency theory, and in order to advance this research on a national and international level,
The seminar takes place for an afternoon every six-eight weeks, moving between LIX (École Polytechnique), LRE (EPITA Paris), and IRIF (Université Paris Cité). It is held in hybrid mode and is an evolution of the (i)Po(m)set Project Online Seminar (PPOS). It is inspired by the MeFoSyLoMa seminar, with which it has a slight thematic overlap, but includes a hybrid component.
The seminar has a low-traffic mailing list for announcements etc.
The program for each afternoon is roughly as follows:
| 14:00--14:45 | In-person talk |
| 14:45--15:30 | Virtual talk |
| 15:30--16:00 | Coffee break |
| 16:00--17:00 | Discussion |
Venue: LIX, École polytechnique
Speaker 1: Enzo Erlich, IRIF, Université Paris Cité, France
Title: Expressivity of First Order and Temporal Logics for Pomset Languages
Abstract: TBA
Speaker 2: Masaki Waga, Kyoto University, Japan
Title: Active Learning of Deterministic Timed Automata with Myhill-Nerode Style Characterization
Abstract: We present an algorithm to learn a deterministic timed automaton (DTA) via membership and equivalence queries. Our algorithm is an extension of the L* algorithm with a Myhill-Nerode style characterization of recognizable timed languages, which is the class of timed languages recognizable by DTAs. We first characterize the recognizable timed languages with a Nerode-style congruence. Using it, we give an algorithm with a smart teacher answering symbolic membership queries in addition to membership and equivalence queries. With a symbolic membership query, one can ask the membership of a certain set of timed words at one time. We prove that for any recognizable timed language, our learning algorithm returns a DTA recognizing it. We show how to answer a symbolic membership query with finitely many membership queries. We also show that our learning algorithm requires a polynomial number of queries with a smart teacher and an exponential number of queries with a normal teacher. We applied our algorithm to various benchmarks and confirmed its effectiveness with a normal teacher.