On monday, at 2pm - UPEC CMC - Room P2-131

January 24, 2022


Nathan Grosshans (Universität Kassel)

December 13, 2021

Addressing Machines for Higher-Order Computations

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

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.

December 6, 2021

Geometric amortization of enumeration algorithms

Florent Capelli (INRIA Lille équipe LINKS)

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.

November 29, 2021

Invariance pour l’ordre et logique à deux variables.

Julien Grange (LACL)

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é.

November 22, 2021

QCSP monsters and the future of the Chen Conjecture

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

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.

November 15, 2021

Pareto analysis and approximation in stochastic and timed systems

Mahsa Shirmohammadi (IRIF)

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.

November 8, 2021

Conjunctive grammars, cellular automata and logic

Théo Grente (LACL)

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.

October 18, 2021

Simulating Digital Computations with Analog Machines

Olivier Bournez (Lix)

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.

October 11, 2021

Expressions régulières pour transducteurs apériodiques

Luc Dartois (LACL)

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.