In recent years, many different methods for identifying hybrid automata from data have been proposed. However, most of these methods consider clean simulator data, and consequently do not perform well for noisy data measured from real systems. We address this shortcoming with a new approach for the identification of hybrid automata that is specifically designed to be robust to noise. In particular, we propose a new high-level strategy consisting of the following three steps: clustering based on the dynamics identified from a local dataset, state space partitioning using decision trees, and conversion of the decision tree to a hybrid automaton. In addition, we introduce several new concepts for the realization of the single steps. For example, we propose an automated regularization of the dynamic models used for clustering via rank adaption, as well as a new variant of the Gini impurity index for decision tree learning, tailored toward hybrid systems where different dynamics can be active within the same state space region. As our experiments on 19 challenging benchmarks with different characteristics demonstrate, in addition to being robust to both process and measurement noise, our approach avoids the need for extensive hyper-parameter tuning and also performs well for clean data without noise.

In this talk, we present exact characterizations of the functions that are computable in anonymous networks with varying assumptions in the degree of awareness or control that agents have over their outneighbors. First, we characterize the computable functions in the “blind broadcast” model, i.e., when agents have no information on their outgoing neighborhoods. Then we enrich this communication model with either output port awareness, bidirectional channels, or outdegree awareness: In each case, we prove that a function can be computed if and only it is frequency-based, namely, its value only depends on the frequencies of the different input values. This characterization holds for both exact and approximate computability. If one or several nodes are distinguished as leaders, or if the cardinality of the network is known, then under any of the above three assumptions it becomes possible to compute any symmetric function.

Noticing the similarity between the monotone weak distributive laws combining two layers of non-determinism in sets and in compact Hausdorff spaces, we study whether the latter law can be obtained automatically as a weak lifting of the former. This holds partially, but does not generalize to other categories of algebras: we then characterize when exactly monotone weak distributive laws over powerset monads in categories of algebras exist, exhibiting a law combining probabilities and non-determinism in compact Hausdorff spaces and showing on the other hand that such laws do not exist in a lot of other cases.

Consider the classical middle third Cantor set. This is a self-similar set containing all the numbers in the unit interval which have a ternary expansion that avoids the digit 1. We can ask when the intersection of the Cantor set with a translate of itself is also self-similar. Sufficient and necessary conditions were given by Deng, He, and Wen in 2008. This question has also been generalized to classes of subsets of the unit interval. I plan to discuss how existing ideas can be used to address the question for certain self-similar sets with dimension greater than one. These ideas will be illustrated using a class of self-similar sets in the plane that can be realized as radix expansions in base $-n+i$ where $n$ is a positive integer. I will also discuss a property of the fractal dimensions of these kinds of intersections.

In 1963, Paul Cohen discovered the forcing method and definitively answered the first of Hilbert's 23 problems by using this technique to prove the independence of the Continuum Hypothesis from the ZFC axioms. Since then, forcing has become the primary tool in set theory for establishing independence and consistency results. In this talk, we will present the key ingredients and ideas necessary to understand Cohen's model of ZFC + ¬CH. In particular, we will explore Cohen's forcing via the boolean-valued models approach.

Combinatorial automata theory can be seen as studying reachability in transformation semigroups. An interesting way of generalising this setting is by lifting it up to reachability in finite semigroups of rational matrices. Here, besides finite automata theory, other areas come into play, for example weighted automata, algebraic number theory, and multilinear algebra. I will explain several nice questions (such as mortality and minimum rank) that transfer from transformation semigroups to finite matrix semigroups. I will also explain the lack of mathematical structure that is brought by certain PSPACE-complete transformation semigroup problems.

This research aims to connect two important areas: parameterized complexity and multi-objective optimization. Parameterized complexity is a way of studying how efficiently an algorithm can solve a problem by focusing on given parameters, while multi-objective optimization focuses on real-world problems that have several goals to achieve at once. The Multi-Objective Traveling Salesman Problem (MOTSP) is a variation of the Traveling Sales-man Problem (TSP) where a salesman must visit a set of cities and return to the starting point, but instead of optimizing just one objective (like minimizing distance), there are multiple objectives to consider simultaneously. These objectives could be things like minimizing total cost, distance, or travel time, while also considering factors like fuel consumption or safety. We aim to solve MOTSP using a local search method. To enhance the effectiveness of this approach, we have proposed a new neighborhood operator. The Local MOTSP(r-swap) problem takes as input an H-ordered graph G = (V, E), two edge weight functions w1, w2 with maximum weight W, and a positive integer k. The goal is to determine whether there exists an ordered sequence S of at most k r-swaps such that perm(S) results in an improved Hamiltonian cycle. The problem is parameterized by r, k and W. We show that even with multiple objectives, the problem can still be solved in FPT time, specifically in time O(k2·k!·r2(k−1)·n + k5·r ·W4·n2).

I will try to convince you type checkers can be seen as logic programs with ‘directions’, and doing type checking correspond to proof reductions in classical linear logic. This gives us implementations of type checking algorithms for free, by writing bidirectional typing rules as directional logic programs. If time permits, I will tell you some categorical details, or possible extensions to accommodate more expressive type systems. Based on joint work with Vikraman Choudhury and Neel Krishnaswami.

In collaboration with the logic group of the math department (IMJ-PRG), PPS pole is organizing a meeting:

• Logique à Paris
• 26 - 28 February 2025
• Amphi Turing, Sophie Germain
• https://www.sylvyanscombe.com/logiqueaparis2025.html

Talks are given by six invited speakers on various current topics in logic, which in several cases include interactions with the foundations of computer science: Albert Atserias, Ingo Blechschmidt, Laura Fontanella, Jonathan Kirby, Chris Lambie-Hanson, Mariana Vicaria.

Each speaker will give two hours of lectures; typically, the first lecture gives a broad introduction to their domain, followed by a more in-depth talk on a recent topic.

If you would like to attend one or more of the talks, we kindly request that you register via the link above.