Logic, Language, Information and Computation

Model-checking regular properties is well established and a powerful verification technique for regular as well as context-free program behaviours. Recently, through the use of ω-visibly pushdown languages (ωVPLs), defined by ω-visibly pushdown automata, model-checking of properties beyond regular expressiveness was made possible and shown to be still decidable even when the program’s model of behaviour is an ωVPL. In this paper, we give a grammatical representation of ωVPLs and the corresponding finite word languages – VPL. From a specification viewpoint, the grammatical representation provides a more natural representation than the automata approach.

Pregroup grammars are a context-free grammar formalism introduced as a simplification of Lambek calculus. This formalism is interesting for several reasons: the syntactical properties of words are specified by a set of types like the other type-based grammar formalisms ; as a logical model, compositionality is easy ; a polytime parsing algorithm exists.

However, this formalism is not completely lexicalized because each pregroup grammar is based on the free pregroup built from a set of primitive types together with a partial order, and this order is not lexical information. In fact, only the pregroup grammars that are based on primitive types with an order that is equality can be seen as fully lexicalized.

We show here how we can transform, using a morphism on types, a particular pregroup grammar into another pregroup grammar that uses the equality as the order on primitive types. This transformation is at most quadratic in size (linear for a fixed set of primitive types), it preserves the parse structures of sentences and the number of types assigned to a word.

Triangular norms or t-norms, in short, and automorphisms are very useful to fuzzy logics in the narrow sense. However, these notions are usually limited to the set [0,1].

In this paper we will consider a generalization of the t-norm notion for arbitrary bounded lattices as a category where these generalized t-norms are the objects and generalizations of automorphisms are the morphisms of the category. We will prove that, this category is an interval category, which roughly means that it is a Cartesian category with an interval covariant functor.

Being able to automatically analyze the search spaces of automated theorem provers is of the greatest importance. A method is proposed to do that. It is inspired by inductive tasks (e.g. discovering in mathematics and natural sciences). The key idea is to replace implicit genetic descriptions of the consequences in search spaces (i.e. the problem specification) by structural ones (describing the form of such consequences). The approach profits from the expressive power of term schematization languages and from the capabilities offered by existing powerful symbolic computation systems (Mathematica,...). A running software based on these ideas show evidence of the adequacy of the approach.

Categorial grammars in the tradition of Lambek [1,2] are asymmetric: sequent statements are of the form \({\Gamma}\Rightarrow{A}\), where the succedent is a single formula A, the antecedent a structured configuration of formulas A ₁,...,A _n . The absence of structural context in the succedent makes the analysis of a number of phenomena in natural language semantics problematic. A case in point is scope construal: the different possibilities to build an interpretation for sentences containing generalized quantifiers and related expressions. In this paper, we explore a symmetric version of categorial grammar based on work by Grishin [3]. In addition to the Lambek product, left and right division, we consider a dual family of type-forming operations: coproduct, left and right difference. Communication between the two families is established by means of structure-preserving distributivity principles. We call the resulting system LG. We present a Curry-Howard interpretation for derivations. Our starting point is Curien and Herbelin’s sequent system for λμ calculus [4] which capitalizes on the duality between logical implication (i.e. the Lambek divisions under the formulas-as-types perspective) and the difference operation. Importing this system into categorial grammar requires two adaptations: we restrict to the subsystem where linearity conditions are in effect, and we refine the interpretation to take the left-right symmetry and absence of associativity/commutativity into account. We discuss the continuation-passing-style (CPS) translation, comparing the call-by-value and call-by-name evaluation regimes. We show that in the latter (but not in the former) the types of LG are associated with appropriate denotational domains to enable a proper treatment of scope construal.

We write strategies for both players in the Ehrenfeucht-Fraisse game played between two linear orders. We prove that our strategies win whenever possible. The strategy in a game of fixed, finite length focuses the attention of both players on certain finite sets called ”total information.” These finite sets are semimodels in the sense that if one player does not have a winning strategy, then the other player can win, even when forced to choose only elements of a model which are indicated by the total information.

These sets are semimodels– finite, nested models, such that a formula is satisfied in a linear order iff the formula is semimodel-satisfied in the corresponding semimodel. The strategy implies the decidability of the theory of linear order, and gives a completion of any formula by one with quantifier rank only 2 larger than the original formula. The strategy generalizes directly to the infinitary theory of linear order.

