检索结果-内蒙古大学图书馆

From light logics to type assignments: a case study

LOGIC JOURNAL OF THE IGPL 2009年第5期17卷 449-480页

作者： Gaboardi, Marco Della Rocca, Simona Ronchi Univ Turin Dipartimento Informat I-10149 Turin Italy

Using Soft Linear Logic (SLL) as case study, we analyze a method for transforming a light logic into a type assignment system for the lambda-calculus, inheriting the complexity properties of the logics. Namely the typing assures the strong normalization in a number of steps polynomial in the size of the term, and moreover all polynomial functions can be computed by lambda-terms that can be typed in the system. The proposed method is general enough to be used also for other light logics.

关键词： type assignment implicit computational complexity lambda calculus polynomial time

来源：评论

学校读者我要写书评

暂无评论

Some complexity and Expressiveness Results on Multimodal and Stratified Proof Nets

Some Complexity and Expressiveness Results on Multimodal and...

引用

International Conference of the TYPES 2008

作者： Roversi, Luca Vercelli, Luca Univ Turin Dip Informat I-10124 Turin Italy Univ Turin Dept Matemat I-10124 Turin Italy

ISBN: (纸本)9783642024436

We introduce a multimodal stratified framework MS that generalizes an idea hidden in the definitions of Light Linear/Affine logical systems: "More modalities means more expressiveness". MS is a set of building-rule schemes that depend on parameters. We interpret the values of the parameters as modalities. Fixing the parameters yields deductive systems as instances of MS, that we call subsystems. Every subsystem generates stratified proof nets whose normalization preserves stratification, a structural property of nodes and edges, like in Light Linear/Affine logical systems. A first result is a sufficient condition for determining when a subsystem is strongly polynomial time sound. A second one shows that the ability to choose which modalities are used and how can be rewarding. We give a family of subsystems as complex as Multiplicative Linear Logic they are linear time and space sound - that can represent Church numerals and some common combinators on them.

关键词： implicit computational complexity Structural Proof-theory Linear Logic Polynomial Time Computations

来源：评论

学校读者我要写书评

暂无评论

complexity Information Flow in a Multi-threaded Imperative Language

Complexity Information Flow in a Multi-threaded Imperative L...

引用

11th Annual Conference on Theory and Applications of Models of Computation (TAMC)

作者： Marion, Jean-Yves Pechoux, Romain Univ Lorraine CNRS Nancy France

ISBN: (纸本)9783319060897;9783319060880

In this paper, we propose a type system to analyze the time consumed by multi-threaded imperative programs with a shared global memory, which delineates a class of safe multi-threaded programs. We demonstrate that a safe multi-threaded program runs in polynomial time if (i) it is strongly terminating wrt a non-deterministic scheduling policy or (ii) it terminates wrt a deterministic and quiet scheduling policy. As a consequence, we also characterize the set of polynomial time functions. The type system presented is based on the fundamental notion of data tiering, which is central in implicit computational complexity. It regulates the information flow in a computation. This aspect is interesting in that the type system bears a resemblance to typed based information flow analysis and notions of non-interference. As far as we know, this is the first characterization by a type system of polynomial time multi-threaded programs.

关键词： implicit computational complexity Ptime multi-threaded imperative language non-interference type system

来源：评论

学校读者我要写书评

暂无评论

A Logical Account of PSPACE

A Logical Account of PSPACE

引用

35th ACM-SIGPLAN-SIGACT Symposium on Principles of Programming Languages

作者： Gaboardi, Marco Della Rocca, Simona Ronchi Marion, Jean-Yves Univ Turin Dipartimento Informat I-10149 Turin Italy

ISBN: (纸本)9781595936899

We propose a characterization of PSPACE by means of a type assignment for an extension of lambda calculus with a conditional construction. The type assignment STA(B) is an extension of STA, a type assignment for lambda-calculus inspired by Lafont's Soft Linear Logic. We extend STA by means of a ground type and terms for booleans. The key point is that the elimination rule for booleans is managed in an additive way. Thus, we are able to program polynomial time Alternating Turing Machines. Conversely, we introduce a call-by-name evaluation machine in order to compute programs in polynomial space. As far as we know, this is the first characterization of PSPACE which is based on lambda calculus and light logics.

