- Pushdown automata
- Automata with actions on transitions
- Automata with extra internal state
So, which variants of FSM's can be minimized?
I googled for something like 'minimizing automata' and found work on minimizing fuzzy automata (not that interesting for me), pushdown (http://www.labri.fr/perso/igw/Papers/igw-min-vis.pdf) and automata over infinite inputs. Also something named 'history dependent automata' (http://cometa.dimi.uniud.it/meetings/gioconople/pistore.pdf)
What else does there exist?