共查询到20条相似文献,搜索用时 78 毫秒
1.
Read-write locking is an important mechanism to improve concurrent granularity, but it is difficult to reason about the safety of concurrent programs with read-write locks. Concurrent separation logic (CSL) provides a simple but powerful technique for locally reasoning about concurrent programs with mutual exclusive locks. Unfortunately, CSL cannot be directly applied to reasoning about concurrent programs with read-write locks due to the different concurrent control mechanisms.This paper focuses on extending CSL and presenting a proof-carrying code (PCC) system for reasoning about concurrent programs with read-write locks. We extend the heap model with a writing permission set, denoted as logical heap, then define “strong separation” and “weak separation” over logical heap. Following CSL’s local-reasoning idea, we develop a novel program logic to enforce weak separations of heap between different threads and provide verification of concurrent programs with read-write locks. 相似文献
2.
Separation logic provides a simple but powerful technique for reasoning about low-level imperative programs that use shared
data structures. Unfortunately, separation logic supports only “strong updates,” in which mutation to a heap location is safe
only if a unique reference is owned. This limits the applicability of separation logic when reasoning about the interaction
between many high-level languages (e.g., ML, Java, C#) and low-level ones since the high-level languages do not support strong
updates. Instead, they adopt the discipline of “weak updates,” in which there is a global “heap type” to enforce the invariant
of type-preserving heap updates. We present SL
w
, a logic that extends separation logic with reference types and elegantly reasons about the interaction between strong and
weak updates. We describe a semantic framework for reference types, which is used to prove the soundness of SL
w
. Finally, we show how to extend SL
w
with concurrency. 相似文献
3.
Transactional memory (TM) is an easy-using parallel programming model that avoids common problems associated with conventional
locking techniques. Several researchers have proposed a large amount of alternative hardware and software TM implementations.
However, few ones focus on formal reasoning about these TM programs. In this paper, we propose a framework at assembly level
for reasoning about lazy software transactional memory (STM) programs. First, we give a software TM implementation based on
lightweight locks. These locks are also one part of the shared memory. Then we define the semantics of the model operationally,
and the lightweight locks in transaction are non-blocking, avoiding deadlocks among transactions. Finally we design a logic
— a combination of permission accounting in separation logic and concurrent separation logic — to verify various properties
of concurrent programs based on this machine model. The whole framework is formalized using a proof-carrying-code (PCC) framework. 相似文献
4.
Specifications and programs make much use of nondeterministic and/or partial expressions, i.e. expressions which may yield
several or no outcomes for some values of their free variables. Traditional 2-valued logics do not comfortably accommodate
reasoning about undefined expressions, and do not cater at all for nondeterministic expressions. We seek to rectify this with
a 4-valued typed logic E4 which classifies formulae as either “true”, “false”, “neither true nor false”, or “possibly true, possibly false”. The logic
is derived in part from the 2-valued logic E and the 3-valued LPF, and preserves most of the theorems of E. Indeed, the main result is that nondeterminacy can be added to a logic covering partiality at little cost.
Received July 1996 / Accepted in revised form April 1998 相似文献
5.
Streamlining progress-based derivations of concurrent programs 总被引:1,自引:1,他引:0
The logic of Owicki and Gries is a well-known logic for verifying safety properties of concurrent programs. Using this logic,
Feijen and van Gasteren describe a method for deriving concurrent programs based on safety. In this work, we explore derivation
techniques of concurrent programs using progress-based reasoning. We use a framework that combines the safety logic of Owicki
and Gries, and the progress logic of UNITY. Our contributions improve the applicability of our earlier techniques by reducing
the calculational overhead in the formal proofs and derivations. To demonstrate the effectiveness of our techniques, a derivation
of Dekker’s mutual exclusion algorithm is presented. This derivation leads to the discovery of some new and simpler variants
of this famous algorithm.
Author Mooij performed this research at the Department of Mathematics and Computer Science of the Technische Universiteit
Eindhoven, while being supported by the NWO under project 016.023.015: “Improving the Quality of Protocol Standards”.
E. C. R. Hehner 相似文献
6.
Hume is a contemporary programming language oriented to systems with strong resource bounds, based on autonomous concurrent
“boxes” interacting across “wires”. Hume’s design reflects the explicit separation of coordination and computation aspects
of multi-process systems, which greatly eases establishing resource bounds for programs. However, coordination and computation
are necessarily tightly coupled in reasoning about Hume programs. Furthermore, in Hume, local changes to coordination or computation,
while preserving input/output correctness, can have profound and unforeseen effects on other aspects of programs such as timing
of events and scheduling of processes. Thus, traditional program calculi prove inappropriate as they tend to focus exclusively
either on the coordination of interacting processes or on computation within individual processes. 相似文献
7.
Vern R. Walker Nathaniel Carie Courtney C. DeWitt Eric Lesh 《Artificial Intelligence and Law》2011,19(4):291-331
This article describes the Vaccine/Injury Project Corpus, a collection of legal decisions awarding or denying compensation
for health injuries allegedly due to vaccinations, together with models of the logical structure of the reasoning of the factfinders
in those cases. This unique corpus provides useful data for formal and informal logic theory, for natural-language research
in linguistics, and for artificial intelligence research. More importantly, the article discusses lessons learned from developing
protocols for manually extracting the logical structure and generating the logic models. It identifies sub-tasks in the extraction
process, discusses challenges to automation, and provides insights into possible solutions for automation. In particular,
the framework and strategies developed here, together with the corpus data, should allow “top–down” and contextual approaches
to automation, which can supplement “bottom-up” linguistic approaches. Illustrations throughout the article use examples drawn
from the Corpus. 相似文献
8.
上世纪60-70年代以来,虽然有Floyd-Hoare逻辑的出现,但是使用形式化工具对命令式程序的正确性和可靠性进行自动验证一直被认为是极具挑战性、神圣不可及的工作.上世纪末由于更多的科研投入,特别是微软、IBM等大型公司研发部门的大量人力物力的投入,程序验证方面在本世纪初取得了不少进展,例如用于验证空客代码无运行时错误的ASTRÉE工具,用于Windows设备驱动里关于过程调用的协议验证的SLAM工具.但这些工具并没有考虑动态创建的堆(Heap):ASTRÉE工具假设待验证代码没有动态创建的堆,也没有递归;SLAM假设待验证系统已经有了内存安全性.事实上很多重要的程序,例如Linux内核、Apache、操作系统设备驱动程序等等,都涉及到对动态创建堆的操作.如何对这类操作堆的程序(heap-manipulating programs)进行自动验证仍然是个难题.2001-2002年分离逻辑(separation logic)提出后,其分离(separation)思想和相应的框(frame)规则使得局部推理(local reasoning)可以很好地应用到程序验证中.自2004年以来,基于分离逻辑对操作动态创建堆的程序进行自动验证方面的研究有了很大的进展,取得了很多令人瞩目的成果,例如SpaceInvader/Abductor、Slayer、HIP/SLEEK、CSL等工作.本文将着重对这方面的部分重要工作进行阐述. 相似文献
9.
The access control problem in computer security is fundamentally concerned with the ability of system entities to see, make
use of, or alter various system resources. We provide a mathematical framework for modelling and reasoning about (distributed)
systems with access control. This is based on a calculus of resources and processes together with a Hennessy–Milner-style
modal logic, based on the connectives of bunched logic, for which an appropriate correspondence theorem obtains. As a consequence
we get a consistent account of both operational behaviour and logical reasoning for systems with access control features.
In particular, we are able to introduce a process combinator that describes, as a form of concurrent composition, the action
of one agent in the role of another, and provide a logical characterization of this operator via a modality ‘says’. We give
a range of examples, including analyses of co-signing, roles, and chains of trust, which illustrates the utility of our mathematical
framework. 相似文献
11.
Masoud Nikravesh 《Soft Computing - A Fusion of Foundations, Methodologies and Applications》2008,12(2):207-214
Inspired by human’s remarkable capability to perform a wide variety of physical and mental tasks without any measurements
and computations and dissatisfied with classical logic as a tool for modeling human reasoning in an imprecise environment,
Lotfi A. Zadeh developed the theory and foundation of fuzzy logic with his 1965 paper “Fuzzy sets” (Zadeh in Inf Control 8:378–53,
1965) and extended his work with his 2005 paper “Toward a generalized theory of uncertainty (GTU)—an outline” (Zadeh in Inf
Control, 2005). Fuzzy logic has at least two main sources over the past century. The first of these sources was initiated
by Peirce in the form what he called a logic of vagueness in 1900s, and the second source is Lotfi’s A. Zadeh work, fuzzy
sets and fuzzy Logic in the 1960s and 1970s. 相似文献
12.
Argumentation theory is a new research area that concerns mainly with reaching a mutually acceptable conclusion using logical
reasoning. Argumentation can be defined as a proof of dynamic nature and is considered as an ill-defined domain that typically
lacks clear distinctions between “right” and “wrong” answers. Instead, there are often competing reasonable answers. Recently,
a number of argument mapping tools have been developed to diagram, articulate, and comprehend different arguments. Despite
the fact, these methods are of complementary nature, and the efforts for integrating these tools are missing. The purpose
of this paper is threefold: (1) revealing a novel approach for argument representation using a structured relational argument
database “RADB”, which has been designed, developed, and implemented in order to represent different argument analyses and
diagrams, (2) presenting a classifier agent that utilizes the RADB repository by using different mining techniques in order
to retrieve the most relevant arguments to the subject of search, and (3) proposing an agent-based educational environment
(ALES) that utilizes the RABD together with the classifier agent to teach argument analysis. 相似文献
13.
Arguing that intricate concurrent programs satisfy their specifications can be difficult; recording understandable explanations
is important for subsequent readers. Abstraction is a key tool even for sequential programs. The purpose here is to explore
some abstractions that help readers (and writers) understand the design of concurrent programs. As an illustration, the paper
presents a formal development of a non-trivial parallel program: Simpson’s implementation of asynchronous communication mechanisms.
Although the correctness of this “4-slot algorithm” has been shown elsewhere, earlier proofs fail to offer much insight into
the design. From an understandable (yet formal) design history of this one algorithm, the techniques employed in the explanation
are teased out for wider application. Among these techniques is using a “fiction of atomicity” as an aid to understanding
the initial steps of development. The rely-guarantee approach is, here, combined with notions of read/write frames and “phased”
specifications; furthermore, the atomicity assumptions implied by the rely/guarantee conditions are achieved by clever choice
of data representations. 相似文献
14.
Thomas Eiter Wolfgang Faber Michael Fink Stefan Woltran 《Annals of Mathematics and Artificial Intelligence》2007,51(2-4):123-165
Answer set programming is a declarative programming paradigm rooted in logic programming and non-monotonic reasoning. This
formalism has become a host for expressing knowledge representation problems, which reinforces the interest in efficient methods
for computing answer sets of a logic program. The complexity of various reasoning tasks for general answer set programming
has been amply studied and is understood quite well. In this paper, we present a language fragment in which the arities of
predicates are bounded by a constant. Subsequently, we analyze the complexity of various reasoning tasks and computational
problems for this fragment, comprising answer set existence, brave and cautious reasoning, and strong equivalence. Generally
speaking, it turns out that the complexity drops significantly with respect to the full non-ground language, but is still
harder than for the respective ground or propositional languages. These results have several implications, most importantly
for solver implementations: Virtually all currently available solvers have exponential (in the size of the input) space requirements
even for programs with bounded predicate arities, while our results indicate that for those programs polynomial space should
be sufficient. This can be seen as a manifestation of the “grounding bottleneck” (meaning that programs are first instantiated
and then solved) from which answer set programming solvers currently suffer. As a final contribution, we provide a sketch
of a method that can avoid the exponential space requirement for programs with bounded predicate arities.
Some results in this paper have been presented in preliminary form at KR 2004 [15]. 相似文献
15.
Yi -Dong Shen 《New Generation Computing》1997,15(2):187-203
The Equality check and the Subsumption check are weakly sound, but are not complete even for function-free logic programs.
Although the OverSize (OS) check is complete for positive logic programs, it is too general in the sense that it prunes SLD-derivations
merely based on the depth-bound of repeated predicate symbols and the size of atoms, regardless of the inner structure of
the atoms, so it may make wrong conclusions even for some simple programs. In this paper, we explore complete loop checking
mechanisms for positive logic programs. We develop an extended Variant of Atoms (VA) check that has the following features:
(1) it generalizes the concept of “variant” from “the same up to variable renaming” to “the same up to variable renaming except
possibly with some arguments whose size recursively increases”, (2) it makes use of the depth-bound of repeated variants of
atoms instead of depth-bound of repeated predicate symbols, (3) it combines the Equality/Subsumption check with the VA check,
(4) it is complete w. r. t. the leftmost selection rule for positive logic programs, and (5) it is more sound than both the
OS check and all the existing versions of the VA check.
The research was completed when the author visited the University of Maryland Institute for Advanced Computer Studies.
Yi-Dong Shen, Ph. D: He is a professor of Computer Science at Chongqing University, China. He received the Ph. D degree in computer Science from
Chongqing University in 1991. He was a visiting researcher at the University of Valenciennes, France (1992–1993) and the University
of Maryland Institute for Advanced Computer Studies (UMIACS), U. S. A. (1995–1996), respectively. His present interests include:
Artificial Intelligence, Deductive and Object-Oriented Databases, Logic Programming and Parallel Processing. 相似文献
16.
Temporal logics are commonly used for reasoning about concurrent systems. Model checkers and other finite-state verification
techniques allow for automated checking of system model compliance to given temporal properties. These properties are typically
specified as linear-time formulae in temporal logics. Unfortunately, the level of inherent sophistication required by these
formalisms too often represents an impediment to move these techniques from “research theory” to “industry practice”. The
objective of this work is to facilitate the nontrivial and error prone task of specifying, correctly and without expertise
in temporal logic, temporal properties.
In order to understand the basis of a simple but expressive formalism for specifying temporal properties we critically analyze
commonly used in practice visual notations. Then we present a scenario-based visual language called Property Sequence Chart
(PSC) that, in our opinion, fixes the highlighted lacks of these notations by extending a subset of UML 2.0 Interaction Sequence Diagrams. We also provide PSC with both denotational and operational semantics. The operational semantics is obtained via translation into Büchi automata
and the translation algorithm is implemented as a plugin of our Charmy tool. Expressiveness of PSC has been validated with respect to well known property specification patterns.
Preliminary results appeared in (Autili et al. 2006a). 相似文献
17.
并发程序的不变式验证对理解程序和提高程序的正确性具有重要意义.以一种区间时序逻辑程序设计语言Framed Tempura为研究对象,给出了该语言的等价正则形,定义了该正则形在相邻两个状态上的良基关系,进而利用良基归纳法原理对该语言所描述的系统的不变式进行归纳验证.提出的基于良基归纳法的验证方法在时序逻辑程序中可以方便地验证系统的不变式,尤其是循环结构的不变量性质. 相似文献
18.
We consider the problem of modeling and reasoning about statements of ordinal preferences expressed by a user, such as monadic
statement like “X is good,” dyadic statements like “X is better than Y,” etc. Such qualitative statements may be explicitly
expressed by the user, or may be inferred from observable user behavior. This paper presents a novel technique for efficient
reasoning about sets of such preference statements in a semantically rigorous manner. Specifically, we propose a novel approach
for generating an ordinal utility function from a set of qualitative preference statements, drawing upon techniques from knowledge
representation and machine learning. We provide theoretical evidence that the new method provides an efficient and expressive
tool for reasoning about ordinal user preferences. Empirical results further confirm that the new method is effective on real-world
data, making it promising for a wide spectrum of applications that require modeling and reasoning about user preferences. 相似文献
19.
Faisal Al-Saqqar Jamal Bentahar Khalid Sultan Mohamed El Menshawy 《Applied Intelligence》2014,41(1):235-259
Both knowledge and social commitments have received considerable attention in Multi-Agent Systems (MASs), specially for multi-agent communication. Plenty of work has been carried out to define their semantics. However, the relationship between social commitments and knowledge has not been investigated yet. In this paper, we aim to explore such a relationship from the semantics and model checking perspectives with respect to CTLK logic (an extension of CTL logic with modality for reasoning about knowledge) and CTLC logic (an extension of CTL with modalities for reasoning about commitments and their fulfillments). To analyze this logical relationship, we simply combine the two logics in one new logic named CTLKC. The purpose of such a combination is not to advocate a new logic, but only to express and figure out some reasoning postulates merging both knowledge and commitments as they are currently defined in the literature. By so doing, we identify some paradoxes in the new logic showing that simply combining current versions of commitment and knowledge logics results in a logical language that violates some fundamental intuitions. Consequently, we propose CTLKC+, a new logic that fixes the identified paradoxes and allows us to reason about social commitments and knowledge simultaneously in a consistent manner. Furthermore, we address the problem of model checking CTLKC+ by reducing it to the problem of model checking GCTL?, a generalized version of CTL? with action formulae. By doing so, we directly benefit from CWB-NC, the model checker of GCTL?. Using this reduction, we also prove that the computational complexity of model checking CTLKC+ is still PSPACE-complete for concurrent programs as the complexity of model checking CTLK and CTLC separately. 相似文献
20.
Salvatore Gaglio Luca Gatani Giuseppe Lo Re Alfonso Urso 《Journal of Network and Systems Management》2006,14(1):127-146
This paper focuses on improving network management by exploiting the potential of “doing” of the Active Networks technology, together with the potential of “planning,” which is typical of the artificial intelligent systems. We propose a distributed multiagent architecture for Active Network management, which exploits the dynamic reasoning capabilities of the Situation Calculus in order to emulate the reactive behavior of a human expert to fault situations. The information related to network events is generated by programmable sensors deployed across the network. A logical entity collects this information, in order to merge it with general domain knowledge, with a view to identifying the root causes of faults, and to deciding on reparative actions. The logical inference system has been devised to carry out automated isolation, diagnosis, and even repair of network anomalies, thus enhancing the reliability, performance, and security of the network. Experimental results illustrate the Reasoner capability of correctly recognizing fault situations and undertaking management actions. 相似文献