Completeness of a combination of neighbourhood logic and temporal logic

This paper presents a completeness result, with respect to a possible world semantics, for a combination of a first-order temporal logic and neighbourhood logic. This logic was considered by Qiu and Zhou (1998, Proceedings of the PROCOMET 98, pp 444–461) to define semantics of a real-time OCCAM-like programming language.Received June 1999Accepted in revised form September 2003 by M. R. Hansen and C. B. Jones     

Parameterized verification of leader/follower systems via first-order temporal logic

Formal Methods in System Design - We introduce a framework for the verification of protocols involving a distinguished machine (referred to as a leader) orchestrating the operation of an arbitrary...     

Linking temporal first-order logic with Bayesian networks for the simulation of pervasive computing systems

The authors’ previous work discussed a scalable abstract knowledge representation and reasoning scheme for Pervasive Computing Systems, where both low-level and abstract knowledge is maintained in the form of temporal first-order logic (TFOL) predicates. Furthermore, we introduced a novel concept of a generalised event, an abstract event, which we define as a change in the truth value of an abstract TFOL predicate. Abstract events represent real-time knowledge about the system and they are defined with the help of well-formed TFOL expressions whose leaf nodes are concrete, low-level events using our AESL language.In this paper, we propose to simulate pervasive systems by providing estimated knowledge about its entities and situations that involve them. To achieve this goal, we enhance AESL with higher-order function predicates that denote approximate knowledge about the likelihood of a predicate instance having the value True with respect to a time reference. We define a mapping function between a TFOL predicate and a Bayesian network that calculates likelihood estimates for that predicate as well as a confidence level, i.e., a metric of how reliable the likelihood estimation is for that predicate.Higher-order likelihood predicates are implemented by a novel middleware component, the Likelihood Estimation Service (LES). LES implements the above mapping; first, for each abstract predicate, it learns a Bayesian network that corresponds to that predicate from the knowledge stored in the sensor-driven system. Once trained and validated, the Bayesian networks generate a likelihood estimate and a confidence level. This new knowledge is maintained in the middleware as approximate knowledge therefore providing a simulation of the pervasive system, in the absence of real-time data. Last but not least, we describe an experimental evaluation of our system using the Active BAT location system.     

Software tools for first-order logic

A suite of software tools for the manipulation and validation of first-order logic expressions is presented. The suite ponsists of a collection of modules, each performing a precise and well-defined task. More sophisticated tasks such as theorem proving can be achieved by concatenating modules and interacting at suitable stages.     

Toward effective knoledge acquisition with first-order logic induction

Knowledge acquisition with machine learning techniques is a fundamental requirement for knowledge discovery from databases and data mining systems. Two techniques in particular — inductive learning and theory revision — have been used toward this end. A method that combines both approaches to effectively acquire theories (regularity) from a set of training examples is presented. Inductive learning is used to acquire new regularity from the training examples; and theory revision is used to improve an initial theory. In addition, a theory preference criterion that is a combination of the MDL-based heuristic and the Laplace estimate has been successfully employed in the selection of the promising theory. The resulting algorithm developed by integrating inductive learning and theory revision and using the criterion has the ability to deal with complex problems, obtaining useful theories in terms of its predictive accuracy.     

On a decidable generalized quantifier logic corresponding to a decidable fragment of first-order logic

Van Lambalgen (1990) proposed a translation from a language containing a generalized quantifierQ into a first-order language enriched with a family of predicatesR _i, for every arityi (or an infinitary predicateR) which takesQxg(x, y₁,..., y_n) to x(R(x, y₁,..., y₁) (x,y₁,...,y_n)) (y ₁,...,y_n are precisely the free variables ofQx). The logic ofQ (without ordinary quantifiers) corresponds therefore to the fragment of first-order logic which contains only specially restricted quantification. We prove that it is decidable using the method of analytic tableaux. Related results were obtained by Andréka and Németi (1994) using the methods of algebraic logic.     

Completeness and incompleteness for plausibility logic

Plausibility Logic was introduced by Daniel Lehmann. We show—among some other results—completeness of a subset of Plausibility Logic for Preferential Models, and incompleteness of full Plausibility Logic for smooth Preferential Models.     

Proving linearizability with temporal logic

Linearizability is a global correctness criterion for concurrent systems. One technique to prove linearizability is applying a composition theorem which reduces the proof of a property of the overall system to sufficient rely-guarantee conditions for single processes. In this paper, we describe how the temporal logic framework implemented in the KIV interactive theorem prover can be used to model concurrent systems and to prove such a composition theorem. Finally, we show how this generic theorem can be instantiated to prove linearizability of two classic lock-free implementations: a Treiber-like stack and a slightly improved version of Michael and Scott’s queue.     

