Minimal Memory Automata
Michael Benedikt‚ Clemens Ley and Gabriele Puppis
Abstract
We provide a Myhill-Nerode-like theorem that characterizes the class of data languages recognized by deterministic finite-memory automata (DMA). As a byproduct of this characterization result, we obtain a canonical representation for any DMA-recognizable language. We then show that this canonical automaton is minimal in a strong sense: it has the minimal number of control states and also the minimal amount of internal storage. We finally show how this minimal automaton can be computed.
Details
| Journal |
Technical Report |
| Note |
Long version of ‘What You Must Remember When Processing Data Words'. |
| Year |
2010 |
Links
Related pages
|
People |