In this paper, hybrid logic is used to formulate a rational reconstruction of a previously published control flow analysis for the mobile ambients calculus and we further show how a more precise flow-sensitive analysis, that takes the ordering of action sequences into account, can be formulated in a natural way. We show that hybrid logic is very well suited to express the semantic structure of the ambient calculus and how features of hybrid logic can be exploited to reduce the “administrative overhead” of the analysis specification and thus simplify it. Finally, we use HyLoTab, a fully automated theorem prover for hybrid logic, both as a convenient platform for a prototype implementation as well as to formally prove the correctness of the analysis.

The paper proposes an account of the contrast (noticed in [9]) between the interpretations of the following two discourses: Harvey courts a girl at every convention. {She is very pretty. vs. She always comes to the banquet with him.}. The initial sentence is ambiguous between two quantifier scopings, but the first discourse as a whole allows only for the wide-scope indefinite reading, while the second allows for both. This cross-sentential interaction between quantifier scope and anaphora is captured by means of a new dynamic system couched in classical type logic, which extends Compositional DRT ([16]) with plural information states (modeled, following [24], as sets of variable assignments). Given the underlying type logic, compositionality at sub-clausal level follows automatically and standard techniques from Montague semantics become available. The paper also shows that modal subordination (A wolf might come in. It would eat Harvey first) can be analyzed in a parallel way, i.e. the system captures the anaphoric and quantificational parallels between the individual and modal domains argued for in . In the process, we see that modal/individual-level quantifiers enter anaphoric connections as a matter of course, usually functioning simultaneously as both indefinites and pronouns.

Condensed BCK-logic, i.e. the set of BCK-theorems provable by the condensed detachment rule of Carew Meredith, has been shown to be exactly the set of principal types of BCK-λ-terms. In 1993 Sachio Hirokawa gave a characterization of the set of principal types of BCK-λ-terms in β-normal form based on a relevance relation that he defined between the type variables in a type. We define a symmetric notion of this and call it dependence relation. Then, using the notion of β _S -reduction introduced by de Groote, we obtain a characterization of the complete set of principal types of BCK-λ-terms.

We describe a simple and efficiently implementable grammatical architecture for generating dependency trees from meaning structures. It is represented by finite state tree top-down transducers applied to feature trees to convert them into sequences of typed forms (typed sentences). The correctness of the generated types is checked using a simple and efficient dependency calculus. The corresponding dependency structure is extracted from the correctness proof. Using an English example, it is demonstrated that this transduction can be carried out incrementally in the course of composition of the meaning structure.

The concept of pregroup was introduced by Lambek for natural language analysis, with a close link to non-commutative linear logic. We reformulate the pregroup calculus so as to extend it by composition with other logics and calculii.The cut elimination property and the decidabilityproperty of the sequent calculus proposed in the article are shown.Properties of composed calculii are also discussed.

In informal mathematical usage we often reason using languages with binding. We usually find ourselves placing capture-avoidance constraints on where variables can and cannot occur free. We describe a logical derivation system which allows a direct formalisation of such assertions, along with a direct formalisation of their constraints. We base our logic on equality, probably the simplest available judgement form. In spite of this, we can axiomatise systems of logic and computation such as first-order logic or the lambda-calculus in a very direct and natural way. We investigate the theory of derivations, prove a suitable semantics sound and complete, and discuss existing and future research.

Highly accurate positioning systems and new broadcasting technology have enabled air traffic management concepts where the responsibility for aircraft separation resides on pilots rather than on air traffic controllers. The Formal Methods Group at the National Institute of Aerospace and NASA Langley Research Center has proposed and formally verified an algorithm, called KB3D, for distributed three dimensional conflict resolution. KB3D computes resolution maneuvers where only one component of the velocity vector, i.e., ground speed, vertical speed, or heading, is modified. Although these maneuvers are simple to implement by a pilot, they are not necessarily optimal from a geometrical point of view. In general, optimal resolutions require the combination of all the components of the velocity vector. In this paper, we propose a two dimensional version of KB3D, which we call KB2D, that computes resolution maneuvers that are optimal with respect to ground speed and heading changes. The algorithm has been mechanically verified in the Prototype Verification System (PVS). The verification relies on algebraic proof techniques for the manipulation of the geometrical concepts relevant to the algorithm as well as standard deductive techniques available in PVS.

We introduce numerical constraints into the context of XML which restrict the number of nodes within subtrees of an XML tree that contain specific value-equal subnodes. We demonstrate the applicability of numerical constraints by optimising XML queries and predicting the number of XML query answers, updates and encryptions.

Inspired by the classical theory of modules over a monoid, we give a first account of the natural notion of module over a monad. The associated notion of morphism of left modules (”linear” natural transformations) captures an important property of compatibility with substitution, in the heterogeneous case where ”terms” and variables therein could be of different types as well as in the homogeneous case. In this paper, we present basic constructions of modules and we show examples concerning in particular abstract syntax and lambda-calculus.

