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

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

来源：评论

学校读者我要写书评

暂无评论

The complexity of Checking Consistency of Pedigree Information and Related Problems

引用

Journal of Computer Science & Technology 2004年第1期19卷 42-59页

作者： LucaAceto JensA.Hansen AnnaIngdlfsddttir JacobJohnsen JohnKnudsen BasicResearchinComputerScience CentreoftheDanishNationalResearchFoundationDepartmentofComputerScienceAalborgUniversityFr.Bajersvej7E9220AalborgΦDenmark deCODEGenetics Sturlugata8101ReykjavikIceland

Consistency checking is a fundamental computational problem in *** a pedigree and information on the genotypes (of some) of the individuals in it, the aim ofconsistency checking is to determine whether these data are consistent with the classic Mendelianlaws of inheritance. This problem arose originally from the geneticists'' need to filter their inputdata from erroneous information, and is well motivated from both a biological and a sociologicalviewpoint. This paper shows that consistency checking is NP-complete, even with focus on a singlegene and in the presence of three alleles. Several other results on the computational complexity ofproblems from genetics that are related to consistency checking are also offered. In particular, itis shown that checking the consistency of pedigrees over two alleles, and of pedigrees withoutloops, can be done in polynomial time.

关键词： consistency checking pedigrees genotypes NP-completeness satisfiability polynomial time complexity critical genotypes

来源：评论

学校读者我要写书评

暂无评论

Combining linear logic and size types for implicit complexity

引用

THEORETICAL COMPUTER SCIENCE 2020年 813卷 70-99页

作者： Baillot, Patrick Ghyselen, Alexis Univ Claude Bernard Lyon I Univ Lyon CNRS ENS Lyon F-69342 Lyon 07 France

Several type systems have been proposed to statically control the time complexity of lambda-calculus programs and characterize complexity classes such as FPtime or FEXPtime. A first line of research stems from linear logic and restricted versions of its I-modality controlling duplication. An instance of this is light linear logic for polynomial time computation [5]. A second approach relies on the idea of tracking the size increase between input and output, and together with a restricted recursion scheme, to deduce time complexity bounds. This second approach is illustrated for instance by non-size-increasing types [8]. However, both approaches suffer from limitations. The first one, that of linear logic, has a limited intensional expressivity, that is to say some natural polynomial time programs are not typable. As to the second approach it is essentially linear, more precisely it does not allow for a non-linear use of functional arguments. In the present work we incorporate both approaches into a common type system, in order to overcome their respective constraints. The source language we consider is a lambda-calculus with datatypes and iteration, that is to say a variant of Gtidel's system T. Our goal is to design a system for this language allowing both to handle non-linear functional arguments and to keep a good intensional expressivity. We illustrate our methodology by choosing the system of elementary linear logic (ELL) and combining it with a system of linear size types. We discuss the expressivity of this new type system, called sEAL, and prove that it gives a characterization of the complexity classes FPtime and 2k-FEXPtime, for k >= 0. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Implicit computational complexity lambda-calculus Linear logic Type systems polynomial time complexity Size types

来源：评论

学校读者我要写书评

暂无评论

TRUDA: a truthful auction mechanism with non-uniform payment for heterogeneous spectrum access in wireless networks

引用

IET COMMUNICATIONS 2017年第14期11卷 2214-2220页

作者： Zhang, Yonglong Li, Bin Qin, Haiyan Yangzhou Univ Coll Informat Engn Yangzhou 225127 Jiangsu Peoples R China Nanjing Univ State Key Lab Novel Software Technol Nanjing 210093 Jiangsu Peoples R China

Auction is a highly effective trading form for distributing resource among buyers in a market at competitive prices, and has been applied to many domains, e.g. spectrum allocation in wireless networks and the virtual machine allocation in cloud computing. Most of existing auction mechanisms based on McAfee double auction calculate the uniform clearing prices for winning buyers no matter what channel they acquired, which does not reflect the differences of buyers' personalised preferences for heterogeneous spectrums. Hence, in this paper, we propose a truthful double auction scheme, named TRUDA, which incorporates the marginal effect of buyer-seller pair into auction mechanism design and considers the case in which buyers are mutually exclusive. We show analytically that this auction mechanism guarantees the economic-robustness of the auction and has polynomial time complexity.

关键词： radio networks frequency allocation pricing TRUDA nonuniform payment heterogeneous spectrum access wireless networks competitive prices spectrum allocation virtual machine allocation cloud computing McAfee double auction uniform clearing prices heterogeneous spectrums buyer personalised preferences buyer-seller pair marginal effect polynomial time complexity truthful double auction scheme

来源：评论

学校读者我要写书评

暂无评论

Iterative generation of higher-order nets in polynomial time using linear programming

引用

IEEE TRANSACTIONS ON NEURAL NETWORKS 1997年第2期8卷 402-412页

作者： Roy, A Mukhopadhyay, S Laboratory of Chromatography DEPg.Fac.Quimica Universidad Nacional Autonoma de Mexico Circuito interior Cd Universitaria/CP 04510 Mexico D.F.Mexico

This paper presents an algorithm for constructing and training a class of higher-order perceptrons for classification problems. The method uses linear programming models to construct and train the net, Its polynomial time complexity is proven and computational results are provided for several well-known problems, In all cases, very small nets were created compared to those reported in other computational studies.

关键词： designing neural networks feedforward nets higher-order networks learning complexity linear programming polynomial time complexity multilayer perceptrons

来源：评论

学校读者我要写书评

暂无评论

A temporal segmentation algorithm for restoring the controllability of networked control systems

引用

IET CONTROL THEORY AND APPLICATIONS 2022年第3期16卷 318-329页

