Heterogeneous knowledge representation: integrating connectionist and symbolic computation

Heterogeneous knowledge representation allows combination of several knowledge representation techniques. For instance, connectionist and symbolic systems are two different computational paradigms and knowledge representations. Unfortunately, the integration of different paradigms and knowledge representations is not easy and very often is informal. In this paper, we propose a formal approach to integrate these two paradigms where as a symbolic system we consider a (logic) rule-based system. The integration is operated at language level between neural networks and rule languages. The formal model that allows the integration is based on constraint logic programming and provides an integrated framework to represent and process heterogeneous knowledge. In order to achieve this we define a new language that allows expression and modelling in a natural and intuitive way the above issues together with the operational semantics.     

Satisfiability and containment of recursive SHACL

The Shapes Constraint Language (SHACL) is the recent W3C recommendation language for validating RDF data, by verifying certain shapes on graphs. Previous work has largely focused on the validation problem, while the standard decision problems of satisfiability and containment, crucial for design and optimisation purposes, have only been investigated for simplified versions of SHACL. Moreover, the SHACL specification does not define the semantics of recursively-defined constraints, which led to several alternative recursive semantics being proposed in the literature. The interaction between these different semantics and important decision problems has not been investigated yet. In this article we provide a comprehensive study of the different features of SHACL, by providing a translation to a new first-order language, called SCL, that precisely captures the semantics of SHACL. We also present MSCL, a second-order extension of SCL, which allows us to define, in a single formal logic framework, the main recursive semantics of SHACL. Within this language we also provide an effective treatment of filter constraints which are often neglected in the related literature. Using this logic we provide a detailed map of (un)decidability and complexity results for the satisfiability and containment decision problems for different SHACL fragments. Notably, we prove that both problems are undecidable for the full language, but we present decidable combinations of interesting features, even in the face of recursion.     

An institution theory of formal meta-modelling in graphically extended BNF

Meta-modelling plays an important role in model driven software development.In this paper,a graphic extension of BNF (GEBNF) is proposed to define the abstract syntax of graphic modelling languages.Fro...     

On the interaction between knowledge and social commitments in multi-agent systems

Both knowledge and social commitments have received considerable attention in Multi-Agent Systems (MASs), specially for multi-agent communication. Plenty of work has been carried out to define their semantics. However, the relationship between social commitments and knowledge has not been investigated yet. In this paper, we aim to explore such a relationship from the semantics and model checking perspectives with respect to CTLK logic (an extension of CTL logic with modality for reasoning about knowledge) and CTLC logic (an extension of CTL with modalities for reasoning about commitments and their fulfillments). To analyze this logical relationship, we simply combine the two logics in one new logic named CTLKC. The purpose of such a combination is not to advocate a new logic, but only to express and figure out some reasoning postulates merging both knowledge and commitments as they are currently defined in the literature. By so doing, we identify some paradoxes in the new logic showing that simply combining current versions of commitment and knowledge logics results in a logical language that violates some fundamental intuitions. Consequently, we propose CTLKC⁺, a new logic that fixes the identified paradoxes and allows us to reason about social commitments and knowledge simultaneously in a consistent manner. Furthermore, we address the problem of model checking CTLKC⁺ by reducing it to the problem of model checking GCTL^?, a generalized version of CTL^? with action formulae. By doing so, we directly benefit from CWB-NC, the model checker of GCTL^?. Using this reduction, we also prove that the computational complexity of model checking CTLKC⁺ is still PSPACE-complete for concurrent programs as the complexity of model checking CTLK and CTLC separately.     

AN EPISTEMIC LOGIC WITH QUANTIFICATION OVER NAMES

Sentential theories of belief hold that propositions (the things that agents believe and know) are sentences of a representation language. To analyze quantification into the scope of attitudes, these theories require a naming map a function that maps objects to their names in the representation language. Epistemic logics based on sentential theories usually assume a single naming map, which is built into the logic. I argue that to describe everyday knowledge, the user of the logic must be able to define new naming maps for particular problems. Since the range of a naming map is usually an infinite set of names, defining a map requires quantification over names. This paper describes an epistemic logic with quantification over names, presents a theorem-proving algorithm based on translation to first-order logic, and proves soundness and completeness. The first version of the logic suffers from the problem of logical omniscience; a second version avoids this problem, and soundness and completeness are proved for this version also.     

