Volume 12, Issue 2

2016


1. Generic algorithms for halting problem and optimal machines revisited

Bienvenu, Laurent ; Desfontaines, Damien ; Shen, Alexander.
The halting problem is undecidable --- but can it be solved for "most" inputs? This natural question was considered in a number of papers, in different settings. We revisit their results and show that most of them can be easily proven in a natural framework of optimal machines (considered […]

2. Non-Obfuscated Unprovable Programs & Many Resultant Subtleties

Case, John ; Ralston, Michael.
The \emph{International Obfuscated C Code Contest} was a programming contest for the most creatively obfuscated yet succinct C code. By \emph{contrast}, an interest herein is in programs which are, \emph{in a sense}, \emph{easily} seen to be correct, but which can\emph{not} be proved correct in […]

3. FO2(<,+1,~) on data trees, data tree automata and branching vector addition systems

Jacquemard, Florent ; Segoufin, Luc ; Dimino, Jerémie.
A data tree is an unranked ordered tree where each node carries a label from a finite alphabet and a datum from some infinite domain. We consider the two variable first order logic FO2(<,+1,~) over data trees. Here +1 refers to the child and the next sibling relations while < refers to the […]

4. On the characterization of models of H*: The semantical aspect

Breuvart, Flavien.
We give a characterization, with respect to a large class of models of untyped lambda-calculus, of those models that are fully abstract for head-normalization, i.e., whose equational theory is H* (observations for head normalization). An extensional K-model $D$ is fully abstract if and only if it is […]

5. Quasipolynomial Normalisation in Deep Inference via Atomic Flows and Threshold Formulae

Bruscoli, Paola ; Guglielmi, Alessio ; Gundersen, Tom ; Parigot, Michel.
Je\v{r}\'abek showed that cuts in classical propositional logic proofs in deep inference can be eliminated in quasipolynomial time. The proof is indirect and it relies on a result of Atserias, Galesi and Pudl\'ak about monotone sequent calculus and a correspondence between that system and […]

6. Certified Context-Free Parsing: A formalisation of Valiant's Algorithm in Agda

Bernardy, Jean-Philippe ; Jansson, Patrik.
Valiant (1975) has developed an algorithm for recognition of context free languages. As of today, it remains the algorithm with the best asymptotic complexity for this purpose. In this paper, we present an algebraic specification, implementation, and proof of correctness of a generalisation […]

7. Formalized linear algebra over Elementary Divisor Rings in Coq

Cano, Guillaume ; Cohen, Cyril ; Dénès, Maxime ; Mörtberg, Anders ; Siles, Vincent.
This paper presents a Coq formalization of linear algebra over elementary divisor rings, that is, rings where every matrix is equivalent to a matrix in Smith normal form. The main results are the formalization that these rings support essential operations of linear algebra, the classification […]

8. Two-variable Logic with Counting and a Linear Order

Charatonik, Witold ; Witkowski, Piotr.
We study the finite satisfiability problem for the two-variable fragment of first-order logic extended with counting quantifiers (C2) and interpreted over linearly ordered structures. We show that the problem is undecidable in the case of two linear orders (in the presence of two other binary […]

9. Weighted Pushdown Systems with Indexed Weight Domains

Minamide, Yasuhiko.
The reachability analysis of weighted pushdown systems is a very powerful technique in verification and analysis of recursive programs. Each transition rule of a weighted pushdown system is associated with an element of a bounded semiring representing the weight of the rule. However, we have […]

10. Using higher-order contracts to model session types

Bernardi, Giovanni ; Hennessy, Matthew.
Session types are used to describe and structure interactions between independent processes in distributed systems. Higher-order types are needed in order to properly structure delegation of responsibility between processes. In this paper we show that higher-order web-service contracts can be used […]

11. The Largest Respectful Function

Parrow, Joachim ; Weber, Tjark.
Respectful functions were introduced by Sangiorgi as a compositional tool to formulate short and clear bisimulation proofs. Usually, the larger the respectful function, the easier the bisimulation proof. In particular the largest respectful function, defined as the pointwise union of all […]

12. No solvable lambda-value term left behind

García-Pérez, Á. ; Nogueira, P..
In the lambda calculus a term is solvable iff it is operationally relevant. Solvable terms are a superset of the terms that convert to a final result called normal form. Unsolvable terms are operationally irrelevant and can be equated without loss of consistency. There is a definition of solvability […]