Freebandlib

This repository contains reference implementations of the algorithms described in the paper:

R. Cirpons and J. D. Mitchell
"Polynomial time multiplication and normal forms in free bands"

The following table gives the correspondence between the formal algorithm description in the paper and the implementation in freebandlib.

Algorithm in paper	Algorithm in `freebandlib`
`IntervalTranducer`	`interval_transducer`
`Minimize`	`transducer_minimize`
`TrimTransducerIsomorphism`	`transducer_isomorphism`
`EqualInFreeBand`	`equal_in_free_band`
`Multiply`	`multiply`
`MinWord`	`min_word`

To run the tests

Type:

python3 -m pip install -r tests/requirements.txt

Then inside the freebandlib top level directory type:

pytest

Download the benchmark sample data files (i.e. input data for the benchmarks). To do so type:

./get_benchmark_sample_data.sh

Then type:

python3 -m pip install -r benchmarks/requirements.txt
make benchmark-all

It is also possible to generate entirely new benchmark sample data by using the code in benchmarks/generate_sample_data.py.

The benchmarks can then be parsed by running python3 ./benchmarks/extract_data.py