Source author record

Tooru Akagi

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Discrete Mathematics Formal Languages and Automata Theory math.CO

Catalog footprint

Research overview

2works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Combinatorics of minimal absent words for a sliding window

A string $w$ is called a minimal absent word (MAW) for another string $T$ if $w$ does not occur in $T$ but the proper substrings of $w$ occur in $T$ . For example, let $Σ= \{\mathtt{a, b, c}\}$ be the alphabet. Then, the set of MAWs for string $w = \mathtt{abaab}$ is $\{\mathtt{aaa, aaba, bab, bb, c}\}$ . In this paper, we study combinatorial properties of MAWs in the sliding window model, namely, how the set of MAWs changes when a sliding window of fixed length $d$ is shifted over the input string $T$ of length $n$ , where $1 \leq d < n$ . We present \emph{tight} upper and lower bounds on the maximum number of changes in the set of MAWs for a sliding window over $T$ , both in the cases of general alphabets and binary alphabets. Our bounds improve on the previously known best bounds [Crochemore et al., 2020].

preprint2022arXiv

Minimal Absent Words on Run-Length Encoded Strings

A string $w$ is called a minimal absent word (MAW) for another string $T$ if $w$ does not occur (as a substring) in $T$ and any proper substring of $w$ occurs in $T$ . State-of-the-art data structures for reporting the set $\mathsf{MAW}(T)$ of MAWs from a given string $T$ of length $n$ require $O(n)$ space, can be built in $O(n)$ time, and can report all MAWs in $O(|\mathsf{MAW}(T)|)$ time upon a query. This paper initiates the problem of computing MAWs from a compressed representation of a string. In particular, we focus on the most basic compressed representation of a string, run-length encoding (RLE), which represents each maximal run of the same characters $a$ by $a^p$ where $p$ is the length of the run. Let $m$ be the RLE-size of string $T$ . After categorizing the MAWs into five disjoint sets $\mathcal{M}_1$ , $\mathcal{M}_2$ , $\mathcal{M}_3$ , $\mathcal{M}_4$ , $\mathcal{M}_5$ using RLE, we present matching upper and lower bounds for the number of MAWs in $\mathcal{M}_i$ for $i = 1,2,4,5$ in terms of RLE-size $m$ , except for $\mathcal{M}_3$ whose size is unbounded by $m$ . We then present a compact $O(m)$ -space data structure that can report all MAWs in optimal $O(|\mathsf{MAW}(T)|)$ time.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.