The Experts below are selected from a list of 72 Experts worldwide ranked by ideXlab platform
Antoni Ligeza - One of the best experts on this subject based on the ideXlab platform.
-
a note on backward dual resolution and its application to Proving Completeness of rule based systems
International Joint Conference on Artificial Intelligence, 1993Co-Authors: Antoni LigezaAbstract:In this paper, a method of theorem Proving dual to resolution method is presented in brief. The investigated method is called backward dual resolution or bd-re solution, for short. The main idea of bd-resolution consists in Proving validity of a formula in disjunctive normal form, by generating an empty tautology formula from it; it is shown that the initial formula is a logical consequence of the obtained tautology. An idea of the theorem Proving method is outlined, and its application to checking Completeness of rule-based systems is investigated. A formal definition of Completeness and specific Completeness are stated and an algorithm for Completeness verification is proposed. Moreover, a generalized bd-resolution aimed at Proving Completeness under intended interpretation is defined.
Rolf Drechsler - One of the best experts on this subject based on the ideXlab platform.
-
DSD - Proving Completeness of Properties in Formal Verification of Counting Heads for Railways
2007Co-Authors: Sebastian Kinder, Rolf DrechslerAbstract:The demand for safety of electronic devices is high. Especially in safety-critical systems, e.g. electronic railway interlocking systems, safety is an important issue. Nowadays these systems are tested and simulated with a manually created set of test cases. But testing is a very cost-intensive procedure and can never reach a complete coverage for large designs. Hence, an efficient way to formally verify these systems is required. In this paper we present the formal verification of Counting Heads for railways, a real-time system that is used in most electronic railway interlocking systems from SIEMENS. For the verification bounded model checking algorithms are applied, i.e. a set of properties is formally proven. The Completeness of this set is also determined efficiently.
-
Proving Completeness of Properties in Formal Verification of Counting Heads for Railways
10th Euromicro Conference on Digital System Design Architectures Methods and Tools (DSD 2007), 2007Co-Authors: Sebastian Kinder, Rolf DrechslerAbstract:The demand for safety of electronic devices is high. Especially in safety-critical systems, e.g. electronic railway interlocking systems, safety is an important issue. Nowadays these systems are tested and simulated with a manually created set of test cases. But testing is a very cost-intensive procedure and can never reach a complete coverage for large designs. Hence, an efficient way to formally verify these systems is required. In this paper we present the formal verification of Counting Heads for railways, a real-time system that is used in most electronic railway interlocking systems from SIEMENS. For the verification bounded model checking algorithms are applied, i.e. a set of properties is formally proven. The Completeness of this set is also determined efficiently.
Wlodzimierz Drabent - One of the best experts on this subject based on the ideXlab platform.
-
Proving Completeness of logic programs with the cut
Formal Aspects of Computing, 2017Co-Authors: Wlodzimierz DrabentAbstract:Completeness of a logic program means that the program produces all the answers required by its specification. The cut is an important construct of programming language Prolog. It prunes part of the search space, this may result in a loss of Completeness. This paper proposes a way of Proving Completeness of programs with the cut. The semantics of the cut is formalized by describing how SLD-trees are pruned. A sufficient condition for Completeness is presented, proved sound, and illustrated by examples.
-
Correctness and Completeness of Logic Programs
ACM Transactions on Computational Logic, 2016Co-Authors: Wlodzimierz DrabentAbstract:We discuss Proving correctness and Completeness of definite clause logic programs. We propose a method for Proving Completeness, while for Proving correctness we employ a method that should be well known but is often neglected. Also, we show how to prove Completeness and correctness in the presence of SLD-tree pruning, and point out that approximate specifications simplify specifications and proofs. We compare the proof methods to declarative diagnosis (algorithmic debugging), showing that approximate specifications eliminate a major drawback of the latter. We argue that our proof methods reflect natural declarative thinking about programs, and that they can be used, formally or informally, in everyday programming.
Antoni Ligęza - One of the best experts on this subject based on the ideXlab platform.
-
IJCAI - A note on backward dual resolution and its application to Proving Completeness of rule-based systems
1993Co-Authors: Antoni LigęzaAbstract:In this paper, a method of theorem Proving dual to resolution method is presented in brief. The investigated method is called backward dual resolution or bd-re solution, for short. The main idea of bd-resolution consists in Proving validity of a formula in disjunctive normal form, by generating an empty tautology formula from it; it is shown that the initial formula is a logical consequence of the obtained tautology. An idea of the theorem Proving method is outlined, and its application to checking Completeness of rule-based systems is investigated. A formal definition of Completeness and specific Completeness are stated and an algorithm for Completeness verification is proposed. Moreover, a generalized bd-resolution aimed at Proving Completeness under intended interpretation is defined.
Antoni Lig - One of the best experts on this subject based on the ideXlab platform.
-
Dual Resolution for Logical Reduction of Granular Tables
2003Co-Authors: Antoni LigAbstract:l Abstract. Dual resolution is a universal logical inference method for automated theorem Proving. Contrary to classical Robinson's resolution it operates on for mulae of conjunctive form and the direction of logical consequence is inverse with respect to resolvent generation. This method is convenient especially for Proving Completeness and formulae reduction. In the paper it is shown how to use dual resolution to reduce attributive decision tables preserving logical equivalence. As atomic values of attributes are to be glued together, granular tables are used to express the results of reduction.