321.
A Specification Logic for Mobility
We present MSL, a specification logic for generic concurrent open systems with Milner-style mobility. MSL draws its expressiveness from the integration of certain operators expressing component distribution and name scoping into a first-order many-sorted logic of actions with fixed-points. MSL semantics is presented in terms of a class of generic structures, allowing its application to diverse concrete computational models, for instance process calculi and systems of mobile objects. We will also show how MSL supports reasoning about interesting aspects of such systems, like structure, creation of new entities, local names, and their dynamics.
322.
.2 Classical Logic
potheses and their restrictions are critical for linear logic, we give here a
formulation of natural deduction for intuitionistic logic with localized hypotheses,
but not parameters. For this we need a notation for hypotheses which we
call a context.
Contexts Gamma ::= Delta j Gamma; u:A
Here, "Delta" represents the empty context, and Gamma; u:A adds hypothesis ` A labelled
u to Gamma. We assume that each label u occurs at most once in a context in order
to avoid ambiguities. The main judgment can then be written as Gamma ` A, where
Delta; u 1 :A 1 ; : : : ; un :An ` A
stands for
u...
323.
Towards a hybrid dynamic logic for hybrid dynamic systems
- André Platzer
We introduce a hybrid variant of a dynamic logic with continuous state transitions along differential equations, and we present a sequent calculus for this extended hybrid dynamic logic. With the addition of satisfaction operators, this hybrid logic provides improved system introspection by referring to properties of states during system evolution. In addition to this, our calculus introduces state-based reasoning as a paradigm for delaying expansion of transitions using nominals as symbolic state labels. With these extensions, our hybrid dynamic logic advances the capabilities for compositional reasoning about (semialgebraic) hybrid dynamic systems. Moreover, the constructive reasoning support for goal-oriented analytic verification...
324.
Reasoning With Partially Ordered Information in a Possibilistic Logic Framework
- Salem Benferhat; Sylvain Lagrue; Odile Papini
Possibilistic logic o#ers a natural qualitative framework for handling uncertain information. This paper discusses its extension to dealing with partially ordered knowledge.
325.
Properties of Prioritized Logic Programs
- Yan Zhang
. Prioritized logic programming has illustrated its rich expressiveness and flexibility in knowledge representation and reasoning. However, some important aspects of prioritized logic programs have yet to be thoroughly explored. In this paper, we investigate several properties of prioritized logic programs in the context of answer set semantics. Specifically, we propose a characterization on the uniqueness of answer set for prioritized logic programs. We then prove two splitting theorems for prioritized logic programs so that under proper conditions, the evaluation of a prioritized logic program can be reduced to the evaluation of some separate "components" of the program. keywords: foundation...
326.
Parallel Logic Programs on the Mayfly
- John S. Conery
Abstract. The Mayfly, a parallel processor being built at HP Labs in Palo Alto, has architectural support for several important aspects of the OM virtual machine for parallel logic programs. Each node has an extra processor that is able to relieve the main processor of a significant amount of the “housekeeping ” work of memory management, task switching, and message handling. This paper describes how the second processor implements kernel level functions in OM, with particular attention to the operations that support task switching and task allocation. The paper includes detailed timing data from a program with interleaved parallel threads...
327.
A Dynamic Logic for Acting, Sensing, and Planning
- Luca Spalazzi; Paolo Traverso
This paper is a first attempt towards a theory for reactive planning systems, i.e. systems able to plan and control execution of plans in a partially known and unpredictable environment. We start from an experimental real world application developed at IRST, discuss some of the fundamental requirements and propose a formal theory based on these requirements. The theory takes into account the following facts: (1) actions may fail, since they correspond to complex programs controlling sensors and actuators which have to work in an unpredictable environment; (2) actions need to acquire information from the real world by activating sensors and...
328.
Verifying Probabilistic Programs Using A Hoare Like Logic
- J. I. Den Hartog; E. P. De Vink
Probability, be it inherent or explicitly introduced, has become an important issue in the verification of programs. In this paper we study a formalism which allows reasoning about programs which can act probabilistically. To describe probabilistic programs, a basic programming language with an operator for probabilistic choice is introduced and a denotational semantics is given for this language. To specify properties of probabilistic programs, standard first order logic predicates are insufficient, so a notion of probabilistic predicates is introduced. A Hoare-style proof system to check properties of probabilistic programs is given. The proof system for a sublanguage is shown to...
329.
Logic Programming Techniques for Solving Circuit Diagnosis
- J. J. Alferes; F. Azevedo; P. Barahona; C. V. Damasio; T. Swift
Model-based diagnosis is a general technique of Artificial Intelligence that has applications to engineering design, networking, planning, and other domains. These applications have led to the creation of special-purpose systems for model-based diagnosis, based on theories of truth maintenance. In this paper we focus on circuit diagnosis, and consider several logic programming approaches, which in contrast to the special-purpose systems, require very small amounts of code, yet are often quite efficient. As a basis for comparison, we start generate and test algorithms. Next, we model faults as abducibles, and the abductive program is evaluated using tabling. As an alternative to...
330.
Fuzzy Logic Connectivity in Semiconductor Defect Clustering
- Thomas Karnowski Shaun; Shaun S. Gleason; Kenneth W. Tobin
In joining defects on semiconductor wafer maps into clusters, it is common for defects caused by different sources to overlap. Simple morphological image processing tends to either join too many unrelated defects together or not enough together. Expert semiconductor fabrication engineers have demonstrated that they can easily group clusters of defects from a common manufacturing problem source into a single signature. Capturing this thought process is ideally suited for fuzzy logic. A system of rules was developed to join disconnected clusters based on properties such as elongation, orientation, and distance. The clusters are evaluated on a pair-wise basis using the...
331.
Automated Protocol Verification in Linear Logic
- Marco Bozzano; Giorgio Delzanno
In this paper we investigate the applicability of a bottom-up evaluation strategy for a first order fragment of linear logic [7] for the purposes of automated validation of authentication protocols. Following [11], we use multi-conclusion clauses to represent the behaviour of agents in a protocol session, and we adopt the Dolev-Yao intruder model and related message and cryptographic assumptions. Also, we use universal quantification to provide a logical and clean way to express creation of nonces. Our approach is well suited to verify properties which can be specified by means of minimality conditions. Unlike traditional approaches based on model-checking, we...
332.
A ‘Natural Logic ’ inference system using the Lambek
- Anna Zamansky; Nissim Francez; Yoad Winter
This paper develops an inference system for natural language within the ‘Natural Logic ’ paradigm as advocated by Van Benthem [11], Sánchez [10] and others. The system that we propose is based on the Lambek calculus and works directly on the Curry-Howard counterparts for syntactic representations of natural language, with no intermediate translation to logical formulae. The Lambek-based system we propose extends the system by Fyodorov et al. [3], which is based on the Ajdukiewicz/Bar-Hillel (AB) calculus ([6]). This enables the system to deal with new kinds of inferences, involving relative clauses, non-constituent coordination, and meaning postulates that involve complex...
333.
Tableau-based decision procedures for hybrid logic
- Thomas Bolander; Torben; Bra Üner
Abstract. Hybrid logics are a principled generalization of both modal logics and description logics. It is well-known that various hybrid logics without binders are decidable, but decision procedures are usually not based on tableau systems, a kind of formal proof procedure that lends itself towards computer implementation. In this paper we give four different tableaubased decision procedures for a very expressive hybrid logic including the universal modality; three of the procedures are based on different tableau systems, and one procedure is based on a Gentzen system. The decision procedures make use of so-called loop-checks which is a technique standardly used...
334.
exists-Universal Termination of Logic Programs
- Salvatore Ruggieri
We introduce the notion of 9-universal termination of logic programs. A program P and a goal G 9-universally terminate iff there exists a selection rule S such that every SLD-derivation of P [ fGg via S is finite. We claim that it is an essential concept for declarative programming, where a crucial point is to associate a terminating control strategy to programs and goals. We show that 9-universal termination and universal termination via fair selection rules coincide. Then we offer a characterization of 9-universal termination by defining fair-bounded programs and goals. They provide us with a correct and complete method...
335.
Under consideration for publication in Theory and Practice of Logic Programming 1 Logic programs with monotone abstract constraint atoms∗
- Victor W. Marek; Ilkka Niemelä
We introduce and study logic programs whose clauses are built out of monotone constraint atoms. We show that the operational concept of the one-step provability operator generalizes to programs with monotone constraint atoms, but the generalization involves nondeterminism. Our main results demonstrate that our formalism is a common generalization of (1) normal logic programming with its semantics of models, supported models and stable models, (2) logic programming with weight atoms (lparse programs) with the semantics of stable models, as defined by Niemelä, Simons and Soininen, and (3) of disjunctive logic programming with the possible-model semantics of Sakama and Inoue.
336.
Constraint Logic Programming
Contents
1 Introduction 5
2 Logical Theories 7
2.1 First-Order Languages . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2 Mathematical Structures . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.3 Proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.4...
337.
Vagueness-Adaptive Logic:
This paper defends a pragmatical approach to vagueness. The vaguenessadaptive
logic VAL is a good reconstruction of and an excellent instrument for human
reasoning processes in which vague predicates are involved. Apart from its proof-theory
and semantics, a Sorites-treating model based on it is presented, disarming the paradox.
The paper opens perspectives with respect to the construction of theories by means of
vague predicates.
338.
Subprevarieties Versus Extensions. Application to the Logic of Paradox
- Pynko, Alexej P.
In the present paper we prove that the poset of all extensions of the logic defined by a class of matrices whose sets of distinguished values are equationally definable by their algebra reducts is the retract, under a Galois connection, of the poset of all subprevarieties of the prevariety generated by the class of the algebra reducts of the matrices involved. We apply this general result to the problem of finding and studying all extensions of the logic of paradox (viz., the implication-free fragment of any non-classical normal extension of the relevance-mingle logic). In order to solve this problem, we...
339.
Independent choices and the interpretation of IF logic
- Theo M. V. Janssen
In this paper it is argued that Hintikka's game theoretical semantics for Independence Friendly logic does not formalize the intuitions about independent choices; it rather is a formalization of imperfect information. Furthermore it is shown that the logic has several strange properties. An alternative semantics is proposed which formalizes intuitions about independence.
340.
Discrete (Set) Derivatives and "Algebraic" Fuzzy Logic Operations
- Bernadette Bouchon-Meunier Hung; Vladik Kreinovich
We propose a new way to generalize logical operations from the discrete classical logic to a continuous fuzzy logic; namely, we propose to define derivatives for discrete case, and then to use these derivatives to derive the continuous operations. We show that this natural approach leads to "algebraic" fuzzy operations a \Delta b and a + b \Gamma a \Delta b. 1
