Some primitives for the portable programming of array and vector processors

A high-level language for array and vector processors is analyzed by the methods of denotational semantics. The analysis leads to the identification of a set of primitives suitable for the portable programming of array and vector processors. Discussion of the primitives includes consideration of the efficiency with which they may be implemented on different machines, and their possible application to portable programming, the design of intermeiate languages, and the design of future array and vector processors.     

A language for linking modules into systems

A variant of the static part of Milner's languageCCS is presented. It can be used for describing the construction of systems from modules, where the interconnection between modules is either export-import relationships of, for instance, procedures and types, or alternatively many-to-one communication channels. The semantics of the language is specified on two levels, the exterior level and the interior level. The exterior level semantics determines the legality of expressions, given externally visible properties of their constituent modules, while the interior level semantics associates a certain class of labeled directed graphs with expressions of the language.     

Constructive theory of enumerable species

A constructive semantics for the language of set theory with atoms based on interpreting set variables by enumerable species is defined. The soundness of the axioms of the Zermelo–Fraenkel set theory with this semantics is completely studied.     

Strategies and simulations in a semantic framework

By means of several examples of structural operational semantics for a variety of languages, we justify the importance and interest of using the notions of strategies and simulations in the semantic framework provided by rewriting logic and implemented in the Maude metalanguage. On the one hand, we describe a basic strategy language for Maude and show its application to CCS, the ambient calculus, and the parallel functional language Eden. On the other hand, we show how the concept of stuttering simulation can be used inside Maude to show that a stack machine correctly implements the operational semantics of a simple functional language.     

The semantics of realizability for the constructive set theory based on hyperarithmetical predicates

A semantics of realizability based on hyperarithmetical predicates of membership is introduced for formulas of the language of set theory. It is proved that the constructive set theory without the extensionality axiom is sound with this semantics.     

L.P.L. a fuzzy programming language: 1. Syntactic aspects

The L.P.L. language (Linguistic oriented Programming Language) that we shall present in this paper and in a forthcoming one is a new language aiming at an implementation of the concepts of the fuzzy sets theory. In the first paper, after an introduction to the basic concepts. we shall describe the syntactic aspects of L.P.L., i.e., the data declarations structure, the statements structure, the general structure of L.P.L. models. The second paper will deal first with the basic semantic and the semantics of logical expressions, then the semantics of basic statements as well as the semantics of the control structure of programs.     

Logic, language games and ludics

Wittgenstein’s language games can be put into a wider service by virtue of elements they share with some contemporary opinions concerning logic and the semantics of computation. I will give two examples: manifestations of language games and their possible variations in logical studies, and their role in some of the recent developments in computer science. It turns out that the current paradigm of computation that Girard termed Ludics bears a striking resemblance to members of language games. Moreover, the kind of interrelations that are emerging could be scrutinised from the viewpoint of logic that virtually necessitates game-theoretic conceptualisations, demonstrating the fact that the meaning of utterances may, in many situations, be understood as Wittgenstein’s language games of ‘showing or telling what one sees’. This provides motivation for the use of games in relation to logic and formal semantics that some commentators have called for. Many of the ideas can be traced to C.S. Peirce, for whom signs were vehicles of strategic communication. The conclusion about Wittgenstein is that the notions of saying and showing converge in his late philosophy.     

On hyperarithmetical realizability

The notion of hyperarithmetical realizability is introduced for various extensions of the language of formal arithmetic. The correctness of classical, intuitionistic, and basic logic with respect to the semantics based on hyperarithmetical realizability is studied.     

Interactions Between Natural Language and Mathematical Structures: The Case of "Wordwalking"

In the course of solving relatively routine word problems, 7th-grade students sometimes made a substitution of a word or phrase in the original problem statement. The substitutions discussed here appeared insignificant because the natural language meaning overlapped with that of the replaced word or phrase, but they had major consequences mathematically because they affected the mathematical structure that modeled the resulting problem statement. The term wordwalking was coined to refer to such substitutions. Wordwalking was observed during qualitative data reduction required for the coding of a quantitative study. The relative ambiguity of natural language and the precision of mathematical expressions are invoked to explain the dynamics of wordwalking.     

Interactions Between Natural Language and Mathematical Structures: The Case of Wordwalking

In the course of solving relatively routine word problems, 7th-grade students sometimes made a substitution of a word or phrase in the original problem statement. The substitutions discussed here appeared insignificant because the natural language meaning overlapped with that of the replaced word or phrase, but they had major consequences mathematically because they affected the mathematical structure that modeled the resulting problem statement. The term wordwalking was coined to refer to such substitutions. Wordwalking was observed during qualitative data reduction required for the coding of a quantitative study. The relative ambiguity of natural language and the precision of mathematical expressions are invoked to explain the dynamics of wordwalking.     

Non-Deterministic Closure Theory and Universal Arrows

Traditional closure theory discusses the closure operations on orders with graph-theoretic methods, or the reflectors on skeletal categories with category-theoretic methods. Both approaches are confined, like most of classical mathematics, to total and deterministic operations. So traditional closure theory makes it possible to define the semantics of the while-do commands only for terminating and deterministic programming. This paper outlines a closure theory for relations which transcend totality and determinism. For the sake of conciseness, the language used is that of graph theory but the methods are category-theoretic and some hints are offered for a possible translation into the language of category theory. Our basic idea is that closure relations consist of universal arrows in the sense of category theory. The new closure theory is appropriate for defining a semantics of the while-do commands both for terminating, deterministic programming and for non-terminating, non-deterministic programming.     

