Paris Automata and Concurrency Theory Seminar

Venue: LRE, EPITA Paris

Speaker 1: (present) Adrien Pommellet, LRE

Title: Active Learning Techniques for Pomset Recognizers

Abstract: Pomsets are a promising formalism for concurrent programs based on partially ordered sets. Among this class, series-parallel pomsets admit a convenient linear representation and can be recognized by simple algebraic structures known as pomset recognizers. Active learning consists in inferring a formal model of a recognizable language by asking membership and equivalence queries to a minimally adequate teacher (MAT). We improve existing learning algorithms for pomset recognizers by (1) introducing a new counter-example analysis procedure that is in the best case scenario exponentially more efficient than existing methods; (2) adapting the state-of-the-art L^λ algorithm to minimize the impact of exceedingly verbose counter-examples and remove redundant queries; (3) designing a suitable finite test suite that ensures equivalence between two pomset recognizers provided their sizes are close enough by extending the well-known W-method.

Speaker 2: (online) Rajeev Alur, University of Pennsylvania, US

Title: Automata over Series-Parallel Graphs

Abstract: Motivated by distributed data processing applications, we introduce a class of labeled directed acyclic graphs constructed using sequential and parallel composition operations, and study automata and logics over them. We show that deterministic and non-deterministic acceptors over such graphs have the same expressive power, which can be equivalently characterized by Monadic Second-Order logic and the graded μ-calculus. We establish closure under composition operations and decision procedures for membership, emptiness, and inclusion.
A key feature of our graphs, called synchronized series-parallel graphs (SSPG), is that parallel composition introduces a synchronization edge from the newly introduced source vertex to the sink. The transfer of information enabled by such edges is crucial to the determinization construction, which would not be possible for the traditional definition of series-parallel graphs. SSPGs allow both ordered ranked parallelism and unordered unranked parallelism. The latter feature means that in the corresponding automata, the transition function needs to account for an arbitrary number of predecessors by counting each type of state only up to a specified constant, thus leading to a notion of counting complexity that is distinct from the classical notion of state complexity. The determinization construction translates a nondeterministic automaton with n states and k counting complexity to a deterministic automaton with 2ⁿ² states and kn counting complexity, and both these bounds are shown to be tight. Furthermore, for nondeterministic automata a bound of 2 on counting complexity suffices without loss of expressiveness.