501.
A Brief Guide to Linear Logic
An overview of linear logic is given, including an extensive bibliography
and a simple example of the close relationship between linear
logic and computation.
1 Overview
Linear logic, introduced by Girard [45], is a refinement of classical logic.
Linear logic is sometimes described as resource sensitive because it provides
an intrinsic and natural accounting of resources. This is indicated by the
fact that in linear logic, two assumptions of a formula A are distinguished
from a single assumption of A. Informally, on the level of basic intuition, one
might say that classical logic is about truth, that intuitionistic logic is about
construction of proofs, and that linear logic is about...
502.
Contextual Deontic Logic
- Yao-hua Tan
In this article we propose contextual deontic logic (CDL). Contextual obligations are written as O(ffjfinfl), and are to be read as `ff should be the case if fi is the case, unless fl is the case'. The unless clause is analogous to the justification in Reiter's default rules. We show how contextual obligations can be used to solve certain aspects of contrary-to-duty paradoxes of dyadic deontic logic.
503.
A Fuzzy Logic Model of Visual Importance for Efficient Image Synthesis
- Brown, Ross A.; Pham, Binh L.; Maeder, Anthony J.
Experiments have shown that viewers only regard certain informative regions within a presented image. Furthermore, it has been shown that these regions of interest contain low level feature differences that influence the fixation time of the viewer. In this paper we present a novel fuzzy logic model of visual attention which seeks to compute the relative visual importance of regions in an image based upon these spatial feature differences. We also demonstrate some of the possible savings to be had in applying the visual importance model to the modulation of super-sampling in a ray-traced image. We expect this approach to...
504.
A Conservative Technique to Improve Deterministic Evaluation of Logic Programs
- Roychoudhury Ramakrishnan Ramakrishnan; A. Roychoudhury; C. R. Ramakrishnan; I. V. Ramakrishnan; R. Sekar
The performance of logic programs can be significantly improved by reducing nondeterminism in their evaluation using techniques for early pruning of computation paths that would eventually fail. Using static information gleaned from the program, we can identify (simple) conditions that must hold for certain computation paths to succeed, and test them before searching along those paths. However, naive introduction of such tests can actually lead to performance degradation since tests may be repeated along a branch, and also because the tests themselves may create additional choice points. We therefore develop a program transformation algorithm that enables us to introduce only...
505.
On the Role of Negation in Choice Logic Programs
- Marina De Vos; Dirk Vermeir
We introduce choice logic programs as negation-free datalog programs that allow rules to have exclusive-only (possibly empty) disjunctions in the head. Such programs naturally model decision problems where, depending on a context, agents must make a decision, i.e. an exclusive choice out of several alternatives. It is shown that such a choice mechanism is in a sense equivalent with negation as supported in semi-negative datalog programs. We also discuss an application where strategic games can be naturally formulated as choice programs: it turns out that the stable models of such programs capture exactly the set of Nash equilibria. We then...
506.
An Expectation-Transformer Model for Probabilistic Temporal Logic
- Carroll Morgan; Carroll Morgan; Annabelle McIver; Annabelle Mciver
We reinterpret the modal ¯-calculus [16] to act over expectations rather than predicates, where expectations generalise predicates by taking states into the interval [0; 1] rather than the two-point set f0; 1g; our interest is in the idioms of the ¯-calculus that correspond to operators of temporal logic, in particular in establishing reasoning principles for them. Our model includes both probabilistic and demonic choice, and the interpretation exploits the characterisation [20] of probabilistic healthiness for expectation transformers to determine the algebraic properties of probabilistic next, and thence those of the other probabilistic temporal operators. The results confirm that many nonprobabilistic...
507.
Domain Construction for Mode Analysis of Typed Logic Programs
- Jan-Georg Smaus; Pat Hill; Andy King
There are many applications where precise mode analysis is required. However, within the framework of abstract interpretation, the precision of an analyser depends, in part, on the expressiveness of the abstract domain and its associated abstraction function. This paper considers abstract domains for polymorphically typed logic programs where each nonvariable symbol is explicitly typed. We show how to construct precise domains and their abstraction functions that reflect the declared structure of terms. This domain construction is modular in that an abstract domain for a type does not depend on modules that import this type. A program is abstracted by replacing...
508.
Esfandiar Mohammadi Dual Light Affine Logic Outline
- Esfandiar Mohammadi; Introduction Dual; Light Affine Logic(dlal
DLAL: a stratified logic Bound for weak normalization Expressiveness of DLAL
509.
The Hanf numbers of stationary logic. II. Comparison with other logics
- Shelah, Saharon
We show that the ordering of the Hanf number of L_{omega, omega}(wo) (well
ordering), L^c_{omega, omega} (quantification on countable sets), L_{omega,
omega}(aa) (stationary logic) and second order logic, have no more restraints
provable in ZFC than previously known (those independence proofs assume
CON(ZFC) only). We also get results on corresponding logics for L_{lambda, mu}
.
510.
Alboran is and is not dry: Katalin Havas on Logic and Dialectics
- Peña, Lorenzo
[EN] In her book Logic and Dialectic: Essays in the Philosophy of Logic
Katalin Havas broaches the relationship between logic and the idea of
true contradictions ingrained in the dialectical tradition which
comprised at least some of the main Marxist thinkers. She thinks that,
whatever the utility of non-classical logical systems, in the main
dialectics does not need them, since it is wholly compatible with
Aristotelian logic.
The current paper goes into the relationship between degrees and
contradictions. Havas thinks that any inconsistency implied by the
recognition of degrees is apparent. I show that in virtue of broadly
accepted logical...
511.
Implementation and Development Issues for the Linear Logic Programming Language Lygon
- Michael Winikoff; James Harland
We describe and discuss the implementation of a new logic programming language called Lygon. This language is based on linear logic, a logic designed with bounded resources in mind. Linear logic may be thought of as a generalisation of classical logic, and as a result Lygon contains various features which do not exist in (pure) Prolog, whilst maintaining all the features of (pure) Prolog. In this paper we describe the implementation of this language, which posed a variety of programming challenges. The operational model for the language is based on the notion of goal-directed provability, a notion which has been...
512.
Modeling, Analysis, And Implementation Of Logic Controllers For Machining Systems Using Petri Nets And Sfc
- Euisu Park; Dawn M. Tilbury; Pramod P. Khargonekar
The logic control for high-volume machiningsysteE such asthe transfe line commonlyuse inthe automotive manufacturing industry, must achie e multiple functions in distinct control mode and thus isquite comple Ame dology for constructingthe logic controlle using Pe ne isoutlineE Each ope inthe machining syste isassigne es the are e orirre ere opeE module and an algorithm for conneE- then module to formthe control logic ispre te The reE logic controlle is guaranter to be live safe and reeE The logic controlle can be impleE te in SFC. Introduction Transfer lines are widely used in the automotive and other highvolume industries. In...
513.
Implementation and development Issues for the Linear Logic Programming Language Lygon
- Michael Winikoff; James Harland
We describe and discuss the implementation of a new logic programming language called Lygon. This language is based on linear logic, a logic designed with bounded resources in mind. Linear logic may be thought of as a generalisation of classical logic, and as a result Lygon contains various features which do not exist in (pure) Prolog, whilst maintaining all the features of (pure) Prolog. In this paper we describe the implementation of this language, which posed a variety of programming challenges. The operational model for the language is based on the notion of goal-directed provability, a notion which has been...
514.
Constraint Logic Programming with Dynamic Scheduling: A Semantics Based on Closure Operators
- Moreno Falaschi; Maurizio Gabbrielli; Kim Marriott; Catuscia Palamidessi
The first logic programming languages, such as Prolog, used a fixed left-to-right atom scheduling rule. Recent logic programming languages, however, provide more flexible scheduling in which there is a default computation rule such as left-to-right but in which some calls are dynamically "delayed" until their arguments are sufficiently instantiated to allow the call to run efficiently. Such languages include constraint logic programming languages, since most implementations of these languages delay constraints which are "too hard." From the semantic point of view, the fact that an atom must be delayed under certain conditions, causes the standard semantics of (constraint) logic programming...
515.
Implementation and development Issues for the Linear Logic Programming Language Lygon
- Michael Winikoff; James Harland
We describe and discuss the implementation of a new logic programming language called Lygon. This language is based on linear logic, a logic designed with bounded resources in mind. Linear logic may be thought of as a generalisation of classical logic, and as a result Lygon contains various features which do not exist in (pure) Prolog, whilst maintaining all the features of (pure) Prolog. In this paper we describe the implementation of this language, which posed a variety of programming challenges. The operational model for the language is based on the notion of goal-directed provability, a notion which has been...
516.
Dynamic logic with non-rigid functions: A basis for object-oriented program verification
- Bernhard Beckert; André Platzer
Abstract. We introduce a dynamic logic that is enriched by non-rigid functions, i.e., functions that may change their value from state to state (during program execution), and we present a (relatively) complete sequent calculus for this logic. In conjunction with dynamically typed object enumerators, non-rigid functions allow to embed notions of objectorientation in dynamic logic, thereby forming a basis for verification of object-oriented programs. A semantical generalisation of substitutions, called state update, which we add to the logic, constitutes the central technical device for dealing with object aliasing during function modification. With these few extensions, our dynamic logic captures the...
517.
Implementation and Development Issues for the Linear Logic Programming Language Lygon
- Michael Winiko; James Harland
We describe and discuss the implementation of a new logic programming language called Lygon. This language is based on linear logic, a logic designed with bounded resources in mind. Linear logic may be thought of as a generalisation of classical logic, and as a result Lygon contains various features which do not exist in (pure) Prolog, whilst maintaining all the features of (pure) Prolog. In this paper we describe the implementation of this language, which posed a variety of programming challenges. The operational model for the language is based on the notion of goal-directed provability, a notion which has been...
518.
Dynamic logic with non-rigid functions: A basis for object-oriented program verification
- Bernhard Beckert; André Platzer
Abstract. We introduce a dynamic logic that is enriched by non-rigid functions, i.e., functions that may change their value from state to state (during program execution), and we present a (relatively) complete sequent calculus for this logic. In conjunction with dynamically typed object enumerators, non-rigid functions allow to embed notions of objectorientation in dynamic logic, thereby forming a basis for verification of object-oriented programs. A semantical generalisation of substitutions, called state update, which we add to the logic, constitutes the central technical device for dealing with object aliasing during function modification. With these few extensions, our dynamic logic captures the...
519.
Implementation and development Issues for the Linear Logic Programming Language Lygon
- Michael Winikoff; James Harland
We describe and discuss the implementation of a new logic programming language called Lygon. This language is based on linear logic, a logic designed with bounded resources in mind. Linear logic may be thought of as a generalisation of classical logic, and as a result Lygon contains various features which do not exist in (pure) Prolog, whilst maintaining all the features of (pure) Prolog. In this paper we describe the implementation of this language, which posed a variety of programming challenges. The operational model for the language is based on the notion of goal-directed provability, a notion which has been...
520.
Constructor-based Observational Logic
- Observational Logic; Ecole Normale; Suprieure Cachan; M. Bidoit; R. Hennicker
This paper focuses on the integration of reachability and observability concepts within an algebraic, institution-based framework. In the first part of this work, we develop the essential ingredients that are needed to define the constructorbased observational logic institution, called COL, which takes into account both the generation- and observation-oriented aspects of software systems. The underlying paradigm of our approach is that the semantics of a specification should be as loose as possible to capture all its correct realizations. We also consider the "black box" semantics of a specification which is useful to study the behavioral properties a user can observe...
