641.
Solving Cardinality Constraints in (Constraint) Logic Programming
- Dietmar Seipel; Ulrich Geske
We investigate cardinality constraints of the form M ,! K, where M is a set and is one of the comparison operators \=, ", or \": a model of such a constraint is required to contain \exactly, at most", or \at least", respectively, K elements of M . Applications dealing with cardinality constraints may for instance arise in assignment problems, such as course planning , or in games : E.g. there may be rules like \every student has to take 3 of the courses of a given set M". We present a calculus represented by a denite logic program, which...
642.
Three-Valued Semantics for Extended Logic Programs
- Piero A. Bonatti; Laura Giordano
In [4] , the semantics of monotonic (i.e. not -free) extended logic programs (ELPs) has been rephrased in three-valued logic for two purposes: achieving tractable reasoning with incomplete information and understanding the relationships between the existing semantics and many-valued logics. In this paper, we generalize this approach to unrestricted ELPs. We obtain a unifying view of many formalisms, including the answer set semantics, the well-founded semantics, generalized stable models (as in [11]), default logic, autoepistemic logic (AEL) and some of its variants (three-valued AEL and Schwartz's reflexive AEL) . Our framework highlights surprising similarities between previously unrelated formalisms, such as...
643.
Demand-driven Search in Functional Logic Programs
- Pierre Rety; Michael Hanus; Michael Hanus
In this paper we discuss the advantage of lazy functional logic languages to solve search problems. We show that the lazy evaluation strategy of such languages can be easily exploited to implement a solver that explores only the dynamically demanded parts of the search space. In contrast to pure logic programming, the use of nondeterministic functions enables a modular and simple implementation without the risk of floundering. Furthermore, a local encapsulation of search is useful to avoid the combinatorial explosion of the demanded search space. The necessary features (laziness, non-deterministic functions, encapsulated search) are available in Curry, a new declarative...
644.
A Logic for Reasoning about Time and Reliability
- Hans Hansson; Bengt Jonsson
We present a logic for stating properties such as, "after a request for service there is at least a 98% probability that the service will be carried out within 2 seconds". The logic extends the temporal logic CTL by Emerson, Clarke and Sistla with time and probabilities. Formulas are interpreted over discrete time Markov chains. We give algorithms for checking that a given Markov chain satisfies a formula in the logic. The algorithms require a polynomial number of arithmetic operations, in size of both the formula and This research report is a revised and extended version of a paper that...
645.
DILL: Specifying Digital Logic in LOTOS
- Kenneth J. Turner; Paul D. Amer; M. Umit Uyar; K. J. Turner; Richard O. Sinnott
Data Type) operations on input values. However, the time-dependent behaviour of logic circuits is often important, so it is better to use LOTOS behaviour expressions. More importantly, a specification using ADTs would not readily support `wiring up' a circuit. Each logic gate is therefore specified as a LOTOS process, instantiated with appropriate parameters. A real logic gate exhibits a propagation delay from a change in input to the subsequent output. This appears naturally in a LOTOS specification since output events follow input events. However, the actual time delay between such events is not modelled in LOTOS. For many purposes the...
646.
Proof Procedures for Branching-Time Logic Programs
- M. Gergatsoulis; P. Rondogiannis; T. Panayiotopoulos
Traditional implementation techniques for temporal logic programming languages are based on the notion of canonical temporal atoms/clauses. Although such an approach is satisfactory for proving goals that refer to specific moments in time, it usually leads to non-terminating computations when considering open-ended goals. In this paper, we propose a new generalized proof procedure for implementing branching time logic programming languages. The particular strength of the new proof procedure, called CSLD-resolution, is that it can handle in a more general way openended queries, without the need of enumerating all their canonical instances. Keywords: Temporal Logic Programming, Branching Time, Proof Procedures. 1...
647.
DisLoP: A Research Project on Disjunctive Logic Programming
- Chandrabose Aravindan; Jürgen Dix; Rabose Aravindan; J Urgen Dix; Ilkka Niemelä
This paper gives a brief high-level description of what has been done in the Disjunctive Logic Programming-project (funded by Deutsche Forschungs-Gemeinschaft), undertaken by the University of Koblenz since July 1995. We present the main ideas, cite the relevant papers and point to the implemented systems and how to access them. This paper also serves as a brief survey of the current status of disjunctive logic programming by highlighting important developments and providing enough pointers for further reading.
648.
Binding Logic: proofs and models
- Gilles Dowek
We de
ne an extension of predicate logic, called Binding
Logic, where variables can be bound in terms and in propositions. We
introduce a notion of model for this logic and we prove a completeness
theorem for it. This theorem is obtained as a consequence of the completeness
theorem of predicate logic, by encoding this logic back into
predicate logic.
649.
A Semantics for a Logic of Authentication
Burrows, Abadi, and Needham have proposed a logic for the analysis of authentication protocols. It is a logic of belief, with special constructs for expressing some of the central concepts used in authentication. The logic has revealed many subtleties and serious errors in published protocols. Unfortunately, it has also created some confusion. In this paper, we provide a new semantics for the logic, our attempt to clarify its meaning. In the search for a sound semantics, we have identified many sources of the past confusion. Identifying these sources has helped us improve the logic's syntax and inference rules, and extend...
650.
Artificial Reasoning with Subjective Logic
. This paper defines a framework for artificial reasoning called
Subjective Logic, which consists of a belief model called opinion and set
of operations for combining opinions. Subjective Logic is an extension
of standard logic that uses continuous uncertainty and belief parameters
instead of only discrete truth values. It can also be seen as an extension
of classical probability calculus by using a second order probability representation
instead of the standard first order representation. In addition
to the standard logical operations, Subjective Logic contains some operations
specific for belief theory such as consensus and recommendation. In
particular, we show that Dempster's consensus rule is inconsistent with
Bayes' rule and therefore...
651.
The Logic of Bunched Implications
We introduce a logic BI in which a multiplicative (or linear) and an additive (or intuitionistic) implication
live side-by-side. The propositional version of BI arises from an analysis of the proof-theoretic
relationship between conjunction and implication; it can be viewed as a merging of intuitionistic logic
and multiplicative intuitionistic linear logic. The naturality of BI can be seen categorically: models of
propositional BI's proofs are given by bicartesian doubly closed categories, i.e., categories which freely
combine the semantics of propositional intuitionistic logic and propositional multiplicative intuitionistic
linear logic. The predicate version of BI includes, in addition to standard additive quantifiers, multiplicative
(or intensional) quantifiers 8new and 9new...
652.
A Semantics for a Logic of Authentication
)
Mart'in Abadi
Digital Equipment Corporation
Systems Research Center
130 Lytton Avenue
Palo Alto, CA 94301
ma@src.dec.com
Mark R. Tuttle
Digital Equipment Corporation
Cambridge Research Lab
One Kendall Square, Bldg. 700
Cambridge, MA 02139
tuttle@crl.dec.com
Abstract: Burrows, Abadi, and Needham have proposed
a logic for the analysis of authentication protocols.
It is a logic of belief, with special constructs for
expressing some of the central concepts used in authentication.
The logic has revealed many subtleties
and serious errors in published protocols. Unfortunately,
it has also created some confusion.
In this paper, we provide a new semantics for
the logic, our attempt to clarify its meaning. In
the search for a sound semantics, we have identified
many sources of the past confusion. Identifying these
sources...
653.
Artificial Reasoning with Subjective Logic
. This paper defines a framework for artificial reasoning called
Subjective Logic, which consists of a belief model called opinion and set
of operations for combining opinions. Subjective Logic is an extension
of standard logic that uses continuous uncertainty and belief parameters
instead of only discrete truth values. It can also be seen as an extension
of classical probability calculus by using a second order probability representation
instead of the standard first order representation. In addition
to the standard logical operations, Subjective Logic contains some operations
specific for belief theory such as consensus and recommendation. In
particular, we show that Dempster's consensus rule is inconsistent with
Bayes' rule and therefore...
654.
The Logic of Bunched Implications
We introduce a logic BI in which a multiplicative (or linear) and an additive (or intuitionistic) implication
live side-by-side. The propositional version of BI arises from an analysis of the proof-theoretic
relationship between conjunction and implication; it can be viewed as a merging of intuitionistic logic
and multiplicative intuitionistic linear logic. The naturality of BI can be seen categorically: models of
propositional BI's proofs are given by bicartesian doubly closed categories, i.e., categories which freely
combine the semantics of propositional intuitionistic logic and propositional multiplicative intuitionistic
linear logic. The predicate version of BI includes, in addition to standard additive quantifiers, multiplicative
(or intensional) quantifiers 8new and 9new...
655.
A Semantics for a Logic of Authentication
)
Mart'in Abadi
Digital Equipment Corporation
Systems Research Center
130 Lytton Avenue
Palo Alto, CA 94301
ma@src.dec.com
Mark R. Tuttle
Digital Equipment Corporation
Cambridge Research Lab
One Kendall Square, Bldg. 700
Cambridge, MA 02139
tuttle@crl.dec.com
Abstract: Burrows, Abadi, and Needham have proposed
a logic for the analysis of authentication protocols.
It is a logic of belief, with special constructs for
expressing some of the central concepts used in authentication.
The logic has revealed many subtleties
and serious errors in published protocols. Unfortunately,
it has also created some confusion.
In this paper, we provide a new semantics for
the logic, our attempt to clarify its meaning. In
the search for a sound semantics, we have identified
many sources of the past confusion. Identifying these
sources...
656.
A Semantics for a Logic of Authentication
)
Mart'in Abadi
Digital Equipment Corporation
Systems Research Center
130 Lytton Avenue
Palo Alto, CA 94301
ma@src.dec.com
Mark R. Tuttle
Digital Equipment Corporation
Cambridge Research Lab
One Kendall Square, Bldg. 700
Cambridge, MA 02139
tuttle@crl.dec.com
Abstract: Burrows, Abadi, and Needham have proposed
a logic for the analysis of authentication protocols.
It is a logic of belief, with special constructs for
expressing some of the central concepts used in authentication.
The logic has revealed many subtleties
and serious errors in published protocols. Unfortunately,
it has also created some confusion.
In this paper, we provide a new semantics for
the logic, our attempt to clarify its meaning. In
the search for a sound semantics, we have identified
many sources of the past confusion. Identifying these
sources...
657.
Ground Temporal Logic: A Logic for Hardware Verification
- David Cyrluk,Paliath Narendran
We present a new temporal logic, GTL, appropriate for specifying properties of hardware
at the register transfer level. We argue that this logic represents an improvement over model
checking for some natural hardware verification problems. We show that the validity problem
for this logic is Pi
1
1 complete. We then identify a fragment of the logic that is decidable. We
show that in this fragment we are still able to encode many interesting problems, including the
correctness of pipelined microprocessors.
1 Introduction
Temporal logic is a natural logic for hardware verification. Specifically model checking for various
propositional temporal logics has proven to be a very practical tool for the...
658.
Ground Temporal Logic: A Logic for Hardware Verification
- David Cyrluk,Paliath Narendran
We present a new temporal logic, GTL, appropriate for specifying properties of hardware
at the register transfer level. We argue that this logic represents an improvement over model
checking for some natural hardware verification problems. We show that the validity problem
for this logic is Pi
1
1 complete. We then identify a fragment of the logic that is decidable. We
show that in this fragment we are still able to encode many interesting problems, including the
correctness of pipelined microprocessors.
1 Introduction
Temporal logic is a natural logic for hardware verification. Specifically model checking for various
propositional temporal logics has proven to be a very practical tool for the...
659.
Ground Temporal Logic: A Logic for Hardware Verification
- David Cyrluk,Paliath Narendran
We present a new temporal logic, GTL, appropriate for specifying properties of hardware
at the register transfer level. We argue that this logic represents an improvement over model
checking for some natural hardware verification problems. We show that the validity problem
for this logic is Pi
1
1 complete. We then identify a fragment of the logic that is decidable. We
show that in this fragment we are still able to encode many interesting problems, including the
correctness of pipelined microprocessors.
1 Introduction
Temporal logic is a natural logic for hardware verification. Specifically model checking for various
propositional temporal logics has proven to be a very practical tool for the...
660.
Towards a Logic for Reasoning about Logic Programs Transformation
- Alberto Momigliano
We give a proof-theoretic analysis of logic programs transformations,
viewed as operations on proof trees in the sense of [3, 4, 9, 10].
We present a logic for reasoning about (equivalence preserving) transformations
of logic programs. Our main tool is the usage of inference rules;
the target program may be obtained as a set of clause introduction proofs
with axioms from the source program. The rules are admissible, that is
every proof according to the latter can be translated back in a derivation
of the same consequence built from the source program without those
rules. In this formal setting, we give a general schema for program transformation
analysis, which...