Oriented equational clauses as a programming language

In the Prolog language, Horn clauses of first-order logic are regarded as programs, and the resolution procedure is used as an interpreter. In this paper, we present the formalism of Horn oriented equational clauses (Horn clauses with a rewrite rule as the head part, and a list of equations as the body part). We show that such a formalism can be interpreted as a logic language with built-in equality, and that a procedure based on clausal superposition can be used as an interpreter. We define the operational, model-theoretic and fixpoint semantics of the language, and prove their equivalence. Then we point out the advantages of such a programming language: embodying Prolog, mixing functional and relational features and, handling the equality relation. Lastly, we present experiments performed with an implemented interpreter.     

自然语言处理中的逻辑词

词是自然语言处理中最基本的单位,在当今知识表示领域,知识图作为自然语言理解的语义模型有其独到之处。本文从语言学和逻辑学的角度,首次提出并探讨了逻辑词研究逻辑词分类及如何用知识图表示各类逻辑词的结构。对自然语言处理中研究复句和篇章的理解提供了一种新的途径。     

MSVL: a typed language for temporal logic programming

The development of types is an important but challenging issue in temporal logic programming. In this paper, we investigate how to formalize and implement types in the temporal logic programming language MSVL, which is an executable subset of projection temporal logic (PTL). Specifically, we extendMSVL with a few groups of types including basic data types, pointer types and struct types. On each type, we specify the domain of values and define some standard operations in terms of logic functions and predicates. Then, it is feasible to formalize statements of type declaration of program variables and statements of struct definitions as logic formulas. As the implementation of the theory, we extend theMSV toolkit with the support of modeling, simulation and verification of typedMSVL programs. Applications to the construction of AVL tree and ordered list show the practicality of the language.     

Timer formulas and decidable metric temporal logic

We define a quantitative temporal logic that is based on a simple modality within the framework of monadic predicate logic. Its canonical model is the real line (and not an ω-sequence of some type). It can be interpreted either by behaviors with finite variability or by unrestricted behaviors. For finite variability models it is as expressive as any logic suggested in the literature. For unrestricted behaviors our treatment is new. In both cases we prove decidability and complexity bounds using general theorems from logic (and not from automata theory). The technical proof uses a sublanguage of the metric monadic logic of order, the language of timer normal form formulas. Metric formulas are reduced to timer normal form and timer normal form formulas allow elimination of the metric.     

Towards the uniform implementation of declarative languages

Current implementation techniques for functional languages differ considerably from those for logic languages. This complicates the development of flexible and efficient abstract machines that can be used for the compilation of declarative languages combining concepts of functional and logic programming. We propose an abstract machine, called the JUMP-machine, which systematically integrates the operational concepts needed to implement the functional and logic programming paradigm. The use of a tagless representation for heap objects, which originates from the Spineless Tagless G-machine, supports the integration of different concepts. In this paper, we provide a functional logic kernel language and show how to translate it into the abstract machine language of the JUMP-machine. Furthermore, we define the operational semantics of the machine language formally and discuss the mapping of the abstract machine to concrete machine architectures. We tested the approach by writing a compiler for the functional logic language GTML. The obtained performance results indicate that the proposed method allows to implement functional logic languages efficiently.     

A temporal programming model with atomic blocks based on projection temporal logic

Atomic blocks, a high-level language construct that allows programmers to explicitly specify the atomicity of operations without worrying about the implementations, are a promising approach that simplifies concurrent programming. On the other hand, temporal logic is a successful model in logic programming and concurrency verification, but none of existing temporal programming models supports concurrent programming with atomic blocks yet. In this paper, we propose a temporal programming model (αPTL) which extends the projection temporal logic (PTL) to support concurrent programming with atomic blocks. The novel construct that formulates atomic execution of code blocks, which we call atomic interval formulas, is always interpreted over two consecutive states, with the internal states of the block being abstracted away. We show that the framing mechanism in projection temporal logic also works in the new model, which consequently supports our development of an executive language. The language supports concurrency by introducing a loose interleaving semantics which tracks only the mutual exclusion between atomic blocks. We demonstrate the usage of αPTL by modeling and verifying both the fine-grained and coarse-grained concurrency.     

