A functional logic for higher level reasoning about computation

In many areas of computation and reasoning, the value of an expression may depend on an implicit parameter, which may for example represent a program state, or time, or a possible world. In this paper we describe a formal first order logic which captures a general notion of expressions which depend on an implicit parameter. Both semantics and syntax are discussed. An important application of the logic, used as a running example, is to provide a basis for unifying the Hoare logic of procedural programs with the mathematically powerful techniques of classical logic and set theory. It is, however, beyond the scope of this paper to develop this application fully.     

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     

格值模态命题逻辑及其完备性

文中以满足第一及第二无限分配律的完备格为工具,建立了格值模态命题逻辑的语义理论,并指出这种语义是经典模态命题逻辑语义理论及[0,1]值模态命题逻辑语义理论的共同推广.给出了QMR0代数的定义,并分别以Boole代数及QMR0代数为背景构建了Boole型格值模态命题逻辑系统B及QMR0型格值模态命题逻辑系统QML*,并证明了系统B及系统QML*的完备性.     

Generic case completeness

In this note we introduce a notion of a generically (strongly generically) NP-complete problem and show that the randomized bounded version of the halting problem is strongly generically NP-complete.     

Uniqueness logic

A uniqueness type system is used to distinguish values which are referenced at most once from values which may be referenced an arbitrary number of times in a program. Uniqueness type systems are used in the Clean and Mercury programming languages to provide efficiently updatable data-structures and I/O without compromising referential transparency.     

用蒙太格文法解决汉语语义悖论

蒙太格文法是处理语法、语义和语用的典型方法,尤其在语义学方面独树一帜。通过对一个汉语语义悖论的安全分析,来表明Montague文法对于汉语语义悖论的解决,乃至对于整个汉语语义学的研究都具有非常重要的价值。     

概率逻辑、不确定逻辑和模糊逻辑之比较

通过一个实例分析比较了概率逻辑、主观概率逻辑、不确定逻辑和模糊逻辑的思想方法。提出了自己的观点：基于数据统计的概率逻辑是最科学的。不确定逻辑比主观概率逻辑更科学。当具有不确定性的原子命题具有独立性时,不确定逻辑和模糊逻辑的观点是一致的。而对于处理带有不确定性的相关性命题,不确定逻辑比模糊逻辑更科学。但是模糊逻辑在建立推理理论方面见长。     

Two theorems about the completeness of Hoare's logic

We prove two theorems about the completeness of Hoare's logic for the partial correctness of while-programs over an axiomatic specification. The first result is a completion theorem: any specification (Σ,E) can be refined to a specification (Σ₀, E₀), conservative over (Σ, E), whose Hoare's logic is complete. The second result is a normal form theorem: any complete specification (Σ, E) possessing some complete logic for partial correctness can be refined to an effective specification (Σ₀, E₀) conservative over (Σ, E), which generates all true partial correctness formulae with Hoare's standard rules.     

Empirical evidence for the usefulness of Armstrong relations in the acquisition of meaningful functional dependencies

Armstrong relations satisfy precisely those data dependencies that are implied by a given set of data dependencies. A common perception is that Armstrong relations are useful in the acquisition of data semantics, in particular since errors during the requirements elicitation have the most expensive consequences.     

For completeness, sublogarithmic space is no space

It is shown that for any class C closed under linear-time reductions, the complete sets for C under sublogarithmic reductions are also complete under 2DFA reductions, and thus are isomorphic under first-order reductions.     

A new generic scheme for functional logic programming with constraints

In this paper we propose a new generic scheme CFLP풟, intended as a logical and semantic framework for lazy Constraint Functional Logic Programming over a parametrically given constraint domain 풟. As in the case of the well known CLP풟 scheme for Constraint Logic Programming, 풟 is assumed to provide domain specific data values and constraints. CFLP풟 programs are presented as sets of constrained rewrite rules that define the behavior of possibly higher order and/or non-deterministic lazy functions over 풟. As a main novelty w.r.t. previous related work, we present a Constraint Rewriting Logic CRWL풟 which provides a declarative semantics for CFLP풟 programs. This logic relies on a new formalization of constraint domains and program interpretations, which allows a flexible combination of domain specific data values and user defined data constructors, as well as a functional view of constraints. This research has been partially supported by the Spanish National Projects MELODIAS (TIC2002-01167), MERIT-FORMS (TIN2005-09207-C03-03) and PROMESAS-CAM (S-0505/TIC/0407).     

Adapting functional programs to higher order logic

