1 citations · 1 across the 11 of their papers we have counts for
7 papers · 1 filter
Disproving the Greedy Superstring Conjecture
Hiroki Shibata
The shortest common superstring problem is to find the shortest string that contains every string in a given set as a substring. It is conjectured that the greedy algorithm that re…
Sensitivity and Size Relationships of the Lempel-Ziv Factorization
Hiroki Shibata, Yuto Fujie
The Lempel-Ziv (LZ) factorization is a fundamental method for compressing repetitive strings. Its multiplicative sensitivity to an operation measures how much that operation can in…
Compact Enumeration of Maximal Closed Substrings in Run-Length Encoded Strings
Haruki Umezaki, Hiroki Shibata, Yuto Nakashima +1
A string is closed if , or if has a non-empty proper border occurring only as its prefix and suffix. A maximal closed substring (MCS) is a maximal occurrence of a cl…
Online computation of maximal closed substrings
Hiroki Shibata, Haruki Umezaki, Takuya Mieno +2
A non-empty string is closed if it has length one or its longest border appears exactly twice in the string. An occurrence of a closed substring is a maximal closed substring (MCS)…
Relaxation of Square-Freeness
Hiroki Shibata, Takuya Mieno, Dominik Köppl +1
We extend the analysis of nonrepetitive sequences of Entringer et al. [Journal of Combinatorial Theory, 1974] to relaxations of equality testing under nonstandard equivalence relat…
String Representation Based on Substring Equation Systems
Hiroki Shibata, Hideo Bannai
Repetitiveness measures quantify how much repetitive structure a string contains and serve as parameters for compressed representations and indexing data structures. Many compressi…
Online Computation of Palindromes and Suffix Trees on Tries
Hiroki Shibata, Mitsuru Funakoshi, Takuya Mieno +5
We consider the problems of computing maximal palindromes and distinct palindromes in a trie. A trie is a natural generalization of a string, which can be seen as a single-path tre…