Deterministic finite automata are one of the simplest and most practical models of computation studied in automata theory. Their extension is the non-deterministic finite automata which also have plenty of applications. In this article, we study these models through the lens of succinct data structures where our ultimate goal is to encode these mathematical objects using information theoretically optimal number of bits along with supporting queries on them efficiently.
Succinct Representations for (Non)Deterministic Finite Automata
Roberto Grossi;
2021-01-01
Abstract
Deterministic finite automata are one of the simplest and most practical models of computation studied in automata theory. Their extension is the non-deterministic finite automata which also have plenty of applications. In this article, we study these models through the lens of succinct data structures where our ultimate goal is to encode these mathematical objects using information theoretically optimal number of bits along with supporting queries on them efficiently.File in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
Succinct_Representation_for__Non_Deterministic_Finite_Automata__LATA_.pdf
accesso aperto
Tipologia:
Documento in Post-print
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
397.75 kB
Formato
Adobe PDF
|
397.75 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
