Report icon

Report

Minimal Memory Automata

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.

Actions


Authors


Michael Benedikt More by this author
Clemens Ley More by this author
Gabriele Puppis More by this author
Publication date:
2010
URN:
uuid:dea102b6-b201-41a2-8e73-388f73c40694
Local pid:
cs:4870

Terms of use


Metrics



If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP