Difunctorial Semantics of Object Calculus

In this paper we give a denotational model for Abadi and Cardelli's first order object calculus FOb_1+×μ (without subtyping) in the category pCpo. The key novelty of our model is its extensive use of recursively defined types, supporting self-application, to model objects. At a technical level, this entails using some sophisticated techniques such as Freyd's algebraic compactness to guarantee the existence of the denotations of the object types. The last sections of the paper demonstrates that the canonical recursion operator inherent in our semantics is potentially useful in object-oriented programming. This is witnessed by giving a straightforward translation of algebraic datatypes into so called wrapper classes.     

Deforestation, program transformation, and cut-elimination

The problem of proving that two programs, in any reasonable programming language, are equivalent is well-known to be undecidable. In a formal programming system, in which the rules for equivalence are finitely presented, the problem of provable equivalence is semi-decidable. Despite this improved situation there is a significant lack of generally accepted automated techniques for systematically searching for a proof (or disproof) of program equivalence. Techniques for searching for proofs of equivalence often stumble on the formulation of induction and, of course, coinduction (when it is present) which are often formulated in such a manner as to require inspired guesses.There are, however, well-known program transformation techniques which do address these issues. Of particular interest to this paper are the deforestation techniques introduced by Phil Wadler and the fold/unfold program transformation techniques introduced by Burstall and Darlington. These techniques are shadows of an underlying cut-elimination procedure and, as such, should be more generally recognized as proof techniques.In this paper we show that these techniques apply to languages which have both inductive and coinductive datatypes. The relationship between these program transformation techniques and cut-elimination requires a transformation from initial and final “algebra” proof rules into “circular” proof rules as introduced by Santocanale (and used implicitly in the model checking community). This transformation is only possible in certain proof systems. Here we show that it can be applied to cartesian closed categories with datatypes: closedness is an essential requirement. The cut-elimination theorems and attendant program transformation techniques presented here rely heavily on this alternate presentation of induction and coinduction.     

Bounded Model Checking with Parametric Data Structures

Bounded Model Checking (BMC) is a successful refutation method to detect errors in not only circuits and other binary systems but also in systems with more complex domains like timed automata or linear hybrid automata. Counterexamples of a fixed length are described by formulas in a decidable logic, and checked for satisfiability by a suitable solver.In an earlier paper we analyzed how BMC of linear hybrid automata can be accelerated already by appropriate encoding of counterexamples as formulas and by selective conflict learning. In this paper we introduce parametric datatypes for the internal solver structure that, taking advantage of the symmetry of BMC problems, remarkably reduce the memory requirements of the solver.     

Transformation of structure-shy programs with application to XPath queries and strategic functions

Various programming languages allow the construction of structure-shy programs. Such programs are defined generically for many different datatypes and only specify specific behavior for a few relevant subtypes. Typical examples are XML query languages that allow selection of subdocuments without exhaustively specifying intermediate element tags. Other examples are languages and libraries for polytypic or strategic functional programming and for adaptive object-oriented programming.In this paper, we present an algebraic approach to transformation of declarative structure-shy programs, in particular for strategic functions and XML queries. We formulate a rich set of algebraic laws, not just for transformation of structure-shy programs, but also for their conversion into structure-sensitive programs and vice versa. We show how subsets of these laws can be used to construct effective rewrite systems for specialization, generalization, and optimization of structure-shy programs. We present a type-safe encoding of these rewrite systems in Haskell which itself uses strategic functional programming techniques. We discuss the application of these rewrite systems for XPath query optimization and for query migration in the context of schema evolution.     

CoCasl at Work — Modelling Process Algebra

CoCasl[11], a recently developed coalgebraic extension of the algebraic specification language Casl[2], allows for modelling systems in terms of inductive datatypes as well as of co-inductive process types. Here, we demonstrate how to specify process algebras, namely CCS[10] and CSP[8,17], within such an algebraic-coalgebraic framework. It turns out that CoCasl can deal with the fundamental concepts of process algebra in a natural way: The type system of communications, the syntax of processes and their structural operational semantics fit well in the algebraic world of Casl, while the additional coalgebraic constructs of CoCasl cover the various process equivalences (bisimulation, weak bisimulation, observational congruence, and trace equivalence) and provide fully abstract semantic domains. CoCasl hence becomes a meta-framework for studying the semantics and proof theory of reactive systems.     

A Decision Procedure for (Co)datatypes in SMT Solvers

We present a decision procedure that combines reasoning about datatypes and codatatypes. The dual of the acyclicity rule for datatypes is a uniqueness rule that identifies observationally equal codatatype values, including cyclic values. The procedure decides universal problems and is composable via the Nelson–Oppen method. It has been implemented in CVC4, a state-of-the-art SMT solver. An evaluation based on problems generated from formalizations developed with Isabelle demonstrates the potential of the procedure.     

