Search Results

Documents authored by Horiyama, Takashi

Document
DOI: 10.4230/LIPIcs.CPM.2024.24
Shortest Cover After Edit

Authors: Kazuki Mitani, Takuya Mieno, Kazuhisa Seto, and Takashi Horiyama

Published in: LIPIcs, Volume 296, 35th Annual Symposium on Combinatorial Pattern Matching (CPM 2024)

Abstract
This paper investigates the (quasi-)periodicity of a string when the string is edited. A string C is called a cover (as known as a quasi-period) of a string T if each character of T lies within some occurrence of C. By definition, a cover of T must be a border of T; that is, it occurs both as a prefix and as a suffix of T. In this paper, we focus on the changes in the longest border and the shortest cover of a string when the string is edited only once. We propose a data structure of size O(n) that computes the longest border and the shortest cover of the string in O(𝓁 log n) time after an edit operation (either insertion, deletion, or substitution of some string) is applied to the input string T of length n, where 𝓁 is the length of the string being inserted or substituted. The data structure can be constructed in O(n) time given string T.
Cite as

Kazuki Mitani, Takuya Mieno, Kazuhisa Seto, and Takashi Horiyama. Shortest Cover After Edit. In 35th Annual Symposium on Combinatorial Pattern Matching (CPM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 296, pp. 24:1-24:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{mitani_et_al:LIPIcs.CPM.2024.24,
  author =	{Mitani, Kazuki and Mieno, Takuya and Seto, Kazuhisa and Horiyama, Takashi},
  title =	{{Shortest Cover After Edit}},
  booktitle =	{35th Annual Symposium on Combinatorial Pattern Matching (CPM 2024)},
  pages =	{24:1--24:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-326-3},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{296},
  editor =	{Inenaga, Shunsuke and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2024.24},
  URN =		{urn:nbn:de:0030-drops-201345},
  doi =		{10.4230/LIPIcs.CPM.2024.24},
  annote =	{Keywords: string algorithm, border, cover, quasi-periodicity, dynamic string}
}
Document
DOI: 10.4230/LIPIcs.CPM.2022.26
{RePair} Grammars Are the Smallest Grammars for Fibonacci Words

Authors: Takuya Mieno, Shunsuke Inenaga, and Takashi Horiyama

Published in: LIPIcs, Volume 223, 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022)

Abstract
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.
Cite as

Takuya Mieno, Shunsuke Inenaga, and Takashi Horiyama. {RePair} Grammars Are the Smallest Grammars for Fibonacci Words. In 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 223, pp. 26:1-26:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{mieno_et_al:LIPIcs.CPM.2022.26,
  author =	{Mieno, Takuya and Inenaga, Shunsuke and Horiyama, Takashi},
  title =	{{\{RePair\} Grammars Are the Smallest Grammars for Fibonacci Words}},
  booktitle =	{33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022)},
  pages =	{26:1--26:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-234-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{223},
  editor =	{Bannai, Hideo and Holub, Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2022.26},
  URN =		{urn:nbn:de:0030-drops-161530},
  doi =		{10.4230/LIPIcs.CPM.2022.26},
  annote =	{Keywords: grammar based compression, Fibonacci words, RePair, smallest grammar problem}
}
Document
DOI: 10.4230/LIPIcs.FUN.2016.20
Convex Configurations on Nana-kin-san Puzzle

Authors: Takashi Horiyama, Ryuhei Uehara, and Haruo Hosoya

Published in: LIPIcs, Volume 49, 8th International Conference on Fun with Algorithms (FUN 2016)

Abstract
We investigate a silhouette puzzle that is recently developed based on the golden ratio. Traditional silhouette puzzles are based on a simple tile. For example, the tangram is based on isosceles right triangles; that is, each of seven pieces is formed by gluing some identical isosceles right triangles. Using the property, we can analyze it by hand, that is, without computer. On the other hand, if each piece has no special property, it is quite hard even using computer since we have to handle real numbers without numerical errors during computation. The new silhouette puzzle is between them; each of seven pieces is not based on integer length and right angles, but based on golden ratio, which admits us to represent these seven pieces in some nontrivial way. Based on the property, we develop an algorithm to handle the puzzle, and our algorithm succeeded to enumerate all convex shapes that can be made by the puzzle pieces. It is known that the tangram and another classic silhouette puzzle known as Sei-shonagon chie no ita can form 13 and 16 convex shapes, respectively. The new puzzle, Nana-kin-san puzzle, admits to form 62 different convex shapes.
Cite as

Takashi Horiyama, Ryuhei Uehara, and Haruo Hosoya. Convex Configurations on Nana-kin-san Puzzle. In 8th International Conference on Fun with Algorithms (FUN 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 49, pp. 20:1-20:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{horiyama_et_al:LIPIcs.FUN.2016.20,
  author =	{Horiyama, Takashi and Uehara, Ryuhei and Hosoya, Haruo},
  title =	{{Convex Configurations on Nana-kin-san Puzzle}},
  booktitle =	{8th International Conference on Fun with Algorithms (FUN 2016)},
  pages =	{20:1--20:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-005-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{49},
  editor =	{Demaine, Erik D. and Grandoni, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2016.20},
  URN =		{urn:nbn:de:0030-drops-58730},
  doi =		{10.4230/LIPIcs.FUN.2016.20},
  annote =	{Keywords: silhouette puzzles, nana-kin-san puzzle, enumeration algorithm, convex polygon}
}
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact