An algebraic semantics of higher-order types with subtypes

This paper extends order-sorted algebras with higher-order functions. The aim is to present a new semantics for higher-order order-sorted types in functional programming, data type specification and program transformation. Our framework unifies higher-order functions, equational deduction, overloading and subtype polymorphism.     

Towards Behavioral Maude: Behavioral Membership Equational Logic

How can algebraic and coalgebraic specifications be integrated? How can behavioral equivalence be addressed in an algebraic specification language? The hidden-sorted approach, originating in work of Goguen and Meseguer in the early 80's, and further developed into the hidden-sorted logic approach by researchers at Oxford, UC San Diego, and Kanazawa offers some attractive answers, and has been implemented in both BOBJ and CafeOBJ. In this work we investigate both further extensions of hidden logic, and an extension of the Maude specification language called BMaude supporting this extended hidden-sorted semantics.Maude's underlying equational logic, membership equational logic, generalizes and increases the expressive power of many-sorted and order-sorted equational logics. We develop a hidden-sorted extension of membership equational logic, and give conditions under which theories have both an algebraic and a coalgebraic semantics, including final (co-)algebras. We also discuss the language design of BMaude, based on such an extended logic and using categorical notions in and across the different institutions involved. We also explain how Maude's reflective semantics provides a systematic method to extend Maude to BMaude within Maude, including module composition operations, evaluation, and automated proof methods.     

Explicit graphs in a functional model for spatial databases

Observing that networks are ubiquitous in applications for spatial databases, we define a new data model and query language that especially supports graph structures. This model integrates concepts of functional data modeling with order-sorted algebra. Besides object and data type hierarchies, graphs are available as an explicit modeling tool, and graph operations are part of the query language. Graphs have three classes of components, namely, nodes, edges, and explicit paths. These are at the same time object types within the object type hierarchy and can be used like any other type. Explicit paths are useful because real-world objects often correspond to paths in a network. Furthermore, a dynamic generalization concept is introduced to handle heterogeneous collections of objects in a query. In connection with spatial data types, this leads to powerful modeling and querying capabilities for spatial databases, in particular for spatially embedded networks such as highways, rivers, public transport, and so forth. We use multilevel order-sorted algebra as a formal framework for the specification of our model. Roughly spoken, the first-level algebra defines types and operations of the query language, whereas the second-level algebra defines kinds (collections of types) and type constructors as functions between kinds, and so provides the types that can be used at the first level     

Modules over monads and initial semantics

Inspired by the classical theory of modules over a monoid, we introduce 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, not only in the so-called homogeneous case but also in the heterogeneous case where “terms” and variables therein could be of different types. In this paper, we present basic constructions of modules and we show how modules allow a new point of view concerning higher-order syntax and semantics.     

Circular expressions: elimination of static environments

Consider the connection between denotational semantics for a language with goto statements and flow diagrams for programs in such a language. The main point of interest is that the denotational semantics uses a recursively defined environment to give the meaning of labels, while a flow diagram merely has a jump to the appropriate program point. A simple reduction called “indirection elimination” strips away the environment from the denotational semantics and extracts an expression with cycles that is very close to the flow diagram of a program. The same idea applies to associating bodies with recursive procedures, or to any construct whose semantics is not wedded to the syntax. In addition to being a useful data structure and conceptual device, expressions with cycles are well defined mathematical objects—their semantics can be given by unfolding them into infinite structures that have been well studied. The practicality of the elimination of environments has been tested by constructing a trial implementation, which serves as the front end of a semantics directed compiler generator. The implementation takes a denotational semantics of a language and constructs a “black box” that maps programs in the language into an intermediate representation. The intermediate representation is a circular expression.     

句法网与语义网的对比研究

基于网络观的语言研究已经成为语言分析的趋势之一。但不同语言单位层级、不同语言单位关系的选取导致了语言网络的差异。从词的同现网到句法网再到语义网所需要的语言学知识也逐步深化,该文旨在构建语义学理论支撑的语义网络,并把虚词纳入语义分析过程,分别以句法关系和语义关系作为联结,用Cytoscape构建了句法网和语义网。结果发现: 语义网的直径、平均最短距离比句法网大,层级性比句法网差,聚集系数比句法网小,虚词节点“的”“和”“个”等有可能是局部的中心节点。     

