Parsimonious Types and Non-uniform Computation
Parsimonious Types and Non-uniform Computation
复制标题
简约类型和非均匀计算
DOI：
10.1007/978-3-662-47666-6_28
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Damiano Mazza and Kazushige Terui
中科院分区：
文献类型：
--
作者：
中島若巳;荒谷聡子;藤田英俊;槇田浩史;西岡久寿樹;瀬戸口靖弘;中島利博;Kazushige Terui;Ryota Akiyoshi and Kazushige Terui;Damiano Mazza and Kazushige Terui
我们考虑了一个非均匀仿射代数演算，称为简约，并赋予它的条款与两个类型的纪律：简单类型和线性多态性。我们证明了在第一种情况下，字符串类型到布尔类型的术语表征类L/poly，在第二种情况下，P/poly。此外，我们将这种特征与第二作者在布尔证明网方面给出的特征相关联，突出连续仿射近似作为两种非均匀计算方法之间的桥梁。
We consider a non-uniform affine lambda-calculus, called parsimonious, and endow its terms with two type disciplines: simply-typed and with linear polymorphism. We show that the terms of string type into Boolean type characterize the class L/poly in the first case, and P/poly in the second. Moreover, we relate this characterization to that given by the second author in terms of Boolean proof nets, highlighting continuous affine approximations as the bridge between the two approaches to non-uniform computation.