Conference item icon

Conference item

What You Must Remember When Processing Data Words

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


Host title:
Alberto Mendelzon Workshop on Foundations of Databases
Publication date:
2010-01-01
UUID:
uuid:8d16f636-a4c3-4e3f-81ba-034bfc197159
Local pid:
cs:3617
Deposit date:
2015-03-31

Terms of use


Views and Downloads






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

TO TOP