Evènement pour le groupe Séminaire Méthodes Formelles

Date 2016-02-09  11:00-12:00
TitreA Generalised Twinning Property for Minimisation of Cost Register Automata. 
RésuméWeighted automata extend finite-state automata by associating with transitions weights from a semiring S, defining functions from words to S. Recently, cost register automata have been introduced as an alternative model to describe any function realised by a weighted automaton by means of a deterministic machine. Unambiguous weighted automata over a group G can equivalently be described by cost register automata whose registers take their values in G, and are updated by operations of the form x:=y.c, with c in G, and x,y registers. This class is denoted by CRA(G). In this talk, I will introduce a twinning property and a bounded variation property parametrised by an integer k, such that the corresponding notions introduced originally by Choffrut for finite-state transducers are obtained for k=1. Our main result links these notions with the register complexity of CRA(G). More precisely, we prove that given an unambiguous weighted automaton W over an infinitary group G realizing some function f, the three following properties are equivalent: i) W satisfies the twinning property of order k, ii) f satisfies the k-bounded variation property, iii) f can be described by a CRA(G) with at most k registers. Actually, this result is proved in a more general setting, considering machines over the semiring of finite sets of elements from G and is extended to prove a similar result for finite-valued finite-state transducers. Finally, the effectiveness of the constructions leads to decidability/complexity results about the register complexity (i.e. what is the minimal number of registers needed to compute a given function) of cost register automata. This is a joint work with Pierre-Alain Reynier and Jean-Marc Talbot. 
OrateurLaure Daviaud 
UrlLIP - ENS Lyon 

Aucun document lié à cet événement.

Retour à l'index