Eugene Kirpichov (antilamer) wrote in algorithms,
Eugene Kirpichov
antilamer
algorithms

Minimizing various automata

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?
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 0 comments