关键词： implicit computational complexity Polynomial Space Linear Logic Type Assignment

来源：评论

学校读者我要写书评

暂无评论

Type-Based complexity Analysis for Fork Processes

Type-Based Complexity Analysis for Fork Processes

引用

16th International Conference on Foundations of Software Science and Computation Structures (FOSSACS) Held as Part of the European Joint Conferences on Theory and Practice of Software (ETAPS)

作者： Hainry, Emmanuel Marion, Jean-Yves Pechoux, Romain Univ Lorraine Nancy France LORIA Villers Les Nancy France

ISBN: (纸本)9783642370755;9783642370748

We introduce a type system for concurrent programs described as a parallel imperative language using while-loops and fork/wait instructions, in which processes do not share a global memory, in order to analyze computational complexity. The type system provides an analysis of the data-flow based both on a data ramification principle related to tiering discipline and on secure typed languages. The main result states that well-typed processes characterize exactly the set of functions computable in polynomial space under termination, confluence and lock-freedom assumptions. More precisely, each process computes in polynomial time so that the evaluation of a process may be performed in polynomial time on a parallel model of computation. Type inference of the presented analysis is decidable in linear time provided that basic operator semantics is known.

关键词： implicit computational complexity Tiering Secure Information Flow Concurrent Programming PSpace

来源：评论

学校读者我要写书评

暂无评论

The Power of Non-determinism in Higher-Order implicit complexity Characterising complexity Classes Using Non-deterministic Cons-Free Programming 26th

The Power of Non-determinism in Higher-Order Implicit Comple...

引用

26th European Symposium on Programming (ESOP) Held as Part of the European Joint Conferences on Theory and Practice of Software (ETAPS)

作者： Kop, Cynthia Simonsen, Jakob Grue Univ Copenhagen DIKU Dept Comp Sci Copenhagen Denmark

ISBN: (纸本)9783662544341;9783662544334

We investigate the power of non-determinism in purely functional programming languages with higher-order types. Specifically, we consider cons-free programs of varying data orders, equipped with explicit non-deterministic choice. Cons-freeness roughly means that data constructors cannot occur in function bodies and all manipulation of storage space thus has to happen indirectly using the call stack. While cons-free programs have previously been used by several authors to characterise complexity classes, the work on non-deterministic programs has almost exclusively considered programs of data order 0. Previous work has shown that adding explicit non-determinism to cons-free programs taking data of order 0 does not increase expressivity;we prove that this-dramatically-is not the case for higher data orders: adding non-determinism to programs with data order at least 1 allows for a characterisation of the entire class of elementary-time decidable sets. Finally we show how, even with non-deterministic choice, the original hierarchy of characterisations is restored by imposing different restrictions.

关键词： implicit computational complexity Cons-free programming EXPTIME hierarchy Non-deterministic programming Unitary variables

来源：评论

学校读者我要写书评

暂无评论

Taming Modal Impredicativity: Superlazy Reduction

引用

International Symposium on Logical Foundations of Computer Science

作者： Dal Lago, Ugo Roversi, Luca Vercelli, Luca Univ Bologna Dept Informat I-40126 Bologna Italy Univ Turin Dept Informat I-10124 Turin Italy Univ Turin Dept Matemat I-10124 Turin Italy

ISBN: (纸本)9783540926863

Pure, or type-free, Linear Logic proof nets are Turing complete once cut-elimination is considered as computation. We introduce, modal impredicativity as a new form of impredicativity causing cut-elimination to be problematic from a complexity point of view. Modal impredicativity occurs when, during reduction, the conclusion of a residual of a box b interacts with a node that belongs to the proof net inside another residual of b. Technically speaking, superlazy reduction is a new notion of reduction that allows to control modal impredicativity. More specifically, superlazy reduction replicates a box only when all its copies are opened. This makes the overall cost of reducing a proof net finite and predictable. Specifically, superlazy reduction applied to any pure proof nets takes primitive recursive time. Moreover, any primitive recursive function can be computed by a pure proof net via superlazy reduction.