Tactics for Hierarchical Proof

There is something of a discontinuity at the heart of popular tactical theorem provers. Low-level, fully-checked mechanical proofs are large trees consisting of primitive logical inferences. Meanwhile, high-level human inputs are lexically structured formal texts which include tactics describing search procedures. The proof checking process maps from the high-level to low-level, but after that, explicit connections are usually lost. The lack of connection can make it difficult to understand the proof trees produced by successful tactic proofs, and difficult to debug faulty tactic proofs. We propose the use of hierarchical proofs, also known as hiproofs, to help bridge these levels. Hiproofs superimpose a labelled hierarchical nesting on an ordinary proof tree, abstracting from the underlying logic. The labels and nesting are used to describe the organisation of the proof, typically relating to its construction process. In this paper we introduce a foundational tactic language Hitac which constructs hiproofs in a generic setting. Hitac programs can be evaluated using a big-step or a small-step operational semantics. The big-step semantics captures the intended meaning, whereas the small-step semantics is closer to possible implementations and provides a unified notion of proof state. We prove that the semantics are equivalent and construct valid proofs. We also explain how to detect terms which are stuck in the small-step semantics, and how these suggest interaction points with debugging tools. Finally we show some typical examples of tactics, constructed using tactical combinators, in our language.     

Toward a language theoretic proof of the four color theorem

This paper considers the problem of showing that every pair of binary trees with the same number of leaves parses a common word under a certain simple grammar. We enumerate the common parse words for several infinite families of tree pairs and discuss several ways to reduce the problem of finding a parse word for a pair of trees to that for a smaller pair. The statement that every pair of trees has a common parse word is equivalent to the statement that every planar graph is four-colorable, so the results are a step toward a language theoretic proof of the four color theorem.     

Source program optimization with a generalized FOR statement

A generalized FOR statement which includes multiple control variables was found to be a very powerful tool at the source program level for writing efficient FOR loops. This design of a generalized FOR statement grew out of a requirement to design a language that could be translated into efficient code with (almost) no optimizations done by its compiler.     

On access to temporary resources

The shareable resources of a multiprogramming system can be classified as either permanent or temporary, and their use can be classified as either exclusive or non-exclusive. While semaphores, as defined by Dijkstra synchronize access to permanent resources, this article proposes two new primitives for synchronizing access to temporary resources. Their usefulness is demonstrated by examining the problem of a number of concurrent «readers» and »writers« sharing a single file. Finally, a high-level language notation is proposed which synchronizes access to a declared, shareable resource of any of the categories classified above.     

悖论与数学基础问题(Ⅲ)

本文主要讨论恶性循环原则与类型混淆原则的划分。这是由于我们在一些场合发现有把两个原则混为一谈的情形而引起的。在这个讨论中,我们把“非直谓定义法”划分为广义、狭义和等价式三种情形。本来是没有这种划分的,现在这样做,首先是因为Russell的恶性循环原则指出:‘没有一个整体能包含一个只能借助于这个整体定义的元素’,既有‘只能’,当然应有‘并非只能’的情形。因此,‘只能’和‘并非只能’将是可以得到区分的。另外,‘总体G就是被定义的对象H’显然是‘只能借助总体G来定义H’的一个特殊情形,因此,‘只能’和‘等价式’也将是可以区分的。而对非直谓定义法作了如上的划分之后,将有助于我们对恶性循环原则与类型混淆原则的直观性了解,因之针对等价式非直谓的类型混     

Probabilization of Logics: Completeness and Decidability

The probabilization of a logic system consists of enriching the language (the formulas) and the semantics (the models) with probabilistic features. Such an operation is said to be exogenous if the enrichment is done on top, without internal changes to the structure, and is called endogenous otherwise. These two different enrichments can be applied simultaneously to the language and semantics of a same logic. We address the problem of studying the transference of metaproperties, such as completeness and decidability, to the exogenous probabilization of an abstract logic system. First, we setup the necessary framework to handle the probabilization of a satisfaction system by proving transference results within a more general context. In this setup, we define a combination mechanism of logics through morphisms and prove sufficient condition to guarantee completeness and decidability. Then, we demonstrate that probabilization is a special case of this exogenous combination method, and that it fulfills the general conditions to obtain transference of completeness and decidability. Finally, we motivate the applicability of our technique by analyzing the probabilization of the linear temporal logic over Markov chains, which constitutes an endogenous probabilization. The results are obtained first by studying the exogenous semantics, and then by establishing an equivalence with the original probabilization given by Markov chains.     

A simple logic for reasoning about incomplete knowledge

The semantics of modal logics for reasoning about belief or knowledge is often described in terms of accessibility relations, which is too expressive to account for mere epistemic states of an agent. This paper proposes a simple logic whose atoms express epistemic attitudes about formulae expressed in another basic propositional language, and that allows for conjunctions, disjunctions and negations of belief or knowledge statements. It allows an agent to reason about what is known about the beliefs held by another agent. This simple epistemic logic borrows its syntax and axioms from the modal logic KD. It uses only a fragment of the S5 language, which makes it a two-tiered propositional logic rather than as an extension thereof. Its semantics is given in terms of epistemic states understood as subsets of mutually exclusive propositional interpretations. Our approach offers a logical grounding to uncertainty theories like possibility theory and belief functions. In fact, we define the most basic logic for possibility theory as shown by a completeness proof that does not rely on accessibility relations.