Measuring inconsistency in knowledgebases

It is well-known that knowledgebases may contain inconsistencies. We provide a measure to quantify the inconsistency of a knowledgebase, thereby allowing for the comparison of the inconsistency of various knowledgebases, represented as first-order logic formulas. We use quasi-classical (QC) logic for this purpose. QC logic is a formalism for reasoning and analysing inconsistent information. It has been used as the basis of a framework for measuring inconsistency in propositional theories. Here we extend this framework, by using a first-order logic version of QC logic for measuring inconsistency in first-order theories. We motivate the QC logic approach by considering some formulae as database or knowledgebase integrity constraints. We then define a measure of extrinsic inconsistency that can be used to compare the inconsistency of different knowledgebases. This measure takes into account both the language used and the underlying domain. We show why this definition also captures the intrinsic inconsistency of a knowledgebase. We also provide a formalization of paraconsistent equality, called quasi-equality, and we use this in an extended example of an application for measuring inconsistency between heterogeneous sources of information and integrity constraints prior to merging.     

Certifying assembly programs with trails

In this paper, we introduce a new way of certifying assembly programs. Unlike previous program logics, we extract the control-flow information from the code and generate an intermediate trail between the specification and the real code. Trails are auxiliary specifications and treated as modules in the certification process. We define a simple modular program logic called trail-based certified assembly programming (TCAP) to certify and link different parts of a program using the corresponding trails. Because the control flow information in trails is explicit, the rules are easier to design. We show that our logic is powerful enough to prove partial correctness of assembly programs with features including stack-based abstractions and self-modifying code.We also provide a semantics for TCAP and prove that the logic is sound with respect to the semantics.     

Two Case Studies of Semantics Execution in Maude: CCS and LOTOS

We explore the features of rewriting logic and, in particular, of the rewriting logic language Maude as a logical and semantic framework for representing and executing inference systems. In order to illustrate the general ideas we consider two substantial case studies. In the first one, we represent both the semantics of Milner’s CCS and a modal logic for describing local capabilities of CCS processes. Although a rewriting logic representation of the CCS semantics is already known, it cannot be directly executed in the default interpreter of Maude. Moreover, it cannot be used to answer questions such as which are the successors of a process after performing an action, which is used to define the semantics of Hennessy-Milner modal logic. Basically, the problems are the existence of new variables in the righthand side of the rewrite rules and the nondeterministic application of the semantic rules, inherent to CCS. We show how these problems can be solved in a general, not CCS dependent way by controlling the rewriting process by means of reflection. This executable specification plus the reflective control of rewriting can be used to analyze CCS processes. The same techniques are also used to implement a symbolic semantics for LOTOS in our second case study. The good properties of Maude as a metalanguage allow us to implement a whole formal tool where LOTOS specifications without restrictions in their data types (given as ACT ONE specifications) can be executed. In summary, we present Maude as an executable semantic framework by providing easy-tool-building techniques for a language given its operational semantics.Research supported by CICYT projects Desarrollo Formal de Sistemas Distribuidos (TIC97-0669-C03-01) and Desarrollo Formal de Sistemas Basados en Agentes Móviles (TIC2000-0701-C02-01).     

基于本体的多域访问控制策略集成研究

本体是共享概念模型的形式化规范说明,是一种能在语义和知识层次上描述信息系统概念模型的建模工具,为解决多域环境中的安全互操作提供了一种新的方法.使用本体及其描述语言,对基于角色的访问控制策略进行了描述,形成一个概念和属性的公理集合（TBox）,并采用ALCN（含有个数限制和补算子的描述逻辑语言）对TBox进行形式化的描述.利用域间角色映射方法来解决多域访问控制策略的集成.使用基于规则的推理技术,定义多域访问控制中的一系列推理规则,实现访问控制领域的推理.基于前述方法实现了OntoAC系统,实验结果表明该方法是有效的.     

Abductive logic programming agents with destructive databases

