4 papers
Near-Optimal and Efficient Encoding for Two-Dimensional Range Minimum Queries
Paweł Gawrychowski, Adam Górkiewicz, Srinivasa Rao Satti
We consider the 2D RMQ encoding problem: given an array of elements over a total order, encode it such that, for any query rectangle, the position of its maximum e…
Succinct Representation for (Non)Deterministic Finite Automata
Sankardeep Chakraborty, Roberto Grossi, Kunihiko Sadakane +1
Deterministic finite automata are one of the simplest and most practical models of computation studied in automata theory. Their conceptual extension is the non-deterministic finit…
On Succinct Representations of Binary Trees
Pooya Davoodi, Rajeev Raman, Srinivasa Rao Satti
We observe that a standard transformation between \emph{ordinal} trees (arbitrary rooted trees with ordered children) and binary trees leads to interesting succinct binary tree rep…
Selection from read-only memory with limited workspace
Amr Elmasry, Daniel Dahl Juhl, Jyrki Katajainen +1
Given an unordered array of elements drawn from a totally ordered set and an integer in the range from to , in the classic selection problem the task is to find the…