Higher-order logic proof systems combine functional programming with logic, providing functional programmers with a comfortable setting for the formalization of programs, specifications, and proofs. However, a possibly unfamiliar aspect of working in such an environment is that formally establishing program termination is necessary. In many cases, termination can be automatically proved, but there are useful programs that diverge and others that always terminate but have difficult termination proofs. We discuss techniques that support the expression of such programs as logical functions. Electronic Supplementary Material  The online version of this article () contains supplementary material, which is available to authorized users.     

Kailar逻辑的改进及应用

综合Kailar逻辑和SVO逻辑两种协议分析方法的优点,借助SVO逻辑的思想对Kailar逻辑进行了改进,使其更好地应用于不可否认协议的可追究性分析和设计。同时,将改进后的Kailar逻辑应用在类NG协议的分析中,分析结果证明了该协议可追究方面的安全性质。     

The logic of Peirce algebras

Peirce algebras combine sets, relations and various operations linking the two in a unifying setting. This paper offers a modal perspective on Peirce algebras. Using modal logic a characterization of the full Peirce algebras is given, as well as a finite axiomatization of their equational theory that uses so-called unorthodox derivation rules. In addition, the expressive power of Peirce algebras is analyzed through their connection with first-order logic, and the fragment of first-order logic corresponding to Peirce algebras is described in terms of bisimulations.     

Eliminating the substitution axiom from UNITY logic

The UNITY substitution axiom, if (x=y) is an invariant of a program, then x can be replaced by y in any property of the program, is problematic for several reasons. In this paper, dual predicate transformerssst andwst are introduced that allow the strongest invariant of a program to be expressed, and these are used to give new definitions for the temporal operatorsunless andensures. With the new definitions, the substitutionaxiom is no longer needed, and can be replaced by a derived rule of inference which is formally justified in the logic. One important advantage is that the effects of the initial conditions on the properties of a program are formally captured in a convenient way, and one can forget about substitution in formal treatments of the UNITY proof system while still having it available when desirable to use during the derivation of programs. Composibility and completeness of the modified logic are also discussed.     

The logic of message-passing

Message-passing is a key ingredient of concurrent programming. The purpose of this paper is to describe the equivalence between the proof theory, the categorical semantics, and term calculus of message-passing. In order to achieve this we introduce the categorical notion of a linear actegory and the related polycategorical notion of a poly-actegory. Not surprisingly the notation used for the term calculus borrows heavily from the (synchronous) π-calculus. The cut-elimination procedure for the system provides an operational semantics.     

A PSO based integrated functional link net and interval type-2 fuzzy logic system for predicting stock market indices

This paper presents an integrated functional link interval type-2 fuzzy neural system (FLIT2FNS) for predicting the stock market indices. The hybrid model uses a TSK (Takagi-Sugano-Kang) type fuzzy rule base that employs type-2 fuzzy sets in the antecedent parts and the outputs from the Functional Link Artificial Neural Network (FLANN) in the consequent parts. Two other approaches, namely the integrated FLANN and type-1 fuzzy logic system and Local Linear Wavelet Neural Network (LLWNN) are also presented for a comparative study. Backpropagation and particle swarm optimization (PSO) learning algorithms have been used independently to optimize the parameters of all the forecasting models. To test the model performance, three well known stock market indices like the Standard's & Poor's 500 (S&P 500), Bombay stock exchange (BSE), and Dow Jones industrial average (DJIA) are used. The mean absolute percentage error (MAPE) and root mean square error (RMSE) are used to find out the performance of all the three models. Finally, it is observed that out of three methods, FLIT2FNS performs the best irrespective of the time horizons spanning from 1 day to 1 month.     

部分多值逻辑中单纯可离和完满对称关系的计数

根据部分多值逻辑的完备性理论,对两类准完备集——单纯可离函数集和完满对称函数集进行研究,给出了单纯可离和完满对称关系的函数的计数公式。     

On the role of logical connectives for primality and functional completeness of algebras of logics

We consider certain finite universal algebras arising from algebraic semantics in implicational logics. They contain a binary operation → and two constants 0 and 1 satisfying the axioms 0→x=x→1=x→x=1 and 1→x=x valid in most implicational logics. We characterize the completeness (also called primality) of such algebras, i.e. the property that every finitary operation on their universe is a term operation of the algebra (in other words, it is a composition of the basic operations of the algebra). Using clone theory and the knowledge of maximal clones we describe completeness (functional completeness) in terms of nonpreservation of three types of specific relations. If → has a simple property and the algebra contains a binary operation ⊙ with a neutral element 1 and a unary operation ¬ satisfying ¬(1)=0 and ¬x=1 otherwise, the algebra is functionally complete.