Source author record

Takuya Mieno

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 math.CO Formal Languages and Automata Theory

Catalog footprint

Research overview

7works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2025arXiv

Subsequence Matching and LCS under Cartesian-Tree Equivalence

Two strings of the same length are said to Cartesian-tree match (CT-match) if their Cartesian-trees are isomorphic [Park et al., TCS 2020]. Cartesian-tree matching is a natural model that allows for capturing similarities of numerical sequences. Oizumi et al. [CPM 2022] showed that subsequence pattern matching under CT-matching model (CT-MSeq) can be solved in $O(nm \log \log n)$ time, where $n$ and $m$ are text and pattern lengths, respectively. This current article follows this line of research, and gives the following new results: (1) An $O(nm)$ -time CT-MSeq algorithm for binary alphabets; (2) An $O((nm)^{1-ε})$ -time conditional lower bound for the CT-MSeq problem on alphabets of size 4, for any constant $ε> 0$ , under the Orthogonal Vector Hypothesis (OVH). Further, we introduce the new problem of longest common subsequence under CT-matching (CT-LCS) for two given strings $S$ and $T$ of length $n$ , and present the following results: (3) An $O(n^6)$ -time CT-LCS algorithm for general ordered alphabets; (4) An $O(n^2 / \log n)$ -time CT-LCS algorithm for binary alphabets; (5) An $O(n^{2-ε})$ -time conditional lower bound for the CT-LCS problem on alphabets of size 5, for any constant $ε> 0$ , under OVH.

preprint2022arXiv

Cartesian Tree Subsequence Matching

Park et al. [TCS 2020] observed that the similarity between two (numerical) strings can be captured by the Cartesian trees: The Cartesian tree of a string is a binary tree recursively constructed by picking up the smallest value of the string as the root of the tree. Two strings of equal length are said to Cartesian-tree match if their Cartesian trees are isomorphic. Park et al. [TCS 2020] introduced the following Cartesian tree substring matching (CTMStr) problem: Given a text string $T$ of length $n$ and a pattern string of length $m$ , find every consecutive substring $S = T[i..j]$ of a text string $T$ such that $S$ and $P$ Cartesian-tree match. They showed how to solve this problem in $\tilde{O}(n+m)$ time. In this paper, we introduce the Cartesian tree subsequence matching (CTMSeq) problem, that asks to find every minimal substring $S = T[i..j]$ of $T$ such that $S$ contains a subsequence $S'$ which Cartesian-tree matches $P$ . We prove that the CTMSeq problem can be solved efficiently, in $O(m n p(n))$ time, where $p(n)$ denotes the update/query time for dynamic predecessor queries. By using a suitable dynamic predecessor data structure, we obtain $O(mn \log \log n)$ -time and $O(n \log m)$ -space solution for CTMSeq. This contrasts CTMSeq with closely related order-preserving subsequence matching (OPMSeq) which was shown to be NP-hard by Bose et al. [IPL 1998].

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.

preprint2022arXiv

RePair Grammars are the Smallest Grammars for Fibonacci Words

Grammar-based compression is a loss-less data compression scheme that represents a given string $w$ by a context-free grammar that generates only $w$ . While computing the smallest grammar which generates a given string $w$ is NP-hard in general, a number of polynomial-time grammar-based compressors which work well in practice have been proposed. RePair, proposed by Larsson and Moffat in 1999, is a grammar-based compressor which recursively replaces all possible occurrences of a most frequently occurring bigrams in the string. Since there can be multiple choices of the most frequent bigrams to replace, different implementations of RePair can result in different grammars. In this paper, we show that the smallest grammars generating the Fibonacci words $F_k$ can be completely characterized by RePair, where $F_k$ denotes the $k$ -th Fibonacci word. Namely, all grammars for $F_k$ generated by any implementation of RePair are the smallest grammars for $F_k$ , and no other grammars can be the smallest for $F_k$ . To the best of our knowledge, Fibonacci words are the first non-trivial infinite family of strings for which RePair is optimal.

preprint2020arXiv

Lyndon Words, the Three Squares Lemma, and Primitive Squares

We revisit the so-called "Three Squares Lemma" by Crochemore and Rytter [Algorithmica 1995] and, using arguments based on Lyndon words, derive a more general variant which considers three overlapping squares which do not necessarily share a common prefix. We also give an improved upper bound of $n\log_2 n$ on the maximum number of (occurrences of) primitively rooted squares in a string of length $n$ , also using arguments based on Lyndon words. To the best of our knowledge, the only known upper bound was $n \log_ϕn \approx 1.441n\log_2 n$ , where $ϕ$ is the golden ratio, reported by Fraenkel and Simpson [TCS 1999] obtained via the Three Squares Lemma.

preprint2020arXiv

Space-Efficient Algorithms for Computing Minimal/Shortest Unique Substrings

Given a string $T$ of length $n$ , a substring $u = T[i..j]$ of $T$ is called a shortest unique substring (SUS) for an interval $[s,t]$ if (a) $u$ occurs exactly once in $T$ , (b) $u$ contains the interval $[s,t]$ (i.e. $i \leq s \leq t \leq j$ ), and (c) every substring $v$ of $T$ with $|v| < |u|$ containing $[s,t]$ occurs at least twice in $T$ . Given a query interval $[s, t] \subset [1, n]$ , the interval SUS problem is to output all the SUSs for the interval $[s,t]$ . In this article, we propose a $4n + o(n)$ bits data structure answering an interval SUS query in output-sensitive $O(\mathit{occ})$ time, where $\mathit{occ}$ is the number of returned SUSs. Additionally, we focus on the point SUS problem, which is the interval SUS problem for $s = t$ . Here, we propose a $\lceil (\log_2{3} + 1)n \rceil + o(n)$ bits data structure answering a point SUS query in the same output-sensitive time. We also propose space-efficient algorithms for computing the minimal unique substrings of $T$ .

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.

Takuya Mieno

Research overview

Is this your work?

7 publications

Subsequence Matching and LCS under Cartesian-Tree Equivalence

Cartesian Tree Subsequence Matching

Combinatorics of minimal absent words for a sliding window

Minimal Absent Words on Run-Length Encoded Strings

RePair Grammars are the Smallest Grammars for Fibonacci Words

Lyndon Words, the Three Squares Lemma, and Primitive Squares

Space-Efficient Algorithms for Computing Minimal/Shortest Unique Substrings

See the researcher in context

Building this map preview