Source code and benchmark data accompanying the Lancaster University year 3 dissertation project on computing Unique Input/Output (UIO) sequences for deterministic finite state machines. Two algorithms are implemented and compared: a Brute-Force breadth-first search (bruteForce.cpp) and a Successor Tree search with incremental rival tracking and convergence pruning (successorTree.cpp).
On the convergent (worst-case) dataset, the successor tree achieved roughly a 6,000x wall-clock speedup over brute force (around 81,000x mean per-state), and solved 752 cases that exhausted brute force's memory pool entirely, finishing each in a single search node. On the low-diversity dataset it performed about 94% fewer rival comparisons. Brute force grows combinatorially with sequence length; the successor tree grows polynomially on random machines and stays near-constant on convergent ones.
.
├── README.md
├── Project Proposal.pdf initial project proposal
├── UIO Generation for FSMs Project Report.pdf full dissertation report
├── FSM Comparison Datasheet.xlsx aggregated results and charts
├── source/
│ ├── bruteForce.cpp brute-force BFS
│ ├── successorTree.cpp successor tree search
│ └── helper_algorithms/
│ ├── fsm_generator.py regenerates the two supplementary datasets
│ └── data_summary_generator.py aggregates per-state CSVs by (size, seq length)
├── data/ FSM input datasets
│ ├── high_diversity_fsms.txt supervisor's dataset, 6 outputs, sizes 10..200 (step 5)
│ ├── low_diversity_fsms.txt 2 outputs, sizes 10..200 (step 5)
│ └── convergent_fsms.txt equivalent-pair FSMs, sizes 4..30 (step 2)
└── results/ per-run CSVs are written here
└── csv_files/ aggregated summaries go here
All file paths used in the code are relative to the project root, so every command below is meant to be run from this directory.
- A C++17 compiler (tested with
g++11+ on both Linux and MinGW on Windows). - Python 3.8+ (standard library only, no third-party packages).
g++ -O3 -DNDEBUG -march=native -std=c++17 source/bruteForce.cpp -o bruteForce
g++ -O3 -DNDEBUG -march=native -std=c++17 source/successorTree.cpp -o successorTree
The three flags used for benchmarking are -O3 (full optimisation), -DNDEBUG (disables assertions), and -march=native (enables all instruction-set extensions supported by the host CPU). All measurements reported in the dissertation were taken from binaries built with these exact flags.
There are three datasets. The supervisor's high_diversity_fsms.txt is shipped as-is; the other two are regenerated from a fixed seed.
cd source/helper_algorithms
python fsm_generator.py
cd ../..
fsm_generator.py uses two deterministic seeds:
- SEED = 42 for
low_diversity_fsms.txt(1,950 FSMs, 50 per size, 2 outputs). - SEED + 1 = 43 for
convergent_fsms.txt(700 FSMs, 50 per size, 3 inputs, 4 outputs, 50% equivalent pairs).
Running the script on any platform with Python 3 will produce byte-identical files to the ones shipped in data/.
mkdir -p results/csv_files
./bruteForce data/high_diversity_fsms.txt results/bruteforce_analytics.csv
./successorTree data/high_diversity_fsms.txt results/successorTree_analytics.csv
./bruteForce data/low_diversity_fsms.txt results/low_diversity_bf_analytics.csv
./successorTree data/low_diversity_fsms.txt results/low_diversity_st_analytics.csv
./bruteForce data/convergent_fsms.txt results/convergent_bf_analytics.csv
./successorTree data/convergent_fsms.txt results/convergent_st_analytics.csv
If the two CLI arguments are omitted the algorithms default to data/high_diversity_fsms.txt and write to results/bruteforce_analytics.csv or results/successorTree_analytics.csv respectively.
Run order does not matter. The six runs are independent.
cd source/helper_algorithms
python data_summary_generator.py
cd ../..
This parses every CSV in results/ and writes the aggregated summaries into results/csv_files/.
After step 2, results/ should contain six CSVs, one per (algorithm, dataset) pair:
results/
├── bruteforce_analytics.csv supervisor's dataset, BF
├── successorTree_analytics.csv supervisor's dataset, ST
├── low_diversity_bf_analytics.csv
├── low_diversity_st_analytics.csv
├── convergent_bf_analytics.csv
└── convergent_st_analytics.csv
Each row corresponds to one (FSM, state) pair with the columns:
FSM_ID, State, Outcome, SeqLength, NodesExpanded, SequencesTested,
RivalComparisons, PrunedBranches, TimeMs, UIO_Sequence
Outcome is one of Found, NotFound, or MemLimit. PrunedBranches is only populated by the Successor Tree; it appears as - in Brute-Force rows.
After step 3, results/csv_files/ should contain four aggregated summary CSVs:
results/csv_files/
├── summary.csv supervisor's dataset
├── low_diversity_summary.csv
├── convergent_summary.csv
└── all_summaries.csv all three datasets concatenated with a Dataset column
Each summary row is keyed by (FSM_Size_States, Sequence_Length) and reports mean nodes, sequences, rival comparisons, pruned branches, and wall-clock time for both algorithms, along with the BF/ST efficiency ratios.
Two tunable constants live at the top of both C++ files:
MAX_DEPTH(default 10): maximum input-sequence length the search will consider before giving up.POOL_SIZE(default 500,000): upper bound on the BFS node pool; when reached, the search exits with an outcome ofMemLimit.
Both values were chosen to keep runs tractable on commodity hardware while still producing enough NotFound cases on the convergent dataset to exercise worst-case search behaviour. Changing either constant requires rebuilding.
- Exact timings vary between machines and runs. The relative trends reported in the dissertation (Brute-Force grows combinatorially, Successor Tree grows polynomially on the random set and stays near-constant on the convergent set) are stable across reasonable hardware.
- The FSM generator is fully deterministic for a given seed. Re-running
fsm_generator.pyalways produces the same datasets. - The C++ code is single-threaded and has no dependence on wall-clock time, OS scheduling, or RNG, so the per-run CSVs are bitwise identical across machines.
Released under the MIT License. See LICENSE.