141.
"No Collision" in a Protocol with n Stations: a Comparative Study of Formal Proofs
- Agathe Merceron,Monika Mullerburg,G. Michele Pinna
. Formal methods are used both for designing a system and
for checking that it satisfies required properties. To prove that a finite
system matches its specification, a common line of thought is to express
properties in a suitable temporal logic, and with a model checker, automatically
verify that the system satisfies them. However this method
does not work straightaway for systems composed of n similar components
running in parallel, where n is not fixed, like the protocol we present
in this paper. Several ways out have been proposed. We have selected
3 different methods. We present them, apply them to the protocol and
analyse how they compare.
Keywords: Formal...
142.
Minimal Model Generation Based on E-Hyper Tableaux
- Wenjin Lu
Minimal model generation has received great attention as people have
deeper and deeper understanding in the semantics of the logic programming,
deductive database, non monotonic reasoning and the relationships
among them. But most proposed minimal model generation procedures
in literature are inappropriate in the sense that while generating minimal
model, they also generate non-minimal models. This means an explicit
minimization has to be employed to obtain minimal models. This may be
a great factor of inefficiency. In this paper we develop an approach to generate
the minimal models, without explicit minimization process, based
on E-hyper tableau which is a variant of hyper tableaux. The soundness
and completeness of the procedure...
143.
Disjunctive Logic Programming: A Survey And Assessment
- Robert A. Kowalski,Jack Minker
We describe the
elds of disjunctive logic programming and disjunctive deductive
databases from the time of their inception to the current time. Contributions
with respect to semantics, implementations and applications are surveyed.
144.
Linear Logical Algorithms
- Robert J. Simmons; Frank Pfenning
Abstract. Bottom-up logic programming can be used to declaratively specify many algorithms in a succinct and natural way, and McAllester and Ganzinger have shown that it is possible to define a cost semantics that enables reasoning about the running time of algorithms written as inference rules. Previous work with the programming language Lollimon demonstrates the expressive power of logic programming with linear logic in describing algorithms that have imperative elements or that must repeatedly make mutually exclusive choices. In this paper, we identify a bottom-up logic programming language based on linear logic that is amenable to efficient execution and describe...
145.
Minimal Model Generation Based on E-Hyper Tableaux
- Wenjin Lu; Wenjin Lu
Minimal model generation has received great attention as people have deeper and deeper understanding in the semantics of the logic programming, deductive database, non monotonic reasoning and the relationships among them. But most proposed minimal model generation procedures in literature are inappropriate in the sense that while generating minimal model, they also generate non-minimal models. This means an explicit minimization has to be employed to obtain minimal models. This may be a great factor of inefficiency. In this paper we develop an approach to generate the minimal models, without explicit minimization process, based on E-hyper tableau which is a variant...
146.
"No Collision" in a Protocol with
- Stations Comparative Study; Agathe Merceron; Monika Mullerburg; G. Michele Pinna
. Formal methods are used both for designing a system and for checking that it satisfies required properties. To prove that a finite system matches its specification, a common line of thought is to express properties in a suitable temporal logic, and with a model checker, automatically verify that the system satisfies them. However this method does not work straightaway for systems composed of n similar components running in parallel, where n is not fixed, like the protocol we present in this paper. Several ways out have been proposed. We have selected 3 different methods. We present them, apply them...
147.
Minimal Model Generation Based on E-Hyper Tableaux
- E-hyper Tableaux; Wenjin Lu
. Minimal model generation has received great attention as people have deeper and deeper understanding in the semantics of the logic programming, deductive database, non monotonic reasoning and the relationships among them. But most proposed minimal model generation procedures in the literature are inappropriate in the sense that while generating minimal model, they also generate non-minimal models. This means that an explicit minimization has to be employed to obtain minimal models. This may be a great factor of inefficiency. In this paper we develop an approach to generate the minimal models, without explicit minimization process, based on E-hyper tableau which...
148.
"No Collision" in a Protocol with n Stations: a Comparative Study of Formal Proofs
- Agathe Merceron; Monika Müllerburg; G. Michele Pinna
. Formal methods are used both for designing a system and for checking that it satisfies required properties. To prove that a finite system matches its specification, a common line of thought is to express properties in a suitable temporal logic, and with a model checker, automatically verify that the system satisfies them. However this method does not work straightaway for systems composed of n similar components running in parallel, where n is not fixed, like the protocol we present in this paper. Several ways out have been proposed. We have selected 3 different methods. We present them, apply them...
149.
"No Collision" in a Protocol with n Stations: a Comparative Study of Formal Proofs
- Agathe Merceron; Monika Müllerburg; G. Michele Pinna
. Formal methods are used both for designing a system and for checking that it satisfies required properties. To provethatafinite system matches its specification, a common line of thought is to express properties in a suitable temporal logic, and with a model checker, automatically verify that the system satisfies them. However this method does not work straightaway for systems composed of n similar components running in parallel, where n is not fixed, like the protocol we present in this paper. Several ways out have been proposed. Wehave selected 3 different methods. We present them, apply them to the protocol and...
150.
Handling XML with a Deductive Database System
We propose an integration of XML with F-Logic, a deductive object-oriented database framework. The F-Logic data model is in fact a semistructured data model, exhibiting many similarities with the XML/DOM data model: there is a canonical mapping from XML to a fragment of F-Logic. The advantages of the integration are that the full expressiveness of F-Logic (and the functionality of the FLORID theobject-orientedmodelforclassicaldatabases.Semistructuredmeansthatthedataisnot XMLisadatamodelforsemistructureddatawhereitplaysthesameroleastherelationalor system) can be applied to the data, providing an intuitive language for view definitions, updates, schema reasoning, Web exploration, integration (also with non-XML sources) etc. Especially, extended XML features, such as XML Schema or XLink can...
151.
Disjunctive Logic Programming: A Survey And Assessment
- Jack Minker; Dietmar Seipel
We describe the elds of disjunctive logic programming and disjunctive deductive databases from the time of their inception to the current time. Contributions with respect to semantics, implementations and applications are surveyed.
152.
Mechanised Reasoning and Model Generation for Extended Modal Logics
- Renate A. Schmidt,Ullrich Hustadt
The approach presented in this overview paper exploits that modal logics can be seen to be fragments of first-order logic and deductive methods can be developed and studied within the framework of first-order resolution. We focus on a class of extended modal logics very similar in spirit to propositional dynamic logic and closely related to description logics. We review and discuss the development of decision procedures for decidable extended modal logics and look at methods for automatically generating models.
153.
Mechanised Reasoning and Model Generation for Extended Modal Logics
- Renate A. Schmidt
The approach presented in this overview paper exploits that
modal logics can be seen to be fragments of first-order logic and deductive
methods can be developed and studied within the framework of firstorder
resolution. We focus on a class of extended modal logics very similar
in spirit to propositional dynamic logic and closely related to description
logics. We review and discuss the development of decision procedures for
decidable extended modal logics and look at methods for automatically
generating models.
154.
A stable model semantics for behavioral inheritance in deductive object oriented languages
- Hasan M. Jamil
Logic languages like LOGIN [1] and LIFE [2] incorporate structural inheritance by means of an extended unification algorithm for-terms, complex typed structures that are used for data representation. In [10], Kifer et al. proposed a formalism, called F-Logic, for deductive object oriented database query languages where the semantics of structural inheritance is captured within an elegant model theory and a sound and complete proof theory. F-Logic, together
155.
Mechanised Reasoning and Model Generation for Extended Modal Logics
- Renate A. Schmidt; Renate A. Schmidt; Ullrich Hustadt; Ullrich Hustadt
The approach presented in this overview paper exploits that modal logics can be seen to be fragments of first-order logic and deductive methods can be developed and studied within the framework of first-order resolution. We focus on a class of extended modal logics very similar in spirit to propositional dynamic logic and closely related to description logics. We review and discuss the development of decision procedures for decidable extended modal logics and look at methods for automatically generating models.
156.
Mechanised Reasoning and Model Generation for Extended Modal Logics
- Renate A. Schmidt; Ullrich Hustadt
The approach presented in this overview paper exploits that modal logics can be seen to be fragments of first-order logic and deductive methods can be developed and studied within the framework of firstorder resolution. We focus on a class of extended modal logics very similar in spirit to propositional dynamic logic and closely related to description logics. We review and discuss the development of decision procedures for decidable extended modal logics and look at methods for automatically generating models.
157.
Mechanised reasoning and model generation for extended modal logics
- Renate A. Schmidt; Ullrich Hustadt
Abstract. The approach presented in this overview paper exploits that modal logics can be seen to be fragments of first-order logic and deductive methods can be developed and studied within the framework of resolution. We focus on a class of extended modal logics very similar in spirit to propositional dynamic logic and closely related to description logics. We review and discuss the development of decision procedures for decidable extended modal logics and look at methods for automatically generating models. 1
158.
Extending Classical Logic with Inductive Definitions
- Denecker, Marc
The goal of this paper is to extend classical logic with a generalized notion
of inductive definition supporting positive and negative induction, to
investigate the properties of this logic, its relationships to other logics in
the area of non-monotonic reasoning, logic programming and deductive databases,
and to show its application for knowledge representation by giving a typology
of definitional knowledge.
159.
An Epistemic Foundation for Logic Programming with Uncertainty
- Laks V. S. Lakshmanan
this paper is primarily with probabilistic extensions to logic programming
and deductive databases. Substantial work has been done in this area (see Section 6 for
a brief survey). One criticism (e.g. see [17]) leveled against probabilistic approaches for
uncertainty management is how the probabilities representing degree of likelihood can be
160.
Extending Classical Logic with Inductive Definitions
- Marc Denecker
The goal of this paper is to extend classical logic with a generalized notion of inductive definition supporting positive and negative induction, to investigate the properties of this logic, its relationships to other logics in the area of non-monotonic reasoning, logic programming and deductive databases, and to show its application for knowledge representation by giving a typology of definitional knowledge.