关键词： Linear logic implicit computational complexity proof theory

来源：评论

学校读者我要写书评

暂无评论

Types for complexity of Parallel Computation in Pi-Calculus 1

引用

30th European Symposium on Programming (ESOP) Held as Part of the 24th European Joint Conferences on Theory and Practice of Software (ETAPS)

作者： Baillot, Patrick Ghyselen, Alexis Univ Claude Bernard Lyon 1 LIP Univ Lyon CNRSENS Lyon F-69342 Lyon 07 France

ISBN: (数字)9783030720193

ISBN: (纸本)9783030720193;9783030720186

Type systems as a technique to analyse or control programs have been extensively studied for functional programming languages. In particular some systems allow to extract from a typing derivation a complexity bound on the program. We explore how to extend such results to parallel complexity in the setting of the pi-calculus, considered as a communication-based model for parallel computation. Two notions of time complexity are given: the total computation time without parallelism (the work) and the computation time under maximal parallelism (the span). We define operational semantics to capture those two notions, and present two type systems from which one can extract a complexity bound on a process. The type systems are inspired both by size types and by input/output types, with additional temporal information about communications.

关键词： Type Systems Pi-calculus Process Calculi complexity Analysis implicit computational complexity Size Types

来源：评论

学校读者我要写书评

暂无评论

Linear, polynomial or exponential? complexity inference in polynomial time

Linear, polynomial or exponential? Complexity inference in p...

引用

4th Conference on Computability in Europe (CiE 2008)

作者： Ben-Amram, Amir M. Jones, Neil D. Kristiansen, Lars Tel Aviv Acad Coll Sch Comp Sci Tel Aviv Israel Univ Copenhagen DIKU DK-1168 Copenhagen Denmark Univ Oslo Dept Math N-0316 Oslo Norway

ISBN: (纸本)9783540694052

We present a new method for inferring complexity properties for imperative programs with bounded loops. The properties handled are: polynomial (or linear) boundedness of computed values, as a function of the input;and similarly for the running time. It is well known that complexity properties are undecidable for a Turing-complete programming language. Much work in program analysis overcomes this obstacle by relaxing the correctness notion: one does not ask for an algorithm that correctly decides whether the property of interest holds or not, but only for "yes" answers to be sound. In contrast, we reshaped the problem by defining a "core" programming language that is Turing-incomplete, but strong enough to model real programs of interest. For this language, our method is the first to give a certain answer;in other words, our inference is both sound and complete. The essence of the method is that every command is assigned a "complexity certificate", which is a concise specification of dependencies of output values on input. These certificates are produced by inference rules that are compositional and efficiently computable. The approach is inspired by previous work by Niggl and Wunderlich and by Jones and Kristiansen, but use a novel, more expressive kind of certificates.

关键词： implicit computational complexity polynomial time complexity linear time complexity static program analysis

来源：评论

学校读者我要写书评

暂无评论

Linear Dependent Types and Relative Completeness

Linear Dependent Types and Relative Completeness

引用

26th Annual IEEE Symposium on Logic in Computer Science (LICS)

作者： Dal Lago, Ugo Gaboardi, Marco Univ Bologna Dipartimento Sci Informaz I-40126 Bologna Italy INRIA Valbonne France

ISBN: (纸本)9780769544120

A system of linear dependent types for the lambda calculus with full higher-order recursion, called dlPCF, is introduced and proved sound and relatively complete. Completeness holds in a strong sense: dlPCF is not only able to precisely capture the functional behaviour of P C F programs (i.e. how the output relates to the input) but also some of their intensional properties, namely the complexity of evaluating them with Krivine's Machine. dlPCF is designed around dependent types and linear logic and is parametrized on the underlying language of index terms, which can be tuned so as to sacrifice completeness for tractability.

关键词： implicit computational complexity lambda calculus relative completeness type systems

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：