Denotational and operational semantics for prolog

The semantics of PROLOG programs is usually given in terms of the model theory of first-order logic. However, this does not adequately characterizethe computational behavior of PROLOG programs. PROLOG implementations typically use a sequential evaluation strategy based on the textual order of clauses and literals in a program, as well as nonlogical features like cut. In this work we develop a denotational semantics that captures thecomputational behavior of PROLOG. We present a semantics for “cut-free” PROLOG, which is then extended to PROLOG with cut. For each case we develop a congruence proof that relates the semantics to a standard operational interpreter. As an application of our denotational semantics, we show the correctness of some standard “folk” theorems regarding transformations on PROLOG programs.     

Semantics,dynamics tradeoff in relational database design

This paper gives some objections to the artificial separation of the semantics and dynamics aspects of the application during the database design process. It is suggested that both aspects of the application should play a role throughout the design stages (logical and physical) in order to produce a workable schema that captures the real usage picture of the intended application. A simple method that “trades” semantics and dynamics is proposed to provide a common yardstick to measure the “goodness” of the database design. To narrow the scope of the problem a bit, we will concentrate on the database design for the relational model.     

From Interface to Correspondence: Recovering Classical Representations in a Pragmatic Theory of Semantic Information

One major fault line in foundational theories of cognition is between the so-called “representational” and “non-representational” theories. Is it possible to formulate an intermediate approach for a foundational theory of cognition by defining a conception of representation that may bridge the fault line? Such an account of representation, as well as an account of correspondence semantics, is offered here. The account extends previously developed agent-based pragmatic theories of semantic information, where meaning of an information state is defined by its interface role, to a theory that accommodates a notion of representation and correspondence semantics. It is argued that the account can be used to develop an intermediate approach to cognition, by showing that the major sources of tension between “representational” and “non-representational” theories may be eased.     

Interpreting Abstract Interpretations in Membership Equational Logic

We present a logical framework in which abstract interpretations can be naturally specified and then verified. Our approach is based on membership equational logic which extends equational logics by membership axioms, asserting that a term has a certain sort. We represent an abstract interpretation as a membership equational logic specification, usually as an overloaded order-sorted signature with membership axioms. It turns out that, for any term, its least sort over this specification corresponds to its most concrete abstract value. Maude implements membership equational logic and provides mechanisms to calculate the least sort of a term efficiently. We first show how Maude can be used to get prototyping of abstract interpretations “for free.” Building on the meta-logic facilities of Maude, we further develop a tool that automatically checks an abstract interpretation against a set of user-defined properties. This can be used to select an appropriate abstract interpretation, to characterize the specific loss of information during abstraction, and to compare different abstractions with each other.     

The calculus of context relations

We present the theory of context relations. Context relations are a method for incremental semantic analysis in language-specific editors, which is able to handle incomplete program fragments. The algorithm is generated from the definition of a language's static semantics and is based on inference rules and order-sorted unification. The paper presents the underlying mathematical theory, optimal incremental analysis algorithms, handling of user-defined polymorphism and overloading, and implementation issues. It is intended as the concluding report on a by now mature concept, which has successfully been used to generate efficient incremental type inferencers for languages like ADA and Fortran 8x.     

判别增强的生成对抗模型在文本至图像生成中的研究与应用

目前大部分基于生成对抗网络GAN的文本至图像生成算法着眼于设计不同模式的注意力生成模型,以提高图像细节的刻画与表达,但忽略了判别模型对局部关键语义的感知,以至于生成模型可能生成较差的图像细节“欺骗“判别模型。提出了判别语义增强的生成对抗网络DE-GAN模型,试图在判别模型中设计词汇-图像判别注意力模块,增强判别模型对关键语义的感知和捕捉能力,驱动生成模型生成高质量图像细节。实验结果显示,在CUB-Bird数据集上,DE-GAN在IS指标上达到了4.70,相比基准模型提升了4.2%,达到了较高的性能表现。     

