Prof. Georg Moser at NII Logic Seminar
Date: February 13, 2015, 14:00--16:00
Place: National Institute of Informatics, Room 1208 (12th floor) 場所: 国立情報学研究所 12階 1208室 (半蔵門線,都営地下鉄三田線・新宿線 神保町駅または東西線 竹橋駅より徒歩5分) (地図 http://www.nii.ac.jp/about/access/)
Speaker: Prof. Georg Moser (University of Innsbruck)
Title: Amortised Cost Analysis and Term Rewrite Systems
Abstract: I will present a univariate resource analysis for typed term rewrite systems based on a potential-based type system. This type system gives rise to polynomial bounds on the innermost runtime complexity. The thus obtained amortised resource analysis relates to polynomial interpretations and we obtain the perhaps surprising result that whenever a rewrite system can be well-typed, then there exists a polynomial interpretation that orients the system. If time permits I'll speak about very recent generalisations to a multivariate analysis. This is a joint work with Martin Hofmann.
問合せ先: 龍田 真 (国立情報学研究所) e-mail: [email protected] http://research.nii.ac.jp/~tatsuta