Fast Practical Compression of Deterministic Finite Automata

Autor: Bille, Philip, Gørtz, Inge Li, Pedersen, Max Rishøj

We revisit the popular \emph{delayed deterministic finite automaton} (\ddfa{}) compression algorithm introduced by Kumar~et~al.~[SIGCOMM 2006] for compressing deterministic finite automata (DFAs) used in intrusion detection systems. This compression

Externí odkaz: http://arxiv.org/abs/2306.12771

Gapped Indexing for Consecutive Occurrences

Autor: Bille, Philip, Gørtz, Inge Li, Pedersen, Max Rishøj, Steiner, Teresa Anna

The classic string indexing problem is to preprocess a string S into a compact data structure that supports efficient pattern matching queries. Typical queries include existential queries (decide if the pattern occurs in S), reporting queries (return

Externí odkaz: http://arxiv.org/abs/2102.02505

String indexing for top-k close consecutive occurrences

Autor: Bille, Philip, Gørtz, Inge Li, Pedersen, Max Rishøj, Rotenberg, Eva, Steiner, Teresa Anna

Publikováno v: In Theoretical Computer Science 26 August 2022 927:133-147

Faster Compression of Deterministic Finite Automata

Autor: Bille, Philip, Gørtz, Inge Li, Pedersen, Max Rishøj

Deterministic finite automata (DFA) are a classic tool for high throughput matching of regular expressions, both in theory and practice. Due to their high space consumption, extensive research has been devoted to compressed representations of DFAs th

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::cbcb759bee05f9446b6ce4ed1542a703
http://arxiv.org/abs/2306.12771

String Indexing for Top-k Close Consecutive Occurrences

Autor: Bille, Philip, Gørtz, Inge Li, Pedersen, Max Rishøj, Rotenberg, Eva, Steiner, Teresa Anna

Publikováno v: Bille, P, Gørtz, I L, Pedersen, M R, Rotenberg, E & Steiner, T A 2020, String indexing for top-k close consecutive occurrences . in N Saxena & S Simon (eds), Proceedings of 40 th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science ., 14, Schloss Dagstuhl-Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, Leibniz International Proceedings in Informatics, LIPIcs, vol. 182, 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, Virtual, Goa, India, 14/12/2020 . https://doi.org/10.4230/LIPIcs.FSTTCS.2020.14
Bille, P, Gørtz, I L, Pedersen, M R, Rotenberg, E & Steiner, T A 2022, ' String indexing for top-k close consecutive occurrences ', Theoretical Computer Science, vol. 927, pp. 133-147 . https://doi.org/10.1016/j.tcs.2022.06.004

The classic string indexing problem is to preprocess a string $S$ into a compact data structure that supports efficient subsequent pattern matching queries, that is, given a pattern string $P$, report all occurrences of $P$ within $S$. In this paper,

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::0d6329a62f5a6c93b99c397d0d3f6bfc