Recently published

Complexity of Conditional Term Rewriting


We propose a notion of complexity for oriented conditional term rewrite systems satisfying certain restrictions. This notion is realistic in the sense that it measures not only successful computations, but also partial computations that result in a failed rule application. A transformation […]


Volume: Volume 13, Issue 1
Published on: February 6, 2017
A feasible interpolation for random resolution
Authors: Krajicek, Jan.


Random resolution, defined by Buss, Kolodziejczyk and Thapen (JSL, 2014), is a sound propositional proof system that extends the resolution proof system by the possibility to augment any set of initial clauses by a set of randomly chosen clauses (modulo a technical condition). We show how to apply […]


Volume: Volume 13, Issue 1
Published on: February 3, 2017
Unprovability of circuit upper bounds in Cook's theory PV


We establish unconditionally that for every integer $k \geq 1$ there is a language $L \in \mbox{P}$ such that it is consistent with Cook's theory PV that $L \notin Size(n^k)$. Our argument is non-constructive and does not provide an explicit description of this language.


Volume: Volume 13, Issue 1
Published on: February 3, 2017
Stream Differential Equations: Specification Formats and Solution Methods


Streams, or infinite sequences, are infinite objects of a very simple type, yet they have a rich theory partly due to their ubiquity in mathematics and computer science. Stream differential equations are a coinductive method for specifying streams and stream operations, and their theory has been […]


Volume: Volume 13, Issue 1
Published on: February 3, 2017
Mixed powerdomains for probability and nondeterminism


We consider mixed powerdomains combining ordinary nondeterminism and probabilistic nondeterminism. We characterise them as free algebras for suitable (in)equation-al theories; we establish functional representation theorems; and we show equivalencies between state transformers and appropriately […]


Volume: Volume 13, Issue 1
Published on: January 24, 2017