# Séminaire DALGO : Guido Proietti

Orateur : Guido Proietti (Università degli Studi dell'Aquila)

# Séminaire MOVE : "Costs and Rewards in Priced Timed Automata", Mahsa Shirmohammadi (LIS)

We consider Pareto analysis of reachable states of multi-priced timed automata (MPTA): timed automata equipped with multiple observers that keep track of costs (to be minimised) and rewards (to be maximised) along a computation. Each observer has a constant non-negative derivative which may depend on the location of the MPTA. We study the Pareto Domination Problem, which asks whether it is possible to reach a target location via a run in which the accumulated costs and rewards Pareto dominate a given objective vector. We show that this problem is undecidable in general, but decidable for MPTA with at most three observers. For MPTA whose observers are all costs or all rewards, we show that the Pareto Domination Problem is PSPACE-complete. We also consider an ε-approximate Pareto Domination Problem that is decidable without restricting the number and types of observers. We develop connections between MPTA and Diophantine equations. Undecidability of the Pareto Domination Problem is shown by reduction from Hilbert’s 10th Problem, while decidability for three observers is shown by a translation to a fragment of arithmetic involving quadratic forms.

# Séminaire CANA: Cryptic genes and genetic codes in mitochondria: Some of DNA’s unexplored coding dimensions, Hervé Seligmann

Résumé: Three mechanisms reveal unsuspected information in protein-coding genes: 1) alternative transcriptions that transform along systematic rules template sequences (for example systematic deletions of k nucleotides after each n transcribed nucleotides and systematic exchanges between nucleotides, such as AC or A>C>G>A); 2) codon expansion, where tRNAs with anticodons expanded by noncoding nucleotide(s) decode expanded codons; and 3) reassignments of codons to different amino acids. Here I present evidences for mechanisms 1 and 2, and associated self-correcting properties of the genetic code.

# Séminaire CANA: Classical and Quantum Simulations via Quantum algorithms, Pedro Costa

Abstract: The era of quantum computers has already started. One important question that we can do now that we have these quantum devices ready is which quantum model of computation will be a good choice for encoding the huge number of quantum algorithms available. Another important question which is also extremely important to people that work in the industry that very often employs numerical methods to solve differential equations is that if these numerical methods are a promising application for quantum computers. Going to these directions we will present in this seminar our latest results where we introduce a partitioned model of quantum cellular automata and show how it can simulate, with the same amount of resources, various models of quantum walks. All the algorithms developed within quantum walk models are thus directly inherited by the quantum cellular automata. The latter, however, has its structure based on local interactions between qubits, and as such it can be more suitable for present (and future) experimental implementations. In the part related with numerical methods to solve differential equations, we will present a quantum algorithm for simulating the wave equation under Dirichlet and Neumann boundary conditions. The algorithm uses Hamiltonian simulation and quantum linear system algorithms as subroutines. Relative to classical algorithms for simulating the D-dimensional wave equation, our quantum algorithm achieves exponential space savings, and a speedup which is polynomial for fixed D and exponential in D. We also consider using Hamiltonian simulation for Klein-Gordon equations and Maxwell’s equations.

# WorkShop DYNI : DCLDE 2018

l'équipe DYNI du LIS, UTLN, est heureuse de lancer en partenariat avec le Scripps Inst. le plus grand challenge de bioacoustique sous-marine (4 To, Atlantique et Pacifique) dans le cadre du congrès de Détection Classification Localisation & Estimation de Densité de mammifère marin que nous co-organisons avec Sorbonne Univ. en Juin.

# Séminaire DALGO : "Anonymity in Distributed Read/Write Systems: a Short Problem-Based Introduction", Michel Raynal

Orateur : Michel Raynal (Professeur, IRISA, Université de Rennes, et Hong Kong Polytechnic University)