FA State function

A DFA can be represented by a very sparse table. Though in practice, this is not a good way because we often want to define values in ranges and entering each value in the range is wasteful

Safe Approach

A simple way that will work efficiently is to store the data in a sorted listed where the index is the state then the start of the range and the value is the end of the range and the output state.

Trees

For the most part, state IDs do not matter so long as they are consistent. We may also want all the output states to have some identifier like having the first bit set to one. It may be even better is we can get all the output states below a specific value and with some target density so that they can be efficiently mapped with an array.

We can form a tree where each branch node contains some low cost check and each leaf node contains a value.

Merging

The way to pick up efficiency is to merge transitions. For instance if state A in range a:b goes to state C and state B in range c:d also goes to C, if we can find a check that matches both those inputs and outputs C, that can be a single node. If that's not possible, it may be possible to find something that is true for all those values, plus some additional values that can be checked against another check.

A more complex merge would be one where A in range a:b goes to state X and state B in range c:d goes to Y, it may be possible to find an operation that produces the correct outputs.

To make this possible, we may also need to split ranges. Say the input is limited to a byte. Something in the range 100 to 150 (01100100 to 10010110), there are no constant leading bits. Defining two ranges as 100 to 127 (01100100 to 01111111) and 128 to 150 (10000000 to 10010110) gives three leading bits. This could be further broken down if necessary, for instance 100 to 111 (01100100 to 01101111) and 112 to 127 (01110000 to 01111111) which gets 4 leading bytes. This is valuable because it is easy to create binary operations that will work on those leading bits.

Rough Notes

I got tired of trying to work out all the details, so here's the rough sketch.

We're going to make a tree, like a KT tree, possibly where each node contains it's own check. We find a check that cleanly bifurcates the leaves and that's our first node. But, the less it bifurcates with in a state, the better. So the ideal function would bifurcate the leaves, but each output state is present in only one subtree. This is because if we get to a node where all the output states are the same, we're done.

The original line of thinking that lead here is still useful. I can't remember the name, but it's from the logic map reduction. Imagine the enormous table of all values, including all the error states. Not find the largest rectangle that contains only one value. Checking if we're in this rectangle is cheap. Now we can extend the remaining rectangles to contain either a constant value, or cells already returned. But the selector doesn't need to be a rectangle. Any function that returns a boolean can work.

And the values of the state can change. For instance, if we're just selecting rectangles, it's easy to see how changing the states numbers could lead to larger rectangles.