Algebraic–coalgebraic specification in CoCasl

We introduce CoCasl as a light-weight but expressive coalgebraic extension of the algebraic specification language Casl. CoCasl allows the nested combination of algebraic datatypes and coalgebraic process types. Moreover, it provides syntactic sugar for an observer-indexed modal logic that allows e.g. expressing fairness properties. This logic includes a generic definition of modal operators for observers with structured equational result types. We prove existence of final models for specifications in a format that allows the use of equationally specified initial datatypes as observations, as well as modal axioms. The use of CoCasl is illustrated by specifications of the process algebras CSP and CCS.     

The parallel system for integrating impact models and sectors (pSIMS)

We present a framework for massively parallel climate impact simulations: the parallel System for Integrating Impact Models and Sectors (pSIMS). This framework comprises a) tools for ingesting and converting large amounts of data to a versatile datatype based on a common geospatial grid; b) tools for translating this datatype into custom formats for site-based models; c) a scalable parallel framework for performing large ensemble simulations, using any one of a number of different impacts models, on clusters, supercomputers, distributed grids, or clouds; d) tools and data standards for reformatting outputs to common datatypes for analysis and visualization; and e) methodologies for aggregating these datatypes to arbitrary spatial scales such as administrative and environmental demarcations. By automating many time-consuming and error-prone aspects of large-scale climate impacts studies, pSIMS accelerates computational research, encourages model intercomparison, and enhances reproducibility of simulation results. We present the pSIMS design and use example assessments to demonstrate its multi-model, multi-scale, and multi-sector versatility.     

Refactoring pattern matching

Defining functions by pattern matching over the arguments is advantageous for understanding and reasoning, but it tends to expose the implementation of a datatype. Significant effort has been invested in tackling this loss of modularity; however, decoupling patterns from concrete representations while maintaining soundness of reasoning has been a challenge. Inspired by the development of invertible programming, we propose an approach to program refactoring based on a right-invertible language rinv—every function has a right (or pre-) inverse. We show how this new design is able to permit a smooth incremental transition from programs with algebraic datatypes and pattern matching, to ones with proper encapsulation, while maintaining simple and sound reasoning.     

A study of substitution,using nominal techniques and Fraenkel–Mostowksi sets

Fraenkel–Mostowski (FM) set theory delivers a model of names and alpha-equivalence. This model, now generally called the ‘nominal’ model, delivers inductive datatypes of syntax with alpha-equivalence — rather than inductive datatypes of syntax, quotiented by alpha-equivalence.The treatment of names and alpha-equivalence extends to the entire sets universe. This has proven useful for developing ‘nominal’ theories of reasoning and programming on syntax with alpha-equivalence, because a sets universe includes elements representing functions, predicates, and behaviour.Often, we want names and alpha-equivalence to model capture-avoiding substitution. In this paper we show that FM set theory models capture-avoiding substitution for names in much the same way as it models alpha-equivalence; as an operation valid for the entire sets universe which coincides with the usual (inductively defined) operation on inductive datatypes.In fact, more than one substitution action is possible (they all agree on sets representing syntax). We present two distinct substitution actions, making no judgement as to which one is ‘right’ — we suspect this question has the same status as asking whether classical or intuitionistic logic is ‘right’. We describe the actions in detail, and describe the overall design issues involved in creating any substitution action on a sets universe.Along the way, we think in new ways about the structure of elements of FM set theory. This leads us to some interesting mathematical concepts, including the notions of planes and crucial elements, which we also describe in detail.     

A general inequality of Chebyshev type for semi(co)normed fuzzy integrals

Generalization of the Chebyshev inequality for semi(co)normed fuzzy integrals on an abstract fuzzy measure space based on a binary operation is given. Also, Minkowski’s and Hölder’s inequalities for semi(co)normed fuzzy integrals are studied in a rather general form. The main results of this paper generalize some previous results. Finally, a conclusion is drawn and an open problem for further investigations is given.     

A computational approach of A ∞-(co)algebras

We present a computer program to compute the explicit structural components of an A _∞-(co)algebra deduced from a contraction, which is a special type of homotopy equivalence. The input is a contraction from a dg-(co)algebra to a simple dg-module and the output is a functional object that defines the operations {μ _i } _i≥1 (resp. {Δ _i } _i≥1) in the deduced A _∞-structure on the simple dg-module. We conclude with some concrete applications.     

Tensors, !-graphs,and Non-commutative Quantum Structures

