线性逻辑和态极逻辑引论(Ⅰ)

《线性逻辑和态极逻辑引论》一文概述了由Girard分别于1986和2001所创建的线性逻辑和态极逻辑.线性逻辑和态极逻辑汲取于计算机科学并反之应用于其中,从根本上对数理逻辑进行了彻底的审视.全文分为两部分.本文是文章的第一部分,致力于线性逻辑的联结词、证明规则、可判定性性质和模型.文章的第二部分将研究证明网并简要介绍态极逻辑.证明网是证明的图式表示,是线性逻辑的主要创新之一.     

Looking-ahead in backtracking algorithms for abstract argumentation

We refine implemented backtracking algorithms for a number of problems related to Dung's argumentation frameworks. Under admissible, preferred, complete, stable, semi stable, and ideal semantics we add enhancements, what are so-called global looking-ahead pruning strategies, to the-state-of-the-art implementations of two problems. First, we tackle the extension enumeration problem: constructing some/all set(s) of acceptable arguments of a given argumentation framework. Second, we address the acceptance decision problem: deciding whether an argument is in some/all set(s) of accepted arguments of a given argumentation framework. The experiments that we report show that the speedup gain of the new enhancements is quite significant.     

Quantum Uncertainties and Holism Seem to Render Irrelevant Qudit-Semantics

We consider a semantics based on the peculiar holistic features of the quantum formalism. Any formula of the language gives rise to a quantum circuit that transforms the density operator associated to the formula into the density operator associated to the atomic subformulas in a reversible way. The procedure goes from the whole to the parts against the compositionality-principle and gives rise to a semantic characterization for a new form of quantum logic that has been called “Łukasiewicz quantum computational logic”. It is interesting to compare the logic based on qubit-semantics with that on qudit-semantics. Having in mind the relationships between classical logic and Łukasiewicz-many valued logics, one could expect that the former is stronger than the fragment of the latter. However, this is not the case. From an intuitive point of view, this can be explained by recalling that the former is a very weak form of logic. Many important logical arguments, which are valid either in Birkhoff and von Neumann’s quantum logic or in classical logic, are generally violated.     

On the equivalence between logic programming semantics and argumentation semantics

In the current paper, we re-examine the connection between formal argumentation and logic programming from the perspective of semantics. We observe that one particular translation from logic programs to instantiated argumentation (the one described by Wu, Caminada and Gabbay) is able to serve as a basis for describing various equivalences between logic programming semantics and argumentation semantics. In particular, we are able to show equivalence between regular semantics for logic programming and preferred semantics for formal argumentation. We also show that there exist logic programming semantics (L-stable semantics) that cannot be captured by any abstract argumentation semantics.     

Dual‐Context Sequent Calculus and Strict Implication

We introduce a dual‐context style sequent calculus which is complete with respectto Kripke semantics where implication is interpreted as strict implication in the modal logic K. The cut‐elimination theorem for this calculus is proved by a variant of Gentzen's method.     

网络驱动的未识甲骨字特性及场景语义预测

甲骨学的研究具有重要的文化价值和传承意义,可以极大提高国家的文化自信。未识甲骨字的语义预测是甲骨学研究中最主要的问题,也是传统甲骨学研究中最棘手的问题。现有的计算机技术辅助研究方法无法预测未识甲骨字的语义。利用复杂网络对甲骨文进行了抽象和理解,并对未识甲骨字的场景语义进行预测。首先,以甲骨拓片为基础数据,通过建模构建甲骨字网络;其次,在甲骨字网络之上,分析未识甲骨字的重要性、信息丰富度、闭合性等特性,为预测未识甲骨字的场景语义提供理论依据;最后,根据网络特性和甲骨拓片的上下文语境预测未识甲骨字的场景语义。构建的未识甲骨字特性体系以及预测未识甲骨字的场景语义思路为破译其他未识甲骨字的语义奠定了基础,有助于推动甲骨文考释的进程。     

逻辑,语义和计算机科学中的一些基本思想

本文对理论计算机科学，特别是对其在逻辑与语义方面的基本思想作了一个直观易懂的综述，旨在使上述思想为希望在该领域开拓视野之士敞开大门。     

A universal compiler system based on production rules

This paper describes a compiler system which makes use of production rules for the translation. The source language syntax is defined in terms of a phrase structure grammar. Semantic rules are provided by an extension of the production rules, and special symbols are introduced for this purpose. Recognition of symbol strings is facilitated by a special syntactic filter routine. An example of a simple macro compiler is given to illustrate the basic concepts of the system.     

On the Approximation of Denotational Mu-Semantics

A signature gives rise to a language L(Var) by extending with variables x Var and binding constructs x and x, corresponding to least and greatest fixed points respectively. The natural denotational models for such languages are bicomplete dcpos as monotone -algebras. We prove that several approximating denotational semantics have the usual compositional semantics as their limit. These results provide techniques for relating syntactic and semantic concepts such as in full abstraction or completeness proofs. In the presence of an involutive antitone map on a bicomplete dcpo D we may translate the language L(Var) into one with least fixed points only such that meanings are preserved. This allows an approximative semantics where least and greatest fixed points are simultaneously approximated by unwindings in the syntax, provided that the limit semantics is substitutive. We discuss the principal difficulties of simultaneous unwindings in the absence of such semantic negations.     

Bisimulations between generalized Veltman models and Veltman models

Interpretability logic is an extension of provability logic. Veltman models and generalized Veltman models are two semantics for interpretability logic. We consider a connection between Veltman semantics and generalized Veltman semantics. We prove that for a complete image‐finite generalized Veltman modelW there is a Veltman model W ′ that is bisimular to W. (© 2008 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)