Uncertain parameters

Initial value problems (IVPs) are usually given in terms of a differential equation, which yields a family of solutions, and initial conditions that pick a particular solution. In the case of uncertain initial value problems (UIVPs), i.e. IVPs with uncertain initial conditions, the problem statement does not specify a single solution, but rather a family of solutions. The family consists of all solutions obtained from IVPs with initial conditions obtained from the UIVP. Jan has implemented two Picard-based solvers handing UIVPs that use BigDecimal-bounded intervals to represent the computed solutions. Future work will build on these solvers to implement event detection, aiming for an algorithm that computes interval approximations of hybrid systems. 

Types, Lambdas and Categories

This week Adam is attending the 2012 Midlands Graduate School on the foundations of computing science. In particular, he is attending courses on typed labmda calculus, advanced functional programming and category theory. The category theory course, given by Graham Hutton, is based on an unusually student-friendly set of course notes (available online) which introduces categories as a special case of graphs, with some additional structure.

Interval Picard continues

Last week Jan continued the implementation of an interval Picard-based ODE IVP solver using the framework for safe numerics developed with Veronica. The design follows the program (described in previous posts) of keeping things generic in the numeric base type and function representation to facilitate the comparison and evaluation of various alternatives. He will continue this work over the next weeks.

Floating sequences

Continuing their work on generic differential equation solving in Scala Veronica and Jan have made sequences of Floating values an instance of Floating. This makes it possible to use algorithms for solving linear ODEs to be applied to higher order ODEs by translating them to systems of linear ODEs. When the original solver algorithm is written polymorphically over the real number type the extension comes at no extra cost as the Floating instance to be used is obtained from the code for the field and initial condition of the system of ODEs. Coming work aims at completing the supported set of Interval Floating methods and adding Floating instances for Floating-valued functions to the framework.

Reducing noise in failing test cases

During the past week Adam has looked at test case minimization, also known as shrinking, and how to apply it to test cases generated from external specifications. Shrinking aims to make debugging easier by removing noise, that is information which is not relevant to the error which the a failing test case provokes. Given a failing test case and the specification that was used to generate it, Adam investigated ways to obtain shrunk testcases which are still valid with respect to the specification. This included a simple approach, where the specification was only used to validate shrunk test case variants, and a more sophisticated method where the specification was used to guide the shrinking. In both cases the number of cases to consider is very large, as an optimal solution really requires that all possible shrunk variants are enumerated. In the latter case, however, the task is reduced since variants which are invalid with repsect to the specification can be omitted. 

Sampling the strings of a regular language

This week Adam focused on the generation of strings which match a specific regular expression. Several ways of approaching this has problem have been described in the literature. For example, two methods are given in the functional pearl Enumerating the strings of regular languages by M. Douglas McIlroy, but focus has been on the enumeration of all such strings, an approach that does not scale well. A practical alternative is to give up on the constraint that each string should be generated with equal probability. An approach taken by the tool Xeger is to generate the strings by transforming the regular expression into a non-deterministic finite automaton, and then to generate the string simulating the automaton by giving each option in a non-deterministic choice equal probability. This corresponds to a probabilistic automaton whose stochastic matrix consists of uniform distributions.