Hydra games were introduced by Kirby and Paris, for the formulation of a result which is independent from Peano arithmetic but depends on the transfinite structure of ε ₀. Tree ordinals are a well-known simple way to represent countable ordinals. In this paper we study the relation between these concepts; an ordinal less than ε ₀ is canonically translated into both a hydra and a tree ordinal term, and the reduction graph of the hydra and the normal form of the term syntactically correspond to each other.

In this paper, we explore the Lambek-Grishin calculus \(\textbf{LG}\): a symmetric version of categorial grammar based on the generalizations of Lambek calculus studied in Grishin [1]. The vocabulary of \(\textbf{LG}\) complements the Lambek product and its left and right residuals with a dual family of type-forming operations: coproduct, left and right difference. The two families interact by means of structure-preserving distributivity principles. We present an axiomatization of \(\textbf{LG}\) in the style of Curry’s combinatory logic and establish its decidability. We discuss Kripke models and Curry-Howard interpretation for \(\textbf{LG}\) and characterize its notion of type similarity in comparison with the other categorial systems. From the linguistic point of view, we show that \(\textbf{LG}\) naturally accommodates non-local semantic construal and displacement — phenomena that are problematic for the original Lambek calculi.

We survey several computational interpretations of classical linear logic based on two-player one-move games. The moves of the games are higher-order functionals in the language of finite types. All interpretations discussed treat the exponential-free fragment of linear logic in a common way. They only differ in how much advantage one of the players has in the exponentials games. We discuss how the several choices for the interpretation of the modalities correspond to various well-known functional interpretations of intuitionistic logic, including Gödel’s Dialectica interpretation and Kreisel’s modified realizability.

The particular molecular-scale devices that are the topic of this article are known as DNA nanostructures. As will be explained, DNA nanostructures have some unique advantages among nanostructures: they are relatively easy to design, fairly predictable in their geometric structures, and have been experimentally implemented in a growing number of labs around the world. They are constructed primarily of synthetic DNA. A key principle in the study of DNA nanostructures is the use of self-assembly processes to actuate the molecular assembly. Since self-assembly operates naturally at the molecular scale, it does not suffer from the limitation in scale reduction that so restricts lithography or other more conventional top-down manufacturing techniques.

The aim of this work is to analyze the interval canonical representation for fuzzy QL-implications and automorphisms. Intervals have been used to model the uncertainty of a specialist’s information related to truth values in the fuzzy propositional calculus: the basic systems are based on interval fuzzy connectives. Thus, using subsets of the real unit interval as the standard sets of truth degrees and applying continuous t-norms, t-conorms and negation as standard truth interval functions, the standard truth interval function of an QL-implication can be obtained. Interesting results on the analysis of interval canonical representation for fuzzy QL-implications and automorphisms are presented. In addition, commutative diagrams are used in order to understand how an interval automorphism acts on interval QL-implications, generating other interval fuzzy QL-implications.

We study the set T _A of infinite binary trees with nodes labelled in a semiring A from a coalgebraic perspective. We present coinductive definition and proof principles based on the fact that T _A carries a final coalgebra structure. By viewing trees as formal power series, we develop a calculus where definitions are presented as behavioural differential equations. We present a general format for these equations that guarantees the existence and uniqueness of solutions. Although technically not very difficult, the resulting framework has surprisingly nice applications, which is illustrated by various concrete examples.

This paper proposes a semiring formulation for reasoning about an agent’s changing beliefs: a dynamic epistemic semiring (DES ). A DES  is a modal semiring extended with epistemic-action operators. The paper concentrates on the revision operator by proposing an axiomatisation, developing a basic calculus and deriving the classical AGM revision axioms in the algebra.

Ant Colony Optimization (ACO) is a metaheuristic inspired by the foraging behavior of ant colonies that has been successful in the resolution of hard combinatorial optimization problems. This work proposes MaxMin-SAT, an ACO alternative for the satisfiability problem (SAT). MaxMin-SAT is the first ACO algorithm for SAT that implements an Adaptive Fitness Function, which is a technique used for Genetic Algorithms to escape local optima. To show effectiveness of this technique, three different adaptive fitness functions are compared: Stepwise Adaptation of Weights, Refining Functions, and a mix of the previous two. To experimentally test MaxMin-SAT, a comparison with Walksat (a successful local search algorithm) is presented. Even though MaxMin-SAT cannot beat Walksat when dealing with phase transition instances, experimental results show that it can be competitive with the local search heuristic for overconstrained instances.