Succinct representation for (non)deterministic finite automata.
Peer reviewed, Journal article
Published version
Permanent lenke
https://hdl.handle.net/11250/3042202Utgivelsesdato
2023Metadata
Vis full innførselSamlinger
Originalversjon
Journal of computer & systems sciences international. 2023, 131, 1-12. 10.1016/j.jcss.2022.07.002Sammendrag
(Non)-Deterministic finite automata are one of the simplest models of computation studied in automata theory. Here we study them through the lens of succinct data structures. Towards this goal, we design a data structure for any deterministic automaton having n states over a σ-letter alphabet Σ using bits, that determines, given a string x, whether accepts x in optimal time. We also consider the case when there are non-failure transitions, and obtain various time-space trade-offs. Here some of our results are better than the recent work of Cotumaccio and Prezza (SODA 2021). We also exhibit a data structure for non-deterministic automaton using bits that takes time for string membership checking. Finally, we also provide time and space efficient algorithms for performing several standard operations on the languages accepted by finite automata.