情報理工学院特別講演会

Jacques Sakarovitch先生（CNRS / Paris Diderot University名誉上級研究員, Telecom ParisTech名誉教授）の連続講演会を開催いたします。Sakarovitch先生はオートマトン理論の世界的研究者であり、この分野の最近の教科書として非常に有名な「Elements of Automata Theory」の著者でもあります。１日目は現代的なオートマトン理論の基礎に関する講義をしていただきます。２日目はSakarovitch先生のこれまでの研究成果を中心に講演をいただきます。申し込みは不要ですので皆様どうぞふるってご参加ください。なお２日間で会場が異なりますのでご注意ください。

【１日目】
日時：2018年２月２８日（水）１６時３０分から１７時３０分
会場：西９号館Ｗ９３５講義室
【２日目】
日時：2018年３月１日（木）１６時３０分から１７時３０分
会場：西９号館ディジタル多目的ホール

【１日目概要】
Title: Automata and expressions
Abstract:
Not many results in Computer Science are recognised to be as basic and fundamental as Kleene Theorem. It states the equality of two sets of objects that we now call languages.
In this lecture, I propose a slight change of focus on this result and show how it is mainly the combination of two families of algorithms: algorithms that transform an automaton into an expression on one hand and algorithms that build an automaton from an expression on the other.
The first purpose is to compare the results of these algorithms, in order to understand they are indeed not so different. And also to devise means to keep these results as small as possible.
The second benefit of isolating this part of Kleene Theorem is to allow its extension much beyond languages: to subsets of arbitrary monoids first, and then, with some precaution, to subsets with multiplicity, that is, to formal power series.

【２日目概要】
Title: Conjugacy and equivalence of weighted automata
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.

【問い合わせ先】
鹿島 亮 （情報理工学院 数理・計算科学系）
kashima@is.titech.ac.jp