19 April 2018

Séminaire MOVE : « From Two-Way Transducers to Regular Functions Expressions », Nicolas Baudru (LIS)

Transducers constitute a fundamental extension of automata. The class of regular word functions has recently emerged as an important class of word-to-word functions, characterized by means of (functional, or unambiguous, or deterministic) two-way transducers, copylessstreaming string transducers, and MSO-definable graph transformations. One of the most important result in language theory is Kleene theorem, relating finite state automata and regular expressions. R. Alur, A. Freilich and M. Raghothaman have introduced (CSL-LICS '14) a set of regular function expressions and proved a similar result for regular word functions, by showing the equivalence with copyless streaming string transducers. In this paper, we propose a direct, simplified and effective translation from unambiguous two-way transducers to regular function expressions. In addition, our approach allows us to derive a subset of regular function expressions characterizing the (strict) subclass of functional sweeping transducers.
19 April 2018, 11h0012h30
Salle de réunion du bâtiment modulaire BP5 (en bas de la BU), Luminy

Prochains évènements

Retour à l'agenda
03 May 2018

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.