作者： Cui, Yulong Wu, Mincheng Shao, Cunqi He, Shibo Zhejiang Univ State Key Lab Ind Control Technol Hangzhou 310027 Peoples R China

Restoring the controllability of networked control systems is a fundamental issue that needs to be settled, especially when malicious attacks or malfunctions occur. Previous studies tried to address such an issue by adding extra driver nodes or rewiring edges, which will inevitably change the original network structure. In this paper, an algorithm to restore the controllability of networked systems while preserving the integrity of the original network structure is proposed. Specifically, a static uncontrollable network will be transformed into a controllable temporal network by means of the cactus-based segmentation method. The original problem will be equivalent to the classical set cover problem, which is known to be NP-Hard, if the least number of segmentations is considered. An approximation algorithm with polynomial time complexity is proposed and it is proved that the solution to the problem is two-optimal. Finally, simulations are carried out to verify the effectiveness and feasibility of the proposed algorithm.

关键词： original network structure controllability approximation theory controllable temporal network set theory classical set cover problem malfunctions malicious attacks networked systems polynomial time complexity extra driver nodes cactus based segmentation method temporal segmentation algorithm computational complexity static uncontrollable network rewiring edges networked control systems

来源：评论

学校读者我要写书评

暂无评论

EVIDENCE-BASED RECOGNITION OF 3-D OBJECTS

引用

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE 1988年第6期10卷 783-802页

作者： JAIN, AK HOFFMAN, R NORTHROP CORP CTR RES & TECHNOL AUTOMAT SCI GRP PALOS VERDES PENINSULA CA 90274 USA

An evidence-based recognition technique is defined that identifies 3-D objects by looking for their notable features. This technique makes use of an evidence rule base, which is a set of salient or evidence conditions with corresponding evidence weights for various objects in the database. A measure of similarity between the set of observed features and the set of evidence conditions for a given object in the database is used to determine the identity of an object in the scene or reject the object(s) in the scene as unknown. This procedure has polynomial time complexity and correctly identifies a variety of objects in both synthetic and real range images. A technique for automatically deriving the evidence rule base from training views of objects is shown to generate evidence conditions that successfully identify new views of those objects.

关键词： Object recognition Layout Image recognition Reflectivity Spatial databases Image databases polynomials Navigation Surface emitting lasers Computer vision INSPEC: Controlled Indexing polynomials computational complexity computerised pattern recognition knowledge based systems INSPEC: Non-Controlled Indexing polynomial time complexity 3-D object recognition computerized pattern recognition evidence-based recognition rule base database

来源：评论

学校读者我要写书评

暂无评论

An Approach to Forming Optimal Design Structures on the Basis of the Ranking Method of Solving Nonlinear Boolean Equations

引用

JOURNAL OF AUTOMATION AND INFORMATION SCIENCES 2011年第10期43卷 42-55页

作者： Listrovoy, S. V. Minukhin, S. V. Ukrainian State Acad Railway Transport Kharkov Ukraine Kharkov Natl Univ Econ Kharkov Ukraine

The new problem statement of formalizing the choice of the optimal design structure of an organization, which is based on the modern methodology of developing complex software systems, reduced to nonlinear Boolean equations, is proposed. The procedure that uses the ranking approach to solving combinatorial optimization problems with the polynomial time complexity, is developed. The results of statistical modeling are given.

关键词： nonlinear Boolean equations ranking approach of solving optimal design structure of an organization polynomial time complexity

来源：评论

学校读者我要写书评

暂无评论

Light types for polynomial time computation in lambda calculus

引用

INFORMATION AND COMPUTATION 2009年第1期207卷 41-62页

作者： Baillot, Patrick Terui, Kazushige Univ Paris 13 CNRS UMR 7030 LIPN F-93430 Villetaneuse France Kyoto Univ Math Sci Res Inst Kyoto 6068501 Japan

We present a polymorphic type system for lambda calculus ensuring that well-typed programs can be executed in polynomial time: dual light affine logic (DLAL). DLAL has a simple type language with a linear and an intuitionistic type arrow, and one modality. It corresponds to a fragment of light affine logic (LAL). We show that contrarily to LAL, DLAL ensures good properties on lambda-terms (and not only on proof-nets): subject reduction is satisfied and a well-typed term admits a polynomial bound on the length of any of its beta reduction sequences. We also give a translation of LAL into DLAL and deduce from it that all polynomial time functions can be represented in DLAL. (c) 2008 Elsevier Inc. All rights reserved.

关键词： Linear logic Light linear logic Lambda calculus Type system Implicit computational complexity polynomial time complexity

来源：评论

学校读者我要写书评

暂无评论

A polynomial activity insertion algorithm in a multi-resource schedule with cumulative constraints and multiple modes

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2000年第2期127卷 297-316页

作者： Artigues, C Roubellat, F Univ Avignon & Pays Vaucluse Lab Informat Avignon F-84911 Avignon 9 France CNRS Lab Anal & Architecture Syst F-31077 Toulouse France

In this paper, a polynomial activity insertion algorithm in a multi-resource schedule with cumulative constraints, general precedence relations and multiple modes is proposed. Insertion objective is to minimize the resulting impact on maximum lateness, while keeping some essential characteristics of the initial schedule. A new disjunctive are-based representation with multiple capacities associated to resource arcs is proposed. Under specific constraints, some simple dominance rules allow to find an optimal insertion position in the digraph with low-computational requirements. (C) 2000 Elsevier Science B.V. All rights reserved.

关键词： multi-resource scheduling cumulative constraints multiple modes acyclic directed graphs activity insertion polynomial time complexity on-line scheduling local search

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：