~~NOCACHE~~
/* DO NOT EDIT THIS FILE             */

[[seminaires:automates:index|Automates]]\\
Vendredi 13 décembre 2024, 14 heures, Salle 3052\\
**Vincent Michielini** (University of Warsaw) //Complexity of query entailment for description logic with transitive roles//
<button type="link" size="xs" collapse="b5-1017">{{icon>info-circle?lg&color=#777}}</button>\\
<collapse id="b5-1017" collapsed="true">
<well size="sm">
In description logic, the query entailment problem asks the following question: given an ABox A (i.e. basic finite structure, to be completed), an ontology T (or a TBox, a finite set of constrains), and a request q (= a conjunctive query, = a subgraph), does any structure satisfying the ABox and the ontology necessarily also satisfy the request? In ALC, the basic description logic (which is nothing more than modal logic in disguise), this problem is well understood, as it is known to be ExpTime-complete in combined complexity, and coNP-complete in data complexity (i.e. with TBox and query fixed) [Lutz '08].

However, the exact complexity for S, the extension of ALC where some roles (= binary relations) are specified to be transitive, was not known yet. The status being that the problem is coNExpTime-hard [Eiter et al. '09] and in 2ExpTime [Calvanese et al. '98]. An article of 2010 tried to close the gap in a special case, but sadly contains a technical mistake, which could not be repaired so far [personal communication].

In this seminar, we propose an alternative solution to the problem, that even works in the most general case: we prove that if the entailment does not hold, then there exists a counter-model admitting a representation of exponential size (although being most possibly infinite). Hence, we conclude that the query entailment for S is indeed coNExpTime-complete. The construction of such a counter-model elegantly implies a variant of automata over infinite trees.
</well>
</collapse>


[[seminaires:automates:index|Automates]]\\
Vendredi 29 novembre 2024, 14 heures, Salle 3052\\
**Antonio Casares** (University of Warsaw) //Canonical models in automata theory//
<button type="link" size="xs" collapse="b5-1018">{{icon>info-circle?lg&color=#777}}</button>\\
<collapse id="b5-1018" collapsed="true">
<well size="sm">
Abstract: Automata over finite words are amazing (no need to justify this in the automata seminar). A central reason for their amazingness is the existence of canonical models, which allows for efficient minimization and learning algorithms, as well as for plenty of other theoretical applications. Automata have been extended to operate over richer classes of structures (such as infinite words, trees and graphs), and to define functions using various forms of transducers. However, the theory of these more general automata is often limited, due to the absence of canonical models. In this talk, I will present the subject of my CNRS project: Identifying canonical models for automata over richer classes of structures, with a special focus on automata over infinite words.
</well>
</collapse>


[[seminaires:automates:index|Automates]]\\
Vendredi 22 novembre 2024, 14 heures, Salle 3052\\
**Pierre Letouzey** (IRIF) //Generalizing some Hofstadter functions: G, H and beyond//
<button type="link" size="xs" collapse="b5-1019">{{icon>info-circle?lg&color=#777}}</button>\\
<collapse id="b5-1019" collapsed="true">
<well size="sm">
Joint work with Shuo Li (U. Winnipeg) and Wolfgang Steiner (IRIF)

Hofstadter's G function is recursively defined via $G(0)=0$ and then
$G(n)=n-G(G(n-1))$. Following Hofstadter, a family $(F_k)$ of similar
functions is obtained by varying the number $k$ of nested recursive
calls in this equation. We present here a few nice properties of these
functions. In particular, they can be described via some infinite
morphic words generalizing the Fibonacci word. This was crucial for
proving that this family is ordered pointwise: for all $k$ and $n$,
$F_k(n) \le F_{k+1}(n)$. Moreover, these functions have a simple behavior on well-chosen numerical representations (Zeckendorf
decompositions for some Fibonacci-like sequences). Thanks to that,
we were also able to estimate the discrepancies for these $F_k$, i.e. the maximal distances between each $F_k$ and its linear equivalent.
This whole work was formally proved using the Coq proof assistant
(except for a beautiful fractal!) and we will give a gentle
introduction to this Coq development.
</well>
</collapse>


[[seminaires:automates:index|Automates]]\\
Vendredi 15 novembre 2024, 14 heures, Salle 3052\\
**Luc Dartois** (LACL) //Reversible Transducers over Infinite Words//
<button type="link" size="xs" collapse="b5-1020">{{icon>info-circle?lg&color=#777}}</button>\\
<collapse id="b5-1020" collapsed="true">
<well size="sm">
Deterministic two-way transducers capture the class of regular functions. The efficiency of composing two-way transducers has a direct implication in algorithmic problems related to  synthesis, where transformation specifications are converted into equivalent transducers. These specifications are presented in a modular way, and composing the resultant machines simulates the full specification.
In this talk, I will present how we can achieve efficient composition of two-way transducers, mainly through the use of Reversible Transducers. Reversible machines are machine that are both deterministic and codeterministic.
I will show how any two-way transducers can be made reversible, while being easily composable. I will also show how these results can be extended to the setting of infinite words, which is the dedicated setting for model-checking for example.
</well>
</collapse>


[[seminaires:automates:index|Automates]]\\
Vendredi 8 novembre 2024, 14 heures, Salle 3071\\
**Benjamin Bordais** (TU Dortmund) //How to generalize turn-based games into well-behaving concurrent games//
<button type="link" size="xs" collapse="b5-1021">{{icon>info-circle?lg&color=#777}}</button>\\
<collapse id="b5-1021" collapsed="true">
<well size="sm">
We investigate two-player win/lose games over finite graphs. In all generality, these games are concurrent, i.e. at each state of the graph, there is a concurrent interaction between the two players to determine the next state visited. In the special case where, at every state of the graph, there are no real concurrent interaction, i.e. only one player is truly playing, the game is turn-based. Various desirable properties hold on turn-based games, but do not on arbitrary concurrent games; e.g. there exist subgame optimal strategies in all prefix-independent turn-based games, while there do not in very simple prefix-independent concurrent games. A possible way to circumvent this issue is to define a subclass of concurrent games, that is a proper superclass of turn-based games, while enjoying several of their nice properties. The goal of this talk is to introduce such a subclass of concurrent games, namely finitely maximizable games, and to show step by step how we came up with this definition. The novel way that we use to define such a subclass of well-behaving concurrent games constitutes a promising approach for investigating more general concurrent games, such as non-antagonistic two-player games, or even multi-player games.
</well>
</collapse>


[[seminaires:automates:index|Automates]]\\
Vendredi 25 octobre 2024, 14 heures, Salle 3052\\
**Isa Vialard**  //Measuring well quasi-orders//
<button type="link" size="xs" collapse="b5-1022">{{icon>info-circle?lg&color=#777}}</button>\\
<collapse id="b5-1022" collapsed="true">
<well size="sm">
Well quasi orderings (WQOs) are at the heart of the theory of Well-Structured Systems (WSTS), a class of computational models that brought numerous important advances for the automatic verification of infinite-state systems. Recent developments in this field links the complexity of WQO-based algorithms to ordinal measures of WQOs : the maximal order type, ordinal height and ordinal width.

One main challenge is to compute the ordinal invariants of complex well quasi-orders built from simpler well quasi-orders through classical operation, such as the Cartesian product, and high-order constructions, like the finite words embedding. In my thesis, I computed compositionally the maximal order type of the direct product, the width of the multiset embedding, and the height and width of the multiset ordering. Furthermore, I compute the width of the Cartesian product in restricted cases and studied the ordinal measures of the finite powerset.In the process, I developed several tools and techniques, notably a game-theoretical approach to computing width using the notion of quasi-incomparable families of subsets. To tackle the width of the multiset ordering, I introduced and studied a fourth ordinal invariant, the friendly order type.
</well>
</collapse>


[[seminaires:automates:index|Automates]]\\
Vendredi 18 octobre 2024, 14 heures, Salle 3071\\
**Fabian Reiter** (LIGM) //Locality via Alternation?//
<button type="link" size="xs" collapse="b5-1023">{{icon>info-circle?lg&color=#777}}</button>\\
<collapse id="b5-1023" collapsed="true">
<well size="sm">
In this talk, I will show how logic and automata theory can help research in distributed computing.

I will start with an attempt to use logic to extend standard complexity theory to the distributed setting. It turns out that several classical concepts generalize well, including the polynomial hierarchy (and hence the complexity classes P and NP), the Cook-Levin theorem (which identifies Boolean satisfiability as a complete problem for NP), and Fagin's theorem (which characterizes NP as the problems expressible in existential second-order logic). But perhaps more surprisingly, separating complexity classes becomes easier in the general case: when extended to multiple computers, the polynomial hierarchy is provably infinite, while it remains notoriously open whether the same holds in the case of a single computer.

In the second part of the talk, I will use the previous results to address a central question in distributed computing: which problems are purely local, which problems are inherently global, and which problems lie between these extremes? The idea will be to measure locality using quantifier alternation, the key concept underlying the polynomial hierarchy.

The talk is based on my paper “A LOCAL View of the Polynomial Hierarchy”.
- Proceedings version: https://doi.org/10.1145/3662158.3662774
- Full version: https://arxiv.org/abs/2305.09538
</well>
</collapse>


[[seminaires:automates:index|Automates]]\\
Vendredi 11 octobre 2024, 14 heures, Salle 3052\\
**Mihir Vahanwala** (MPI-SWS, Saarbrücken) //On the Monadic Second-Order Theory of Arithmetic Predicates//
<button type="link" size="xs" collapse="b5-1024">{{icon>info-circle?lg&color=#777}}</button>\\
<collapse id="b5-1024" collapsed="true">
<well size="sm">
Büchi's seminal 1962 paper established the decidability of the monadic second-order (MSO) theory of the structure (Nat; <), and in so doing brought to light the profound connections between mathematical logic and automata theory. This talk presents our recent results on the decidability of expansions (Nat; <, P1, ..., Pd) for various unary predicates P1, ..., Pd. We focus in particular on predicates of arithmetic origin, such as Pow-k (powers of k) and N-k (k-th powers). The following is a representative sample of the results yielded by our techniques, which combine automata theory, algebra, number theory, dynamical systems, and combinatorics:

- The MSO theory of (Nat; <, Pow-2, Pow-3) is decidable.

- The MSO theory of (Nat; <, Pow-2, Pow-3, Pow-6) is decidable.

- The MSO theory of (Nat; <, Pow-2, Pow-3, Pow-5) is decidable subject to Schanuel's conjecture.

- The MSO theory of (Nat; <, Squares, Pow-4) is decidable.

- The MSO theory of (Nat; <; Squares, Pow-2) is Turing-equivalent to the MSO theory of (Nat; <, S), where S is the unary predicate corresponding to the binary expansion of s = sqrt(2). As s is widely believed to be a weakly normal number, the corresponding MSO theory is in turn expected to be decidable.

The talk will give an overview of our techniques in general, and the automata theory and algebra that enable the above results in particular.
</well>
</collapse>


[[seminaires:automates:index|Automates]]\\
Mercredi 10 juillet 2024, 14 heures, Salle 3052\\
**Martin Zimmermann**  //History-deterministic Pushdown Automata//
<button type="link" size="xs" collapse="b5-1025">{{icon>info-circle?lg&color=#777}}</button>\\
<collapse id="b5-1025" collapsed="true">
<well size="sm">
Deterministic automata are often less expressive or at least less succinct than nondeterministic ones, but offer often better algorithmic and closure properties. History-determinism, a limited form of nondeterminism constitutes an appealing middle ground as history-deterministic automata often combine the best of both worlds, e.g., increased expressiveness in comparison to deterministic automata and better algorithmic and closure properties than fully nondeterministic ones.

History-deterministic pushdown automata live up to that promise: their expressiveness lies strictly between that of deterministic and nondeterministic automata while solving games with history-deterministic winning conditions is EXPTIME-complete, while it is undecidable for nondeterministic pushdown automata. 

But where there is light, there must be shadow: history-deterministic pushdown automata have poor closure properties and checking whether a pushdown automaton is history-deterministic is undecidable. 

To end on a high note, we present several open problems related to history-deterministic pushdown automata.

Based on joint work with Ismaël Jecker, Shibashis Guha and Karoliina Lehtinen.
</well>
</collapse>


[[seminaires:automates:index|Automates]]\\
Vendredi 28 juin 2024, 14 heures, Salle 3052\\
**Lucas Larroque**  //Normalisations of Existential Rules: Not so Innocuous!//
<button type="link" size="xs" collapse="b5-1026">{{icon>info-circle?lg&color=#777}}</button>\\
<collapse id="b5-1026" collapsed="true">
<well size="sm">
Querying data sometimes calls for a logical layer between the user and the data to solve issues that arise with distributed datasets, overspecific vocabulary or incompleteness. Existential rules are an expressive knowledge representation language used for this purpose. In the literature, they are often supposed to be in some normal form that simplifies technical developments. Such assumptions are considered to be made without loss of generality as long as all sets of rules can be normalised while preserving entailment. However, an important question is whether the properties that ensure the decidability of reasoning are preserved as well.
In this talk, I will start with presenting the chase algorithm, which is used to query data in the presence of existential rules. I will then discuss the impact of a normalisation procedure called atomic decomposition over termination of the chase. This discussion will lead me to present other results related to chase termination of (not so) independent interest.
</well>
</collapse>


[[seminaires:automates:index|Automates]]\\
Vendredi 21 juin 2024, 14 heures, 3052\\
**Marc Zeitoun**  //Nested temporal hierarchies of regular languages//
<button type="link" size="xs" collapse="b5-1027">{{icon>info-circle?lg&color=#777}}</button>\\
<collapse id="b5-1027" collapsed="true">
<well size="sm">
In this talk, we focus on unary temporal logic over words (UTL). It is known that languages definable in this logic have several equivalent characterizations based on different formalisms. Additionally, it is known that one can decide whether a regular language can be expressed in UTL.

First, I will present these various characterizations. Then, I will introduce a general approach that encompasses all known results and allows us to obtain new ones. This approach relies on the use of an "operator" whose repeated application yields a hierarchy of classes of regular languages. Finally, I will present some results about this new hierarchy, in particular its relationship with the so-called concatenation hierarchy. This is joint work with Thomas Place.
</well>
</collapse>


[[seminaires:automates:index|Automates]]\\
Vendredi 14 juin 2024, 14 heures, Salle 3052\\
**Sylvain Schmitz**  //On the Length of Strongly Monotone Descending Chains over ℕᵈ//
<button type="link" size="xs" collapse="b5-1028">{{icon>info-circle?lg&color=#777}}</button>\\
<collapse id="b5-1028" collapsed="true">
<well size="sm">
I will present the main results of this joint work with Lia Schütze, available online from arXiv (https://arxiv.org/abs/2310.02847), starting with Rackoff's 1978 upper bound for the coverability problem in vector addition systems, followed by the 2013 breakthrough by Künnemann, Mazowiecki, Schütze, Sinclair-Banks, and Wegrzycki on this upper bound, and finally presenting the `ideal' viewpoint on these results and its consequences for various extensions of vector addition systems.
</well>
</collapse>


[[seminaires:automates:index|Automates]]\\
Vendredi 7 juin 2024, 14 heures, Zoom (+ Salle 3052)\\
**Lê Thành Dũng (Tito) Nguyễn**  //Computing the polynomial degree of size-to-height increase for macro tree transducers//
<button type="link" size="xs" collapse="b5-1029">{{icon>info-circle?lg&color=#777}}</button>\\
<collapse id="b5-1029" collapsed="true">
<well size="sm">
In a paper to appear at ICALP'24 [*], Gallot, Maneth, Nakano and Peyrat show that, given a tree-to-tree function f computed by a macro tree transducer (a natural register-based machine model, which will be recalled in the talk), the following problems are decidable:
(1) is height(f(t)) = O(height(t)) ?
(2) is height(f(t)) = O(size(t)) ?
We sketch a tentative proof of a generalization of (2) by different and arguably simpler means. More precisely, we show that the quantity
inf {k | height(f(t)) = O(size(t)^k)} ∈ ℕ∪{+∞}
is computable by reduction to ambiguity of (ordinary) tree automata. (Joint work with Paul Gallot and Nathan Lhote, in preparation.)
[*] https://arxiv.org/abs/2307.16500
</well>
</collapse>


[[seminaires:automates:index|Automates]]\\
Vendredi 31 mai 2024, 14 heures, Salle 3052\\
**Thomas Colcombet**  //Bisimulation invariant MSO over finite transition systems//
<button type="link" size="xs" collapse="b5-1030">{{icon>info-circle?lg&color=#777}}</button>\\
<collapse id="b5-1030" collapsed="true">
<well size="sm">
In this talk, I will present a recent result obtained in collaboration with Amina Doumane and Denis Kuperberg on the properties definable in MSO which are bisimulation invariant over finite transition systems. We show that these coincide with mu-calculus-definable properties. This is a variant of a result from Janin and Walukiewicz over general (ie possibly infinite) transition systems [JW96].

Our proof techniques involve developing an algebraic theory of infinite regular trees, in particular establishing on the way that recognizable languages of regular trees coincide (over regular trees) with MSO definable language of trees.
</well>
</collapse>


[[seminaires:automates:index|Automates]]\\
Vendredi 24 mai 2024, 14 heures, Salle 3052\\
**Sreejith A V**  //Decomposition results for algebras that recognize countable words//
<button type="link" size="xs" collapse="b5-1031">{{icon>info-circle?lg&color=#777}}</button>\\
<collapse id="b5-1031" collapsed="true">
<well size="sm">
In this talk, we look at the refined understanding of language-logic-algebra inter-play in an algebraic framework (called o-monoids) over countable words. We develop a seamless integration of the block product operation in the countable setting, and generalize well-known decompositional characterizations of FO and some fragments and extensions. We also show that aperiodic o-monoids cannot be
decomposed using a finite-basis.
</well>
</collapse>


[[seminaires:automates:index|Automates]]\\
Vendredi 17 mai 2024, 14 heures, Salle 3052\\
**Laure Daviaud**  //Weighted automata: a la carte!//
<button type="link" size="xs" collapse="b5-1032">{{icon>info-circle?lg&color=#777}}</button>\\
<collapse id="b5-1032" collapsed="true">
<well size="sm">
I will first give a quick overview of decidability problems for weighted automata. Then, up to you!
I can talk about any of the following topics, we'll vote!
- decidability of the Big-O problem for max-plus automata
- the many undecidability results via the halting problems of two-counter machines
- learnability of weighted automata
</well>
</collapse>


[[seminaires:automates:index|Automates]]\\
Vendredi 19 avril 2024, 14 heures, Salle 3052\\
**Florent Capelli**  //Direct Access For Conjunctive Queries with Negation//
<button type="link" size="xs" collapse="b5-1033">{{icon>info-circle?lg&color=#777}}</button>\\
<collapse id="b5-1033" collapsed="true">
<well size="sm">
Direct Access is the operation of returning, given an index j, the j-th answer of a conjunctive query Q on a given database for some given order on the answers set of Q. While this problem is #P-hard in general (wrt combined complexity), many conjunctive queries are structured enough so that for some lexicographical ordering of their answers, one can have a direct access to the answer of Q that takes polylogarithmic time in the size of the database after polynomial time precomputation. Previous work have precisely characterized the tractable classes and given fine grained lower bounds on the time needed for precomputation depending on the structure of the query. We give a generalization of these tractability results to the case of signed conjunctive queries, that is, conjunctive queries that may contain negative atoms. Our technique is based on solving the ranked access for a class of circuits that can represent relational data. Our result then follows from the fact that the tractable (signed) conjunctive queries can be transformed into polynomial size circuit. We recover the known tractable classes from the literature in the case of positive conjunctive queries using this technique and also discover new island of tractability for signed conjunctive queries. In particular, our result generalizes to the Ranked Access Problem the known tractabilities of counting the number of answers to beta-acyclic negative queries and of deciding whether a negative query with bounded nested-width has an answer. This is join work with Oliver Irwin and appeared at ICDT 2024:

- ArXiv version: https://arxiv.org/abs/2310.15800
- Published version: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2024.13
</well>
</collapse>


[[seminaires:automates:index|Automates]]\\
Vendredi 12 avril 2024, 14 heures, Salle 3052\\
**Guillaume Lagarde**  //The complexity of learning temporal formulas from examples//
<button type="link" size="xs" collapse="b5-1034">{{icon>info-circle?lg&color=#777}}</button>\\
<collapse id="b5-1034" collapsed="true">
<well size="sm">
In this talk we are interested in the problem of learning linear temporal logic (over finite traces, LTL_f) formulas from examples, as a first step towards expressing a property separating positive and negative instances in a way that is comprehensible for humans. We initiate the study of the computational complexity of the problem. Our main results are hardness results: we show that the LTL_f learning problem is NP-complete for almost all of its fragments, but also hard to approximate within a o(log n) factor in some cases. This motivates the search for efficient heuristics, and highlights the complexity of expressing separating properties in concise natural language.
</well>
</collapse>


[[seminaires:automates:index|Automates]]\\
Vendredi 29 mars 2024, 14 heures, Salle 3052\\
**Leonid Libkin**  //Embedded finite models and finitely representable databases: a forgotten area ready for a comeback//
<button type="link" size="xs" collapse="b5-1035">{{icon>info-circle?lg&color=#777}}</button>\\
<collapse id="b5-1035" collapsed="true">
<well size="sm">
A question was asked 35 years: can we store an infinite set in a database? Turns out the answer is yes, and for this a set has to be finitely representable. In databases we use logic for querying, and thus finitely represent sets by logical formulas over infinite models. The next question was: what can you ask about such databases? To answer this question we had to go back to the finite world, and thus embedded finite models were born, a mix of finite and the infinite. While theoreticians were happy to talk about AC0 and o-minimality, cell decomposition, and local triviality in the same paper, practitioners asked whether something useful can be built based on these ideas. The 1990s answer was no, computers were too slow, solvers were too immature. But the world doesn’t stand still, and we have witnessed signs of rebirth of this area that at the very least gave us theoreticians lots of fun. In the talk I’ll tell this story and share some thoughts on making finitely representable databases great again.
</well>
</collapse>


[[seminaires:automates:index|Automates]]\\
Vendredi 22 mars 2024, 14 heures, Salle 3052\\
**Quentin Aristote**  //Active Learning of Deterministic Transducers with Outputs in Arbitrary Monoids//
<button type="link" size="xs" collapse="b5-1036">{{icon>info-circle?lg&color=#777}}</button>\\
<collapse id="b5-1036" collapsed="true">
<well size="sm">
We study monoidal transducers, transition systems arising as deterministic automata whose transitions also produce outputs in an arbitrary monoid, for instance allowing outputs to commute or to cancel out.
In a first part I'll explain how Vilar's algorithm for the active learning à la Angluin of (normal) transducers generalize to monoidal transducers. In a second part I'll then discuss how this is an instance of the categorical framework for minimization and learning of Colcombet, Petrişan and Stabile: the active learning algorithm was obtained by instantiating monoidal transducers in this framework.
</well>
</collapse>


[[seminaires:automates:index|Automates]]\\
Vendredi 8 mars 2024, 14 heures, Salle 3052\\
**Rémi Morvan** (LaBRI) //Automatic relations through the prism of graph colourability and algebraic language theory//
<button type="link" size="xs" collapse="b5-1037">{{icon>info-circle?lg&color=#777}}</button>\\
<collapse id="b5-1037" collapsed="true">
<well size="sm">
This talk focuses on **automatic (aka synchronous)** relations, defined as the binary relations of finite words that can be recognized by finite-state synchronous automata. We study two orthogonal approaches.


**- Graph theoretic properties:** we show that given an automatic graph (a graph defined by an automatic relation), the problem of whether the graph can be **regularly 2-coloured** (meaning that it can be 2-coloured, and for every colour, the set of words having this colour is a regular language) is surprisingly undecidable; this results yields the undecidability of the **separation problem of automatic relations** by a subclass of recognizable relations.

**- Language-theoretic properties:** on the contrary, we show that most of the reasonable language-theoretic properties of automatic relations are decidable. We develop an **algebraic theory for automatic relations**, called "synchronous algebras", which are to relations as monoids are to languages. The three pillars of algebraic language theory hold in our settings, namely (1) all relations admit a syntactic synchronous algebra, which is finite if and only if the relation is automatic, (2) classes of automatic relations with nice closure properties (called pseudovarieties) are in natural correspondence with pseudovarieties of finite synchronous algebras and (3) the latter are exactly the classes of finite synchronous algebras which can be described by "profinite dependencies", a generalization of classical profinite equations. Building on these results, we show how algebraic characterizations of pseudovarieties of regular languages can be lifted to the pseudovarieties of synchronous relations that they induce.

The graph-colourability part the talk is based on a joint work with Pablo Barceló and Diego Figueira published at MFCS '23.
</well>
</collapse>


[[seminaires:automates:index|Automates]]\\
Lundi 4 mars 2024, 16 heures, Salle 3052\\
**Yann Strozecki** (DAVID, UVSQ) //A tutorial on enumeration complexity: defining tractability//
<button type="link" size="xs" collapse="b5-1038">{{icon>info-circle?lg&color=#777}}</button>\\
<collapse id="b5-1038" collapsed="true">
<well size="sm">
We review the different ways tractability is defined in enumeration using as complexity measure total time, incremental time, delay and space. We present the associated complexity classes, typical problems and algorithmic methods. 

The focus is on understanding incremental polynomial time and polynomial delay which are the classes containing most problems. In particular we present an attempt to classify which saturation problems naturally in incremental polynomial time are in fact in polynomial delay and give separation and collapses for general classes. We also briefly present low complexity classes and way to completely avoid exhaustive enumeration, through compact representation and approximation of the solution set.
</well>
</collapse>


[[seminaires:automates:index|Automates]]\\
Vendredi 1 mars 2024, 14 heures, Salle 3052\\
**Benjamin Bordais**  //From Local to Global Optimality in Concurrent Parity Games//
<button type="link" size="xs" collapse="b5-1039">{{icon>info-circle?lg&color=#777}}</button>\\
<collapse id="b5-1039" collapsed="true">
<well size="sm">
In two-player turn-based stochastic parity games, both players have positional optimal strategies. On the other hand, in two-player concurrent parity games, optimal strategies may not exist and playing (almost-)optimally may require infinite memory. In this talk, I will present how to identify a local condition that ensures the existence of positional optimal strategies for both players; this local condition is satisfied by more than only turn-based games. I will discuss how we have proved this result --- by adapting to the concurrent setting techniques used in the turn-based deterministic setting --- and what we can say about this local condition.

This is a joint work with my former PhD advisors Patricia Bouyer and Stéphane Le Roux, and it is based on a paper published in CSL 2024.
</well>
</collapse>


[[seminaires:automates:index|Automates]]\\
Jeudi 29 février 2024, 14 heures, Salle 3052\\
**Ivan Varzinczak**  //An Introduction to Defeasible Description Logics//
<button type="link" size="xs" collapse="b5-1040">{{icon>info-circle?lg&color=#777}}</button>\\
<collapse id="b5-1040" collapsed="true">
<well size="sm">
Description Logics (DLs) are a family of logic-based knowledge representation formalisms with appealing computational properties and various applications at the confluence of artificial intelligence, databases and other areas. In particular, DLs are well-suited for representing and reasoning about ontologies; therefore, they stand as the formal foundations of the Semantic Web. The different DL formalisms that have been proposed in the literature provide us with a wide choice of constructors in the object language. Nevertheless, these are intended to represent only classical, unquestionable knowledge and, therefore, cannot express and cope with the different aspects of uncertainty and vagueness that often appear in everyday life. Examples of these comprise the various guises of exceptions, typicality (and atypicality), approximations and many others, as usually encountered in the different forms of everyday human reasoning. A similar argument can be put forward when moving to the level of entailment, that of the sanctioned conclusions from an ontology. DL systems provide a variety of (standard and non-standard) reasoning services. Still, the underlying notion of entailment remains classical. Therefore, depending on the application one has in mind, DLs inherit most of the criticisms raised in the development of the so-called non-classical logics. In this talk, I make a case for endowing DLs and their associated reasoning services with the ability to cope with defeasibility. I start by introducing the notion of defeasible class subsumption, which allows for the specification of and reasoning about defeasible inheritance. I also show how it can be given an intuitive semantics in terms of preference relations. Next, I show how to take defeasibility to the level of entailment through the notion of rational closure of a defeasible ontology. Of particular interest is the fact that our constructions do not negatively affect the decidability or complexity of reasoning with defeasible inheritance for a wide class of DLs.

Speaker's short CV:
Ivan Varzinczak is an associate professor at Université Paris 8. He holds a PhD (2006) in artificial intelligence from Université Paul Sabatier, France. Ivan has co-authored over 75 peer-reviewed publications on logic-based approaches to knowledge representation and reasoning in AI. In 2019 he defended his habilitation at Université d'Artois, France. Ivan is an associate editor of Artificial Intelligence and of the Journal of Artificial Intelligence Research and chairman of the steering committee of the International Workshop on Nonmonotonic Reasoning. In 2022, he served as program chair of the 12th International Symposium on Foundations of Information and Knowledge Systems (FoIKS). He has had several visiting researcher appointments and taught courses and tutorials worldwide, including two courses at ESSLLI and two tutorials at IJCAI.
</well>
</collapse>


[[seminaires:automates:index|Automates]]\\
Vendredi 23 février 2024, 14 heures, Salle 3052\\
**Sven Dziadek** (Inria Paris) //Acceptance Conditions for Weighted ω-Automata//
<button type="link" size="xs" collapse="b5-1041">{{icon>info-circle?lg&color=#777}}</button>\\
<collapse id="b5-1041" collapsed="true">
<well size="sm">
Ésik and Kuich extended the theory of weighted formal languages to infinite words in 2005.
There, automata are matrices over a semiring and Büchi acceptance is an operation over those matrices.
We are trying to extend the theory to other acceptance conditions (Muller, generalized Büchi, etc.) and face several challenges.
Mainly, the former operator allows for a disjunction of constraints but now we need conjunction.

I will introduce the theory and detail those challenges.

Joint work with Uli Fahrenberg.
</well>
</collapse>


[[seminaires:automates:index|Automates]]\\
Vendredi 16 février 2024, 14 heures, Salle 3052\\
**Dakotah Lambert**  //Constraint-driven analysis of formal languages//
<button type="link" size="xs" collapse="b5-1042">{{icon>info-circle?lg&color=#777}}</button>\\
<collapse id="b5-1042" collapsed="true">
<well size="sm">
Often, a formal language can be described in several ways. The different descriptions bring with them different perspectives. One constraint might appear to be complex by one analysis but simple under another.  This talk discusses a few of the classes that have arisen with good motivation in the study of natural languages, with perspectives from algebra and learning theory in addition to the languages and their automata.
</well>
</collapse>


[[seminaires:automates:index|Automates]]\\
Vendredi 2 février 2024, 14 heures, Salle 3052\\
**Laetitia Laversa**  //k-synchronizability for distributed systems//
<button type="link" size="xs" collapse="b5-1043">{{icon>info-circle?lg&color=#777}}</button>\\
<collapse id="b5-1043" collapsed="true">
<well size="sm">
Distributed systems are ubiquitous and their implementation is complex and error-prone. In order to check for errors, they can be modeled as systems of communicating automata, where each automaton represents the behavior of an element of the system. In general, verification problems are undecidable in such a model. The use of (under or over) approximations is necessary. This talk presents k-synchronizable systems, which are a subclass of systems of communicating automata, and some results on them.
</well>
</collapse>


[[seminaires:automates:index|Automates]]\\
Vendredi 26 janvier 2024, 14 heures, Salle 3052\\
**Thomas Schwentick** (TU Dortmund) //Work-efficient constant-time parallel dynamic and static algorithms//
<button type="link" size="xs" collapse="b5-1044">{{icon>info-circle?lg&color=#777}}</button>\\
<collapse id="b5-1044" collapsed="true">
<well size="sm">
Dynamic algorithms constitute an established and rich research area.
"Dynamic Complexity" refers to a much less known research area, in which dynamic algorithms are specified by formulas of first-order logic. The class of problems for which this is possible is called DynFO.

The talk gives a short introduction to Dynamic Complexity and presents a recent and ongoing line of research that tries to bring Dynamic Complexity closer to Dynamic Algorithms through the study of constant-time parallel dynamic algorithms. It also takes a look at constant-time parallel "static" algorithms.
</well>
</collapse>


[[seminaires:automates:index|Automates]]\\
Vendredi 12 janvier 2024, 14 heures, Salle 3052\\
**Jon Rawski**  //Learning (Sub)regular string functions//
<button type="link" size="xs" collapse="b5-1045">{{icon>info-circle?lg&color=#777}}</button>\\
<collapse id="b5-1045" collapsed="true">
<well size="sm">
Automata can be characterized in terms of their expressive power, as well as their learnability, i.e. under what cases a canonical representation can be induced from data. This talk will overview recent insights in the learnability of subclasses of the regular transductions. I will overview polynomial time learning algorithms in a variety of settings, and show how in some cases one can reduce even further in time and space for certain subclasses (those that coincidentally characterize natural language patterns). I will then show how classes of functions can be used to create rigorous experiments testing the learning capacity of sequential neural networks. If there is time I will overview some ongoing work connecting newer neural net varieties to aperiodic transducers.
</well>
</collapse>