[logic-ml] JAIST Logic Seminar Series

[Takako Nemoto]

皆様
インスブリア大学（イタリア）の Marco Benini 先生の講演のお知らせです。
どうぞふるってご参加ください。

問い合わせ先：
根元　多佳子
北陸先端科学技術大学院大学　情報科学系
email: t-nemoto at jaist.ac.jp
---------------------------------------------
*JAIST Logic Seminar Series*

Date: Friday, 12 May, 2017, 15:30-17:00

Place: JAIST, Collaboration room 7 (I-56)
(Access: http://www.jaist.ac.jp/english/location/access.html)

Speaker: Marco Benini (Università degli Studi dell'Insubria)

Title: Explaining the Kruskal's Tree Theorem

Abstract: The famous Kruskal's tree theorem states that the collection
of finite trees labelled over a well quasi order and ordered by
homeomorphic embedding, forms a well quasi order. Its intended
mathematical meaning is that the collection of finite, connected and
acyclic graphs labelled over a well quasi order is a well quasi order
when it is ordered by the graph minor relation.
Oppositely, the standard proof(s) shows the property to hold for trees
in the Computer Science's sense together with an ad-hoc, inductive
notion of embedding. The mathematical result follows as a consequence
in a somewhat unsatisfactory way.
In this talk, a variant of the standard proof will be illustrated
explaining how the Computer Science and the graph-theoretical
statements are strictly coupled, thus explaining why the double
statement is justified and necessary.