Mechanising first-order temporal resolution

First-order temporal logic is a concise and powerful notation, with many potential applications in both Computer Science and Artificial Intelligence. While the full logic is highly complex, recent work on monodic first-order temporal logics has identified important enumerable and even decidable fragments. Although a complete and correct resolution-style calculus has already been suggested for this specific fragment, this calculus involves constructions too complex to be of practical value. In this paper, we develop a machine-oriented clausal resolution method which features radically simplified proof search. We first define a normal form for monodic formulae and then introduce a novel resolution calculus that can be applied to formulae in this normal form. By careful encoding, parts of the calculus can be implemented using classical first-order resolution and can, thus, be efficiently implemented. We prove correctness and completeness results for the calculus and illustrate it on a comprehensive example. An implementation of the method is briefly discussed.     

Extending statecharts with temporal logic

The task of designing large real-time reactive systems, which interact continuously with their environment and exhibit concurrency properties, is a challenging one. The authors explore the utility of a combination of behavior and function specification languages in specifying such systems and verifying their properties. An existing specification language, statecharts, is used to specify the behavior of real-time reactive systems, while a new logic-based language called FNLOG (based on first-order predicate calculus and temporal logic) is designed to express the system functions over real time. Two types of system properties, intrinsic and structural, are proposed. It is shown that both types of system properties are expressible in FNLOG and may be verified by logical deduction, and also hold for the corresponding behavior specification     

一阶子句搜索方法

子句集的可满足性判定是自动证明领域的热点之一.提出了子句搜索方法判定命题子句集Φ的可满足性,该方法查找Φ中子句的一个公共不可扩展子句C,当且仅当找到C时Φ可满足,此时C中各文字的补构成一个模型.结合部分实例化方法将子句搜索方法提升至一阶.一阶子句搜索方法可以判定子句集的M可满足性,具备终止性、正确性和完备性,是一种判定子句集可满足性的有效方法.     

A first-order coalition logic for BDI-agents

Coalition logic (CL) enables us to model the strategic abilities and specify what a group of agents can achieve whatever the other agents do. However, some rational mental attitudes of the agents are beyond the scope of CL such as the prestigious beliefs, desires and intentions (BDI) which is an interesting and useful epistemic notion and has spawned substantial amount of studies in multi-agent systems. In this paper, we introduce a first-order coalition BDI (FCBDI) logic for multi-agent systems, which provides a semantic glue that allows the formal embedding and interaction of BDI, coalition and temporal operators in a first-order language. We further introduce a semantic model based on the interpreted system model and present an axiomatic system that is proved sound and complete with respect to the semantics. Finally, it is shown that the computational complexity of its model checking in finite structures is PSPACE-complete.     

Protected completions of first-order general logic programs

Minker and Perlis [15] have made the important observation that in certain circumstances, it might be desirable to prevent the inference of A when A is in the finite failure set of a logic program P. In this paper, we investigate the model-theoretic aspects of their proposal and develop a Fitting-style [5] declarative semantics for protected completions of general logic programs (containing function symbols). This extends the Minker-Perlis proposal which applies to function-free pure logic programs. In addition, an operational semantics is proposed and it is proven to be sound for existentially quantified positive queries and negative ground queries to general, canonical protected logic programs. Completeness issues are investigated and completeness is proved for positive existential queries and negative ground queries for the following classes of programs: (1) function-free general protected logic programs (the Minker-Perlis operational semantics apply to function-free pure protected logic programs), (2) pure protected logic programs (with function symbols) and (3) protected general logic programs that do not contain any internal variables (though they may contain function symbols).     

Querying datalog programs with temporal logic

Temporal logic queries on Datalog and negated Datalog programs are studied, and their relationship to Datalog queries on these programs is explored. It is shown that, in general, temporal logic queries have more expressive power than Datalog queries on Datalog and negated Datalog programs. It is also shown that anexistential domain-independent fragment of temporal logic queries has the same expressive power as Datalog queries on negated Datalog programs with inflationary semantics. This means that for finite structures this class of queries has the power of the fixpoint logic.     

Verification of a technical system model with linear temporal logic

We consider the verification problem for an electromechanical device with a variable number of connectors and solve it with the modal logic LTL (Linear Temporal Logic). In the course of the analysis, we prove continuity and unambiguity theorems for the device operation and study the restrictions necessary in order for the device operation algorithm to be completely correct.