Date: 01/20/08 (Algorithms)    Keywords: google

What work does there exist on the topic of minimizing non-'conventional' finite state automata? I mean everything but the commonest FSM's usually used for simple regular languages:
- 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?

Source: http://community.livejournal.com/algorithms/96934.html