In this paper we present an agent language that combines agent functionality with a state transition theory and model-theoretic semantics. The language is based on abductive logic programming (ALP), but employs a simplified state-free syntax, with an operational semantics that uses destructive updates to manipulate a database, which represents the current state of the environment. The language builds upon the ALP combination of logic programs, to represent an agent??s beliefs, and integrity constraints, to represent the agent??s goals. Logic programs are used to define macro-actions, intensional predicates, and plans to reduce goals to sub-goals including actions. Integrity constraints are used to represent reactive rules, which are triggered by the current state of the database and recent agent actions and external events. The execution of actions and the assimilation of observations generate a sequence of database states. In the case of the successful solution of all goals, this sequence, taken as a whole, determines a model that makes the agent??s goals and beliefs all true.     

Toward a programming theory for rational agents

An important problem in agent verification is a lack of proper understanding of the relation between agent programs on the one hand and agent logics on the other. Understanding this relation would help to establish that an agent programming language is both conceptually well-founded and well-behaved, as well as yield a way to reason about agent programs by means of agent logics. As a step toward bridging this gap, we study several issues that need to be resolved in order to establish a precise mathematical relation between a modal agent logic and an agent programming language specified by means of an operational semantics. In this paper, we present an agent programming theory that provides both an agent programming language as well as a corresponding agent verification logic to verify agent programs. The theory is developed in stages to show, first, how a modal semantics can be grounded in a state-based semantics, and, second, how denotational semantics can be used to define the mathematical relation connecting the logic and agent programming language. Additionally, it is shown how to integrate declarative goals and add precompiled plans to the programming theory. In particular, we discuss the use of the concept of higher-order goals in our theory. Other issues such as a complete axiomatization and the complexity of decision procedures for the verification logic are not the focus of this paper and remain for future investigation. Part of this research was carried out while the first author was affiliated with the Nijmegen Institute for Cognition and Information, Radboud University Nijmegen.     

实时并发系统的PTSL模型检测

随着实时并发系统的软件规模越来越大、复杂性日趋增加,如何保证并发实时系统正确性和可靠性成为日益紧迫的问题。模型检测技术采用自动化的验证算法判断系统是否具有某一性质,它不仅包括对系统模型的遍历以及基于图形的分析方法,而且还需要大量的数值计算。本文把实时并发模型看成对并发博弈模型（CGS）的扩展,在此基础上添加了概率与时间性质,提出了概率时间并发博弈结构（PTCGS）。同时本文还提出了新的逻辑语言-概率时间策略逻辑（PTSL）,它显式地把策略作为一阶逻辑中的对象,从而使我们能够以简单而自然的方式指定PTCGS系统中的非零和属性。PTSL模型检测方法能够让设计者准确知道模型是否满足用户的需求,从而提高系统的可靠性。最后,本文以ZeroConf协议为例来说明PTSL模型检测方法的正确性。     

Hybrid

Combining higher-order abstract syntax and (co)-induction in a logical framework is well known to be problematic. We describe the theory and the practice of a tool called Hybrid, within Isabelle/HOL and Coq, which aims to address many of these difficulties. It allows object logics to be represented using higher-order abstract syntax, and reasoned about using tactical theorem proving and principles of (co)induction. Moreover, it is definitional, which guarantees consistency within a classical type theory. The idea is to have a de Bruijn representation of λ-terms providing a definitional layer that allows the user to represent object languages using higher-order abstract syntax, while offering tools for reasoning about them at the higher level. In this paper we describe how to use Hybrid in a multi-level reasoning fashion, similar in spirit to other systems such as Twelf and Abella. By explicitly referencing provability in a middle layer called a specification logic, we solve the problem of reasoning by (co)induction in the presence of non-stratifiable hypothetical judgments, which allow very elegant and succinct specifications of object logic inference rules. We first demonstrate the method on a simple example, formally proving type soundness (subject reduction) for a fragment of a pure functional language, using a minimal intuitionistic logic as the specification logic. We then prove an analogous result for a continuation-machine presentation of the operational semantics of the same language, encoded this time in an ordered linear logic that serves as the specification layer. This example demonstrates the ease with which we can incorporate new specification logics, and also illustrates a significantly more complex object logic whose encoding is elegantly expressed using features of the new specification logic.