[kisoron-ml] Prof. Georg Moser at NII Logic Seminar

[Makoto Tatsuta]

		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: tatsuta at nii.ac.jp
http://research.nii.ac.jp/~tatsuta