Generalized quantifiers and modal logic

We study several modal languages in which some (sets of) generalized quantifiers can be represented; the main language we consider is suitable for defining any first order definable quantifier, but we also consider a sublanguage thereof, as well as a language for dealing with the modal counterparts of some higher order quantifiers. These languages are studied both from a modal logic perspective and from a quantifier perspective. Thus the issues addressed include normal forms, expressive power, completeness both of modal systems and of systems in the quantifier tradition, complexity as well as syntactic characterizations of special semantic constraints. Throughout the paper several techniques current in the theory of generalized quantifiers are used to obtain results in modal logic, and conversely.This author was supported by the Foundation for Philosophical Research (SWON), which is subsidized by the Netherlands Organization for Scientific Research (NWO).     

A Logic with Relative Knowledge Operators

We study a knowledge logic that assumes that to each set of agents, an indiscernibility relation is associated and the agents decide the membership of objects or states up to this indiscernibility relation. Its language contains a family of relative knowledge operators. We prove the decidability of the satisfiability problem, we show its EXPTIME-completeness and as a side-effect, we define a complete Hilbert-style axiomatization.     

Theorem proving for intensional logic

For a number of tasks in knowledge representation, and particularly in natural language semantics, it is useful to be able to treat propositions and properties as objects — as items that can appear as arguments of predicates, as things one can quantify over, and so on. Logics that support such intensional operations are notoriously hard to work with. The current paper presents a theorem prover for one such logic, namely, Turner's property theory.     

一种类比知识表示与逻辑描述

本文叙述了一个以情境为单位基于情境间的整体部分关系的类比知识表示系统，给出了描述这种知识结构的内涵命题逻辑的语法，语义和公理系统，用实例说明了情境的联接不是逻辑与关系。     

知识库系统技术研究

由于知识在人类生活中的重要性,知识库系统的研究具有十分重要的意义。本文首先定义了什么是知识库和知识库系统,对近年来人们在知识库领域及相关领域所做的工作进行了概括和总结,最后分析了该领域的研究动向。     

Computational Complexity and Anytime Algorithm for Inconsistency Measurement

Measuring inconsistency degrees of inconsistent knowledge bases is an important problem as it provides context information for facilitating inconsistency handling. Many methods have been proposed to solve this problem and a main class of them is based on some kind of paraconsistent semantics. In this paper, we consider the computational aspects of inconsistency degrees of propositional knowledge bases under 4-valued semantics. We ˉrst give a complete analysis of the computational complexity of computing inconsistency degrees. As it turns out that computing the exact inconsistency degree is intractable, we then propose an anytime algorithm that provides tractable approximations of the inconsistency degree from above and below. We show that our algorithm satisˉes some desirable properties and give experimental results of our implementation of the algorithm.     

Complexity of the Two-Variable Fragment with Counting Quantifiers

The satisfiability and finite satisfiability problems for the two-variable fragment of first-order logic with counting quantifiers are both in NEXPTIME, even when counting quantifiers are coded succinctly.     

Definability of Polyadic Lifts of Generalized Quantifiers

We study generalized quantifiers on finite structures.With every function : we associate a quantifier Q by letting Q x say there are at least (n) elementsx satisfying , where n is the sizeof the universe. This is the general form ofwhat is known as a monotone quantifier of type < 1 >.We study so called polyadic liftsof such quantifiers. The particular lifts we considerare Ramseyfication, branching and resumption.In each case we get exact criteria fordefinability of the lift in terms of simpler quantifiers.     

A finite model construction for coalgebraic modal logic

In recent years, a tight connection has emerged between modal logic on the one hand and coalgebras, understood as generic transition systems, on the other hand. Here, we prove that (finitary) coalgebraic modal logic has the finite model property. This fact not only reproves known completeness results for coalgebraic modal logic, which we push further by establishing that every coalgebraic modal logic admits a complete axiomatisation in rank 1; it also enables us to establish a generic decidability result and a first complexity bound. Examples covered by these general results include, besides standard Hennessy–Milner logic, graded modal logic and probabilistic modal logic.     

从逻辑系统到知识系统

当前的模态或非模态逻辑系统的概念都是狭义的,它们关心的主要是一些重言式或永真式。而对人来说,事实真或假的知识同样是非常重要的,但这样的知识却超出了它们的定义范围。当它们(通常是模态逻辑系统)被用于意识系统研究时,这就不合适了。为此,本文提出了一种知识系统的观点,其中不仅包括了通常逻辑系统的内容,而且也包括了事实真或假的知识等相关内容,从而解决了这一问题。     

Planning in polynomial time: the SAS-PUBS class

This article describes a polynomial-time, O ( n³ ), planning algorithm for a limited class of planning problems. Compared to previous work on complexity of algorithms for knowledge-based or logic-based planning, our algorithm achieves computational tractability, but at the expense of only applying to a significantly more limited class of problems. Our algorithm is proven correct, and it always returns a parallel minimal plan if there is a plan at all.
Cet article décrit un algorithme de planification de temps polynomial O ( n ³) pour une classe restreinte de problemes de planification. Contrairement aux travaux précédents sur la complexité des algorithmes pour la planification basée sur la logique ou les connaissances, l' algorithme dont il est question dans cet article permet d' obtenir la tractabilityé computationnelle; cependant, il ne peut ětre appliqué qu'à une catégorie beaucoup plus restreinte de problèmes. Cet algorithme s'est done révélé correct et il génère toujours un plan minimal en parallèle lorsqu'il y en a un.     

间断区间时态逻辑的语义

区间逻辑不能模拟自然语言中与,或,非时态关系,其公理系统的完备性不易保证。我们建立的间断区间时态知脚注可以克服区间逻辑的上述缺点,本文给出了间断区间逻辑的语法,语义及公理,即描述了间断区间时态逻辑的语义。