Simon Rumle Tarnow
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Simon Rumle Tarnow has a total of 4 co-authors. Here are the top co-authors by number of shared publications:
- Inge Li Gørtz
Technical University of Denmark
4 shared publications - Philip Bille
Technical University of Denmark
4 shared publications - Simon J. Puglisi
Department of Computer Science, University of Helsinki, Finland
3 shared publications - Máximo Pérez López
Technical University of Denmark
1 shared publication
Latest Publications
- 5 November 2026
- Published by Springer Nature
- p. 204-212
Tighter Bounds for Wheeler Determinization
- Open Access
- 28 May 2026
- Published by Springer Nature in Algorithmica
- Vol. 88 (3) , 50
Compressed Dictionary Matching on Run-Length Encoded Strings
Given a set of pattern strings $$\mathcal {P}=\{P_1, P_2,\ldots P_k\}$$ and a text string S , the classic dictionary matching problem is to report all occurrences of each pattern in S . We study the dictionary problem in the compressed setting, where the pattern strings and the text string are compressed using run-length encoding, and the goal is to solve the problem without decompression and achieve efficient time and space in the size of the compressed strings. Let m and n be the total length of the patterns $$\mathcal {P}$$ and the length of the text string S , respectively, and let $$\overline{m}$$ and $$\overline{n}$$ be the total number of runs in the run-length encoding of the patterns in $$\mathcal {P}$$ and S , respectively. Our main result is an algorithm that achieves $$O( (\overline{m} + \overline{n})\log \log m + \textrm{occ})$$ expected time, and $$O(\overline{m})$$ space, where $$\textrm{occ}$$ is the total number of occurrences of patterns in S . This is the first non-trivial solution to the problem. Since any solution must read the input, our time bound is optimal within a $$\log \log m$$ factor. We introduce several new techniques to achieve our bounds, including a new compressed representation of the classic Aho-Corasick automaton and a new efficient string index that supports fast queries in run-length encoded strings.- 28 May 2026
- Published by Springer Nature in Algorithmica
- Vol. 88 (3) , 50
Open AccessCompressed Dictionary Matching on Run-Length Encoded Strings
Given a set of pattern strings $$\mathcal {P}=\{P_1, P_2,\ldots P_k\}$$ and a text string S , the classic dictionary matching problem is to report all occurrences of each pattern in S . We study the dictionary problem in the compressed setting, where the pattern strings and the text string are compressed using run-length encoding, and the goal is to solve the problem without decompression and achieve efficient time and space in the size of the compressed strings. Let m and n be the total length of the patterns $$\mathcal {P}$$ and the length of the text string S , respectively, and let $$\overline{m}$$ and $$\overline{n}$$ be the total number of runs in the run-length encoding of the patterns in $$\mathcal {P}$$ and S , respectively. Our main result is an algorithm that achieves $$O( (\overline{m} + \overline{n})\log \log m + \textrm{occ})$$ expected time, and $$O(\overline{m})$$ space, where $$\textrm{occ}$$ is the total number of occurrences of patterns in S . This is the first non-trivial solution to the problem. Since any solution must read the input, our time bound is optimal within a $$\log \log m$$ factor. We introduce several new techniques to achieve our bounds, including a new compressed representation of the classic Aho-Corasick automaton and a new efficient string index that supports fast queries in run-length encoded strings. - Open Access
- 4 December 2025
- Published by Springer Nature in Research Square
Compressed Dictionary Matching on Run-Length Encoded Strings
Given a set of pattern strings P = {P1, P2, . . . Pk} and a text string S, the classic dictionary matching problem is to report all occurrences of each pattern in S. We study the dictionary problem in the compressed setting, where the pattern strings and the text string are compressed using run-length encoding, and the goal is to solve the problem without decompression and achieve efficient time and space in the size of the compressed strings. Let m and n be the total length of the patterns P and the length of the text string S, respectively, and let m and n be the total number of runs in the run-length encoding of the patterns in P and S, respectively. Our main result is an algorithm that achieves O((m+n) log logm+occ) expected time, and O(m) space, where occ is the total number of occurrences of patterns in S. This is the first non-trivial solution to the problem. Since any solution must read the input, our time bound is optimal within an log logm factor. We introduce several new techniques to achieve our bounds, including a new compressed representation of the classic Aho-Corasick automaton and a new efficient string index that supports fast queries in runlength encoded strings.
- 4 December 2025
- Published by Springer Nature in Research Square
Open AccessCompressed Dictionary Matching on Run-Length Encoded Strings
Given a set of pattern strings P = {P1, P2, . . . Pk} and a text string S, the classic dictionary matching problem is to report all occurrences of each pattern in S. We study the dictionary problem in the compressed setting, where the pattern strings and the text string are compressed using run-length encoding, and the goal is to solve the problem without decompression and achieve efficient time and space in the size of the compressed strings. Let m and n be the total length of the patterns P and the length of the text string S, respectively, and let m and n be the total number of runs in the run-length encoding of the patterns in P and S, respectively. Our main result is an algorithm that achieves O((m+n) log logm+occ) expected time, and O(m) space, where occ is the total number of occurrences of patterns in S. This is the first non-trivial solution to the problem. Since any solution must read the input, our time bound is optimal within an log logm factor. We introduce several new techniques to achieve our bounds, including a new compressed representation of the classic Aho-Corasick automaton and a new efficient string index that supports fast queries in runlength encoded strings.
- Open Access
Compressed Dictionary Matching on Run-Length Encoded Strings
Given a set of pattern strings $\mathcal{P}=\{P_1, P_2,\ldots P_k\}$ and a text string $S$, the classic dictionary matching problem is to report all occurrences of each pattern in $S$. We study the dictionary problem in the compressed setting, where the pattern strings and the text string are compressed using run-length encoding, and the goal is to solve the problem without decompression and achieve efficient time and space in the size of the compressed strings. Let $m$ and $n$ be the total length of the patterns $\mathcal{P}$ and the length of the text string $S$, respectively, and let $\overline{m}$ and $\overline{n}$ be the total number of runs in the run-length encoding of the patterns in $\mathcal{P}$ and $S$, respectively. Our main result is an algorithm that achieves $O( (\overline{m} + \overline{n})\log \log m + \mathrm{occ})$ expected time, and $O(\overline{m})$ space, where $\mathrm{occ}$ is the total number of occurrences of patterns in $S$. This is the first non-trivial solution to the problem. Since any solution must read the input, our time bound is optimal within an $\log \log m$ factor. We introduce several new techniques to achieve our bounds, including a new compressed representation of the classic Aho-Corasick automaton and a new efficient string index that supports fast queries in run-length encoded strings.Open AccessCompressed Dictionary Matching on Run-Length Encoded Strings
Given a set of pattern strings $\mathcal{P}=\{P_1, P_2,\ldots P_k\}$ and a text string $S$, the classic dictionary matching problem is to report all occurrences of each pattern in $S$. We study the dictionary problem in the compressed setting, where the pattern strings and the text string are compressed using run-length encoding, and the goal is to solve the problem without decompression and achieve efficient time and space in the size of the compressed strings. Let $m$ and $n$ be the total length of the patterns $\mathcal{P}$ and the length of the text string $S$, respectively, and let $\overline{m}$ and $\overline{n}$ be the total number of runs in the run-length encoding of the patterns in $\mathcal{P}$ and $S$, respectively. Our main result is an algorithm that achieves $O( (\overline{m} + \overline{n})\log \log m + \mathrm{occ})$ expected time, and $O(\overline{m})$ space, where $\mathrm{occ}$ is the total number of occurrences of patterns in $S$. This is the first non-trivial solution to the problem. Since any solution must read the input, our time bound is optimal within an $\log \log m$ factor. We introduce several new techniques to achieve our bounds, including a new compressed representation of the classic Aho-Corasick automaton and a new efficient string index that supports fast queries in run-length encoded strings.