An order-sorted query system for sort, predicate, and meta-predicate hierarchies

This paper presents a decidable order-sorted query system for reasoning between ontologies and rules. We describe order-sorted logic programming with sort, predicate, and meta-predicate hierarchies (OSL_3h), which derives predicate and meta-predicate assertions. Meta-level predicates (predicates of predicates) are useful for representing relationships between predicate formulas, and further, they conceptually yield a hierarchy similar to the hierarchies of sorts and predicates. By extending the order-sorted Horn-clause calculus, we develop a query-answering system in OSL_3h that can answer queries such as atoms and meta-atoms generalized by containing predicate variables. We show that the expressive query-answering system computes every generalized query in single exponential time, that is, the complexity of our query system is equal to that of DATALOG.     

A three-valued semantics for querying and repairing inconsistent databases

The problem of managing and querying inconsistent databases has been deeply investigated in the last few years. As the problem of consistent query answering is hard in the general case, most of the techniques proposed so far have an exponential complexity. Polynomial techniques have been proposed only for restricted forms of constraints (such as functional dependencies) and queries. In this paper, a technique for computing “approximate” consistent answers in polynomial time is proposed, which works in the presence of a wide class of constraints (namely, full constraints) and Datalog queries. The proposed approach is based on a repairing strategy where update operations assigning an undefined truth value to the “reliability” of tuples are allowed, along with updates inserting or deleting tuples. The result of a repair can be viewed as a three-valued database which satisfies the specified constraints. In this regard, a new semantics (namely, partial semantics) is introduced for constraint satisfaction in the context of three-valued databases, which aims at capturing the intuitive meaning of constraints under three-valued logic. It is shown that, in order to compute “approximate” consistent query answers, it suffices to evaluate queries by taking into account a unique repair (called deterministic repair), which in some sense “summarizes” all the possible repairs. The so obtained answers are “approximate” in the sense that are safe (true and false atoms in the answers are, respectively, true and false under the classical two-valued semantics), but not complete.     

Coalgebraic semantics for timed processes

We give a coalgebraic formulation of timed processes and their operational semantics. We model time by a monoid called a “time domain”, and we model processes by “timed transition systems”, which amount to partial monoid actions of the time domain or, equivalently, coalgebras for an “evolution comonad” generated by the time domain. All our examples of time domains satisfy a partial closure property, yielding a distributive law of a monad for total monoid actions over the evolution comonad, and hence a distributive law of the evolution comonad over a dual comonad for total monoid actions. We show that the induced coalgebras are exactly timed transition systems with delay operators. We then integrate our coalgebraic formulation of time qua timed transition systems into Turi and Plotkin’s formulation of structural operational semantics in terms of distributive laws. We combine timing with action via the more general study of the combination of two arbitrary sorts of behaviour whose operational semantics may interact. We give a modular account of the operational semantics for a combination induced by that of each of its components. Our study necessitates the investigation of products of comonads. In particular, we characterise when a monad lifts to the category of coalgebras for a product comonad, providing constructions with which one can readily calculate.     

Substantial and formal deductions in logics with vector semantics

The problem of logic deduction for one class of logics with a vector semantics is discussed. In the given logics the trustiness is represented by a vector with components 〈Truth; Lie〉, which do not depend on each other. The problem of organization of “substantial” and “formal” deductions is considered. In the first case the meaning of truth (semantics) of judgements is taken into account, whereas in the second case only the structure of judgements (syntax) is considered.     

Cooperation in Games and Epistemic Readings of Independence-Friendly Sentences

In the literature on logics of imperfect information it is often stated, incorrectly, that the Game-Theoretical Semantics of Independence-Friendly (IF) quantifiers captures the idea that the players of semantical games are forced to make some moves without knowledge of the moves of other players. We survey here the alternative semantics for IF logic that have been suggested in order to enforce this “epistemic reading” of sentences. We introduce some new proposals, and a more general logical language which distinguishes between “independence from actions” and “independence from strategies”. New semantics for IF logic can be obtained by choosing embeddings of the set of IF sentences into this larger language. We compare all the semantics proposed and their purported game-theoretical justifications, and disprove a few claims that have been made in the literature.