Constraints Research Group - Software

This page contains links to software packages written by members of the Constraints group.

Contents

• Polyanna - Analysis of relations to find polymorphisms
• Bioinformatics tools

Polyanna

Polyanna is a program for finding the polymorphisms of a given set of relations over a finite domain. Many other attempts have been made in the past to solve this problem, but all have run prohibitively slowly. Polyanna is the first program to fully exploit the symmetry inherent in this problem, and as a result it can run exponentially faster than its rivals.

Polyanna has many features. Most notable among them are:

• Speed. Polyanna can often solve in seconds, problems which previous implementations would take many months to analyse.
• Economy of output. By representing solution sets as function specifications, Polyanna can often exponentially reduce the size of the output. This is especially useful if a human has to read through it.
• Symmetry removal. Polyanna contains sophisticated algorithms for removing symmetries from the output. Yet it is intelligent enough to only apply these algorithms when they would genuinely speed up the calculation (and/or reduce the size of the output).
• Tractability testing. Polyanna is able to search for numerous specific types of functions (majority functions, for example, or associative functions) very quickly. In addition, it has a built-in tractability tester which can analyse input relations and determine whether they give rise to a constraint problem which is tractable, NP-complete, or of unknown complexity.
• State-of-the-art. Polyanna makes use of the latest results from the theory of constraint tractability. For example, it can recognise and detect relations which can be decomposed into disjoint domains. This can often enable it to analyse the complexity of very large relations. It can search for Mal'tsev polymorphisms. Partial support is supplied for recognising conjunctive products, and this will be extended in the near future.
• Free. The source code to Polyanna may be freely downloaded and compiled. It is written in C++, and makes heavy use of the STL. Extensive documentation is supplied.

You may download Polyanna version 1.01 from here. Detailed documentation, including a full user manual, is also available.

To help us keep track of how many people use Polyanna, we would greatly appreciate hearing from you if you make any use of the program. Any comments, suggestions, or bug reports may also be mailed to the author.