皆様 インスブリア大学（イタリア）の Marco Benini 先生の講演のお知らせです。 どうぞふるってご参加ください。
問い合わせ先： 根元 多佳子 北陸先端科学技術大学院大学 情報科学系 email: [email protected] --------------------------------------------- *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.