下記の要領にて，フランスからJacques Sakarovitch先生を招きし，2月23日(金)に Seminar および Lecture を実施いたします．

Sakarovitch先生は現代のオートマトン理論を牽引する世界的研究者であり，この連続講演会は計算機科学に限らず幅広い分野の方々に興味を持っていただけると思います． どうぞふるってご参加ください．

なお，Lectureでは，量子オートマトンとも関連の深い『重み付きオートマトン(weighted automata)』の入門講義をしてもらいます．本講義では現代的なオートマトン理論の基礎を説明してもらう予定ですので，学生の皆様もどうぞふるってご参加ください．

Lecture

Time:
12:30 ~ 14:00, February 23, 2018 (Fri.)

Venue:
Room 209, Faculty of Engineering Science Bldg. No. 7

Title:
Introduction to the theory of weighted automata

Jacques Sakarovitch
CNRS / Paris Diderot University and Telecom ParisTech, Paris

Abstract

This lecture presents the computation model of weighted automata, as a generalisation of the classical finite automata, called Boolean automata in this context.

A weighted automaton does not define a set of words, but a function that associates with every word a value, taken in an arbitrary semiring. The diversity of the possible semiring taken as weight sets gives its richness and versatility to the model of weighted automata.

We will see how the notions of rationality and recognizability extend to these objects, the new problems that arise, and the new mathematical tools that come into play, with the problem of decidability of equivalence as a motivating goal.

As Eilenberg already noted 45 years ago, taking into account multiplicity or weight does not only enlarge the scope of automata theory. Some problems become simpler, and some developments shed a new light on the Boolean case.

 

Seminar

Time:
15:30 ~ 17:00, February 23, 2018 (Fri.)

Venue:
Room 209, Faculty of Engineering Science Bldg. No. 7

Title:
Conjugacy and equivalence of weighted automata

Jacques Sakarovitch
CNRS / Paris Diderot University and Telecom ParisTech

Abstract:
As a main thread of this talk, I present the proof of the following result:

If two regular languages $L$ and $K$ have the same generating functions, that is, for every integer $n$ they have the same number of words of length $n$, there exists a rational bijection realised by a letter-to-letter transducer that maps $L$ onto $K$.

This statement is a consequence of a refinement of the decidability of the equivalence of two automata with multiplicity in $N$. It gives us the opportunity to review first the basic definitions and results on weighted finite automata, and second to revisit the `classical’ theory of reduction of automata with two notions borrowed to symbolic dynamics: conjugacy and the Finite Equivalence Theorem.