!-graphs provide a means of reasoning about infinite families of string diagrams and have proven useful in manipulation of (co)algebraic structures like Hopf algebras, Frobenius algebras, and compositions thereof. However, they have previously been limited by an inability to express families of diagrams involving non-commutative structures which play a central role in algebraic quantum information and the theory of quantum groups. In this paper, we fix this shortcoming by offering a new semantics for non-commutative !-graphs using an enriched version of Penrose’s abstract tensor notation.     

Algebraic proofs over noncommutative formulas

We study possible formulations of algebraic propositional proof systems operating with noncommutative formulas. We observe that a simple formulation gives rise to systems at least as strong as Frege, yielding a semantic way to define a Cook-Reckhow (i.e., polynomially verifiable) algebraic analog of Frege proofs, different from that given in Buss et al. (1997) and Grigoriev and Hirsch (2003). We then turn to an apparently weaker system, namely, polynomial calculus (PC) where polynomials are written as ordered formulas (PC over ordered formulas, for short). Given some fixed linear order on variables, an arithmetic formula is ordered if for each of its product gates the left subformula contains only variables that are less-than or equal, according to the linear order, than the variables in the right subformula of the gate. We show that PC over ordered formulas (when the base field is of zero characteristic) is strictly stronger than resolution, polynomial calculus and polynomial calculus with resolution (PCR), and admits polynomial-size refutations for the pigeonhole principle and Tseitin?s formulas. We conclude by proposing an approach for establishing lower bounds on PC over ordered formulas proofs, and related systems, based on properties of lower bounds on noncommutative formulas (Nisan, 1991).The motivation behind this work is developing techniques incorporating rank arguments (similar to those used in arithmetic circuit complexity) for establishing lower bounds on propositional proofs.     

Solving more general index-2 differential algebraic equations

The paper deals with a class of quasilinear index-2 differential algebraic equations, which covers both linear variable coefficient systems as well as Hessenberg form equations. Supposing low smoothness only, the solvability of initial value problems is stated via classical analytical techniques. For that class of differential algebraic equations, backward differentiation formulas and Runge-Kutta methods as well as projected versions are discussed with respect to feasibility, (in)stability, convergence, and asymptotical behaviour.     

A simple probabilistic explanation of term frequency-inverse document frequency (tf-idf) heuristic (and variations motivated by this explanation)

In document analysis, an important task is to automatically find keywords which best describe the subject of the document. One of the most widely used techniques for keyword detection is a technique based on the term frequency-inverse document frequency (tf-idf) heuristic. This techniques has some explanations, but these explanations are somewhat too complex to be fully convincing. In this paper, we provide a simple probabilistic explanation for the tf-idf heuristic. We also show that the ideas behind explanation can help us come up with more complex formulas which will hopefully lead to a more adequate detection of keywords.     

Generalised folds for nested datatypes

Nested datatypes generalise regular datatypes in much the same way that context-free languages generalise regular ones. Although the categorical semantics of nested types turns out to be similar to the regular case, the fold functions are more limited because they can only describe natural transformations. Practical considerations therefore dictate the introduction of a generalised fold function in which this limitation can be overcome. In the paper we show how to construct generalised folds systematically for each nested datatype, and show that they possess a uniqueness property analogous to that of ordinary folds. As a consequence, generalised folds satisfy fusion properties similar to those developed for regular datatypes. Such properties form the core of an effective calculational theory of inductive datatypes. Received September 1998 / Accepted in revised form July 1999     

Some algebraic laws for spans (and their connections with multirelations)

This paper investigates some key algebraic properties of the categories of spans and cospans (up to isomorphic supports) over the category Set of (small) sets and functions, analyzing the monoidal structures induced over both spans and cospans by cartesian product and disjoint union of sets. Our results find analogous counterparts in (and are partly inspired by) the theory of relational algebras, thus our paper also sheds some light on the relationship between (co)spans and the categories of (multi)relations and of equivalence relations. And, since (co)spans yield an intuitive presentation of dynamical systems with input and output interfaces, our results introduce an expressive, two-fold algebra that can serve as a specification formalism for rewriting systems and for composing software modules.     

OWL-Eu: Adding customised datatypes into OWL

Although OWL is rather expressive, it has a very serious limitation on datatypes; i.e., it does not support customised datatypes. It has been pointed out that many potential users will not adopt OWL unless this limitation is overcome, and the W3C Semantic Web Best Practices and Development Working Group has set up a task force to address this issue. This paper makes the following two contributions: (i) it provides a brief summary of OWL-related datatype formalisms, and (ii) it provides a decidable extension of OWL DL, called OWL-Eu, that supports customised datatypes. A detailed proof of the decidability of OWL-Eu is presented.