M.M. Bonsangue, H.H. Hansen, A. Kurz, and J. Rot. Presenting Distributive Laws. Technical report: ICIS-R13007, June, Radboud University Nijmegen, 2013.
Distributive laws of a monad T over a functor F are categorical tools for specifying algebra-coalgebra interaction. They proved to be important for solving systems of corecursive equations, for the specification of well-behaved structural operational semantics and, more recently, also for enhancements of the bisimulation proof method. If T is a free monad, then such distributive laws correspond to simple natural transformations. However, when T is not free it can be rather difficult to prove the defining axioms of a distributive law. In this paper we describe how to obtain a distributive law for a monad with an equational presentation from a distributive law for the underlying free monad. We apply this result to show the equivalence between two different representations of context-free languages.
Sebastiaan J.C. Joosten, and Hans Zantema. Relaxation of 3-partition instances. Technical report: ICIS-R13002, February, Radboud University Nijmegen, 2013.
The 3-partition problem admits a straightforward formulation as a 0-1 Integer Linear Program (ILP). We investigate problem instances for which the half-integer relaxation of the ILP is feasible, while the ILP is not. We prove that this only occurs on a set of at least 18 elements, and in case of 18 elements such an instance always contains an element of weight ‚?• 10. These bounds are sharp: we give all 14 instances consisting of 18 elements all having weight ‚?§ 10. Our approach is based on analyzing an underlying graph structure.