Eugene Kirpichov (antilamer) wrote in algorithms,
Eugene Kirpichov

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 ( and automata over infinite inputs. Also something named 'history dependent automata' (

What else does there exist?
  • Post a new comment


    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded