I have a deterministic finite automaton which behaves mostly like a Turing machine, with following difference (relevant to this question):
- The tape is initially finite.
- The automaton can insert and delete cells from the tape.
- Actions are associated with states rather than with transitions (this includes head shift and tape manipulation).
- The automaton has no accepting/final state. The computation is only terminated when the machine exits the tape. The final state of the tape is the machine's output.
I know most of the states in the machine are redudant (equivalent to other states). However the good old DFA minimization algorithm won't work here, because it starts its work on the final states (which I don't have).
The algorithm should be efficiently computable (the machines in question have hundreds of thousands to millions of states).
Is this possible in the general case? Every algorithm I make up fails in some cases.