### March 14, 2022

*Une méthode générique d’amélioration de stratégie pour les jeux stochastiques simples.*

**Yann Strozecki**

Skip to content
# Seminars 2021-22

Contact : seminar@lacl.fr
# On monday, at 2pm - UPEC CMC - Room P2-131

### March 14, 2022

*Une méthode générique d’amélioration de stratégie pour les jeux stochastiques simples.*

**Yann Strozecki**
(UVSQ, laboratoire DAVID)

### January 24, 2022

*TBA*

**Nathan Grosshans**
(Universität Kassel)

### December 13, 2021

*Addressing Machines for Higher-Order Computations*

**Giulio Manzonetto**
( Laboratoire d'Informatique de Paris Nord (LIPN))

### December 6, 2021

*Geometric amortization of enumeration algorithms*

**Florent Capelli**
(INRIA Lille équipe LINKS)

### November 29, 2021

*Invariance pour l’ordre et logique à deux variables.*

**Julien Grange**
(LACL)

### November 22, 2021

*QCSP monsters and the future of the Chen Conjecture*

**Barnaby Martin**
(Durham University, Algorithms and Complexity Group (ACiD) )

### November 15, 2021

*Pareto analysis and approximation in stochastic and timed systems*

**Mahsa Shirmohammadi**
(IRIF)

### November 8, 2021

*Conjunctive grammars, cellular automata and logic*

**Théo Grente**
(LACL)

### October 18, 2021

*Simulating Digital Computations with Analog Machines*

**Olivier Bournez**
(Lix)

### October 11, 2021

*Expressions régulières pour transducteurs apériodiques*

**Luc Dartois**
(LACL)

Turing machines and register machines have been used for

decades in theoretical computer science as abstract models of

computation. However, they are not well-suited for modelling

higher-order computations, because accessing the address of a machine

is not a built-in operation, hence functional machines cannot be

easily passed through their reference. We study a class of abstract

machines that we call “*addressing machines*” since they are only able

to manipulate memory addresses of other machines. The operations

performed by these machines are very elementary: load an address in a

register, apply a machine to another one via their addresses, and call

the address of another machine. We endow addressing machines with an

operational semantics based on leftmost reduction and study their

behaviour. We show that they can be used, for instance, to construct

models of the pure, untyped lambda-calculus. Subsequently, we extend

the syntax of their programs by adding instructions for executing

arithmetic operations on natural numbers, and introduce a reflection

principle allowing certain machines to access their own address and

perform recursive calls. We show that the resulting extended

addressing machines naturally model a weak call-by-name PCF with

explicit substitutions. Finally, we show that they are also well

suited for representing regular PCF programs (closed terms) computing

natural numbers.

Enumeration algorithms are algorithms whose goal is to

output the set of all solutions to a given problem. There exists

different measures for the quality of such algorithm, whose relevance

depends on what the user wants to do with the solutions set.

If the goal of the user is to explore a subset of solutions or to

transform the solutions as they are outputted with a stream-like

algorithm, a relevant measure of the complexity in this case is the

delay, that is, the maximal time between the output of two distinct

solutions. Following this line of thoughts, significant efforts have

been made by the community to design polynomial delay algorithms, that

is, algorithms whose delay between the output of two new solutions is

polynomial in the size of the input.

While this measure is interesting, it is not always completely

necessary to have a bound on the delay and it is enough to ask for a

guarantee that running the algorithm for O(t poly(n)) will produce at

least t solutions. While algorithms having this property can be

transformed into polynomial delay algorithm, the naive transformation

may result in a blow up in the space used by the enumerator.

In this talk, we will present a new technique that allow to transform

such algorithms into polynomial delay algorithm with only a polynomial

overhead on the space.

On s’intéressera au pouvoir d’expression d’une extension particulière de la logique du premier ordre portant sur deux variables (FO^2).

On enrichira nos structures d’un ordre linéaire sur leurs sommets, en s’imposant toutefois la limitation suivante: une formule peut s’appuyer sur cette relation d’ordre uniquement si son évaluation est indépendante de cet ordre.

Cette notion d’invariance pour l’ordre est très naturelle en complexité descriptive, et son application à FO^2 l’est d’autant plus que la propriété d’invariance est décidable dans ce contexte.

Il apparaît clairement que l’ajout de cet ordre invariant accroît le pouvoir d’expression de FO^2, en autorisant le comptage.

On proposera ici une borne supérieure à son pouvoir d’expression sur les classes de structures de degré borné.

We elaborate the complexity of the Quantified Constraint Satisfaction Problem, QCSP(A), where A is a finite idempotent algebra. Such a problem is either in NP or is co-NP-hard, and the borderline is given precisely according to whether A enjoys the polynomially-generated powers (PGP) property. This completes the complexity classification problem for QCSPs modulo that co-NP-hard cases might have complexity rising up to Pspace-complete. Our result requires infinite languages, but in this realm represents the proof of a slightly weaker form of a conjecture for QCSP complexity made by Hubie Chen in 2012. The result relies heavily on the algebraic dichotomy between PGP and exponentially-generated powers (EGP), proved by Dmitriy Zhuk in 2015, married carefully to previous work of Chen. Finally, we discuss some recent work with Zhuk in which the aforementioned Chen Conjecture is actually shown to be false. Indeed, the complexity landscape for QCSP(B), where B is a finite constraint language, is much richer than was previously thought.

This is a survey talk on the Pareto and $\epsilon$-Gap Pareto analysis in Markov decision processes, stochastic games and weighted time automata.

The talk will lightly introduce the problems and the challenges one encounters while studying them in the stochastic and time systems; the talk will also pinpoint a couple of related open problems in the above-mentioned models.

Conjunctive grammars are an extension of context free grammars with a conjunction operation. Their expressive power (even on a unary alphabet) is largely unknown.

When restricting time, space or even communication, cellular automata (CA) can act as languages recognizer defining complexity classes.

The goal of this talk is to prove the inclusion of conjunctive languages in one of CA complexity classes.

The proof uses a programming method which relies on exact characterizations of interesting CA complexity classes by sub-logics of ESO (existential second-order logic) with Horn formulas as their first-order part. By using this method, we just have to define conjunctive grammars in our logic to obtain an inclusion result.

We will compare the power of analog machines (such as the General Purpose Analog Computer), based for example on analog electronics, to the power of digital machines (such as Turing machines). This will involve a discussion on how one can compute with ordinary differential equations.

La *classes des fonctions régulières* est une classe robuste définie de façon équivalente par les *transducteurs bidirectionnels*, les *transductions MSO* ou encore les *Streaming String Transducers*. Récemment, il a été proposé des *combinateurs réguliers* afin de définir des expressions régulières pouvant décrire cette classe.

Dans cet exposé, je présenterai la classe des transducteurs bidirectionnels ainsi que ces combinateurs réguliers, puis une extension de ce résultat à la sous-classe des fonctions apériodiques, étendant le célèbre résultat d’équivalence entre expressions sans-étoiles et automates apériodiques de Schützenberger.

Les résultats présentés ici proviennent de travaux récents en collaboration avec Paul Gastin (LSV, Université Paris-Saclay) et Shankara Narayanan Krishna (IIT Bombay) et sont disponible à cette adresse.