Skip to main content

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.

Journal
Technical Report
Note
Long version of ‘What You Must Remember When Processing Data Words'.
Year
2010