2 Search Results for "Horiyama, Takashi"


Document
{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-dev.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
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-dev.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}
}
  • Refine by Author
  • 2 Horiyama, Takashi
  • 1 Hosoya, Haruo
  • 1 Inenaga, Shunsuke
  • 1 Mieno, Takuya
  • 1 Uehara, Ryuhei

  • Refine by Classification
  • 1 Mathematics of computing → Combinatorics on words

  • Refine by Keyword
  • 1 Fibonacci words
  • 1 RePair
  • 1 convex polygon
  • 1 enumeration algorithm
  • 1 grammar based compression
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2016
  • 1 2022

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail