Updated on 2024/10/07

Information

 

写真a

 
NAKASHIMA YUTO
 
Organization
Faculty of Information Science and Electrical Engineering Department of Informatics Associate Professor
School of Sciences Department of Physics（Concurrent）
Graduate School of Information Science and Electrical Engineering Department of Information Science and Technology（Concurrent）
Title
Associate Professor
Profile
文字列の組合せ論および文字列データ処理アルゴリズムの研究を行なっている． 教育では主に，理学部物理学科情報理学コースの演習科目を担当している．
External link

Research Areas

  • Informatics / Theory of informatics

Degree

  • Ph.D.(Information Science)

Research History

  • Kyushu University Faculty of Information Science and Electrical Engineering, Department of Informatics Associate Professor

    2024.6 - Present

    　 More details

    Country：Japan

    researchmap

  • Kyushu University Faculty of Information Science and Electrical Engineering, Department of Informatics Assistant Professor

    2017.4 - 2024.5

    　 More details

Research Interests・Research Keywords

  • Research theme：Combinatorics on words

    Keyword：Combinatorics on words

    Research period： 2024

  • Research theme：String Algorithm

    Keyword：String Algorithm

    Research period： 2024

  • Research theme：String Processing Algorithms, Combinatorics on Words

    Keyword：Pattern Matching, Streaming Model, Lyndon Words

    Research period： 2017.4

Awards

  • IPSJ Yamashita SIG Research Award

    2024.3   Information Processing Society of Japan  

    　More details

  • SPIRE2020 Best Paper Award

    2020.10   SPIRE2020  

Papers

  • On the Number of Non-equivalent Parameterized Squares in a String Reviewed

    Rikuya Hamai, Kazushi Taketsugu, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai

    Proceedings of 31th International Symposium on String Processing and Information Retrieval (SPIRE 2024)   174 - 183   2024.9

    　More details

    Language：English   Publishing type：Research paper (international conference proceedings)  

    researchmap

  • Edit and Alphabet-Ordering Sensitivity of Lex-Parse Reviewed

    Yuto Nakashima, Dominik Köppl, Mitsuru Funakoshi, Shunsuke Inenaga, Hideo Bannai

    Proceedings of the 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)   75:1 - 75:15   2024.8

    　More details

    Language：English   Publishing type：Research paper (international conference proceedings)  

    researchmap

  • Computing Maximal Palindromes in Non-standard Matching Models. Reviewed

    Mitsuru Funakoshi, Takuya Mieno, Yuto Nakashima 0001, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

    Proceedings of the 35th International Workshop on Combinatorial Algorithms (IWOCA 2024)   165 - 179   2024.7

    　More details

    Language：English   Publishing type：Research paper (international conference proceedings)  

    DOI： 10.1007/978-3-031-63021-7_13

    researchmap

    Other Link： https://dblp.uni-trier.de/db/conf/iwoca/iwoca2024.html#FunakoshiMNIBT24

  • Computing Longest Common Subsequence Under Cartesian-Tree Matching Model. Reviewed

    Taketo Tsujimoto, Hiroki Shibata, Takuya Mieno, Yuto Nakashima 0001, Shunsuke Inenaga

    Proceedings of the 35th International Workshop on Combinatorial Algorithms (IWOCA 2024)   369 - 381   2024.7

    　More details

    Language：English   Publishing type：Research paper (international conference proceedings)  

    DOI： 10.1007/978-3-031-63021-7_28

    researchmap

    Other Link： https://dblp.uni-trier.de/db/conf/iwoca/iwoca2024.html#TsujimotoSMNI24

  • Faster space-efficient STR-IC-LCS computation Reviewed

    Yuki Yonemoto, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai

    Theoretical Computer Science   1003   114607 - 114607   2024.5   （ ISSN:0304-3975 ）

    　More details

    Language：English   Publishing type：Research paper (scientific journal)   Publisher：Elsevier BV  

    DOI： 10.1016/j.tcs.2024.114607

    Scopus

    researchmap

  • Largest Repetition Factorization of Fibonacci Words Reviewed

    Kaisei Kishi, Yuto Nakashima, Shunsuke Inenaga

    Proceedings of 30th International Symposium on String Processing and Information Retrieval (SPIRE 2023)   2023.9

    　More details

    Language：English   Publishing type：Research paper (international conference proceedings)  

  • Linear-Time Computation of Generalized Minimal Absent Words for Multiple Strings. Reviewed

    Kouta Okabe, Takuya Mieno, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai

    Proceedings of 30th International Symposium on String Processing and Information Retrieval (SPIRE 2023)   14240 LNCS   331 - 344   2023.9   （ ISSN:0302-9743 ISBN:9783031439797, 9783031439803 eISSN:1611-3349 ）

    　More details

    Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Springer Nature Switzerland  

    DOI： 10.1007/978-3-031-43980-3_27

    Scopus

    researchmap

  • Optimally Computing Compressed Indexing Arrays Based on the Compact Directed Acyclic Word Graph. Reviewed

    Hiroki Arimura, Shunsuke Inenaga, Yasuaki Kobayashi, Yuto Nakashima, Mizuki Sue

    Proceedings of 30th International Symposium on String Processing and Information Retrieval (SPIRE 2023)   14240 LNCS   28 - 34   2023.9   （ ISSN:03029743 ISBN:9783031439797 ）

    　More details

    Language：English   Publishing type：Research paper (international conference proceedings)  

    DOI： 10.1007/978-3-031-43980-3_3

    Scopus

    researchmap

    Other Link： https://dblp.uni-trier.de/db/conf/spire/spire2023.html#ArimuraIKNS23

  • Computing SEQ-IC-LCS of Labeled Graphs Reviewed International journal

    Yuki Yonemoto, Yuto Nakashima, Shunsuke Inenaga

    Proceedings of the Prague Stringology Conference 2023 (PSC 2023)   2023.8

    　More details

    Language：English   Publishing type：Research paper (international conference proceedings)  

  • On Sensitivity of Compact Directed Acyclic Word Graphs Reviewed International journal

    Hiroto Fujimaru, Yuto Nakashima, Shunsuke Inenaga

    Proceedings of 14th International Conference on Words (WORDS 2023)   168 - 180   2023.6

    　More details

    Language：English   Publishing type：Research paper (international conference proceedings)  

  • Optimal LZ-End Parsing Is Hard Reviewed International journal

    Hideo Bannai, Mitsuru Funakoshi, Kazuhiro Kurita, Yuto Nakashima, Kazuhisa Seto, Takeaki Uno

    Proceedings of the 34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)   3:1 - 3:11   2023.6

    　More details

    Language：English   Publishing type：Research paper (international conference proceedings)  

  • Space-Efficient STR-IC-LCS Computation Reviewed International journal

    Yuuki Yonemoto, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai

    Proceedings of 47th International Conference on Current Trends in Theory and Practice of Informatics (SOFSEM 2023)   372 - 384   2023.1

    　More details

    Language：English   Publishing type：Research paper (international conference proceedings)  

  • Parameterized DAWGs: Efficient constructions and bidirectional pattern searches Reviewed

    Katsuhito Nakashima, Noriki Fujisato, Diptarama Hendrian, Yuto Nakashima, Ryo Yoshinaka, Shunsuke Inenaga, Hideo Bannai, Ayumi Shinohara, Masayuki Takeda

    Theoretical Computer Science   933   21 - 42   2022.10   （ ISSN:0304-3975 eISSN:1879-2294 ）

    　More details

    Language：English   Publishing type：Research paper (scientific journal)   Publisher：Elsevier BV  

    DOI： 10.1016/j.tcs.2022.09.008

    Web of Science

    Scopus

    researchmap

  • Combinatorics of minimal absent words for a sliding window Reviewed

    Tooru Akagi, Yuki Kuhara, Takuya Mieno, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

    Theoretical Computer Science   927   109 - 119   2022.6   （ ISSN:0304-3975 eISSN:1879-2294 ）

    　More details

    Language：English   Publishing type：Research paper (scientific journal)   Publisher：Elsevier BV  

    DOI： 10.1016/j.tcs.2022.06.002

    Web of Science

    Scopus

    researchmap

  • Minimal Absent Words on Run-Length Encoded Strings Reviewed International journal

    Tooru Akagi, Kouta Okabe, Takuya Mieno, Yuto Nakashima, Shunsuke Inenaga

    Proceedings of the 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022)   27:1 - 27:17   2022.6

    　More details

    Language：English   Publishing type：Research paper (international conference proceedings)  

  • c-trie++: A dynamic trie tailored for fast prefix searches Reviewed

    Kazuya Tsuruta, Dominik Köppl, Shunsuke Kanda, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

    Information and Computation   285   104794 - 104794   2022.5   （ ISSN:0890-5401 ）

    　More details

    Language：English   Publishing type：Research paper (scientific journal)   Publisher：Elsevier BV  

    DOI： 10.1016/j.ic.2021.104794

    Scopus

    researchmap

  • Factorizing strings into repetitions Reviewed International journal

    Hiroe Inoue, Yoshiaki Matsuoka, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

    Theory of Computing Systems   66 ( 2 )   484 - 501   2022.4

    　More details

    Language：English   Publishing type：Research paper (scientific journal)  

  • Palindromic Trees for a Sliding Window and Its Applications Reviewed

    Takuya Mieno, Kiichi Watanabe, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

    Information Processing Letters   173   106174 - 106174   2022.1   （ ISSN:0020-0190 eISSN:1872-6119 ）

    　More details

    Language：English   Publishing type：Research paper (scientific journal)   Publisher：Elsevier BV  

    DOI： 10.1016/j.ipl.2021.106174

    Web of Science

    Scopus

    researchmap

  • The Parameterized Suffix Tray Reviewed International journal

    Noriki Fujisato, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

    Proceedings of 12th International Conference on Algorithms and Complexity (CIAC 2021)   258 - 270   2021.10

    　More details

    Language：English   Publishing type：Research paper (international conference proceedings)  

  • Efficiently computing runs on a trie Reviewed

    Ryo Sugahara, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

    Theoretical Computer Science   887   143 - 151   2021.10

    　More details

    Language：English   Publishing type：Research paper (scientific journal)  

    DOI： 10.1016/j.tcs.2021.07.011

  • Position Heaps for Cartesian-Tree Matching on Strings and Tries Reviewed International journal

    Akio Nishimoto, Noriki Fujisato, Yuto Nakashima, Shunsuke Inenaga

    Proceedings of 28th International Symposium in String Processing and Information Retrieval (SPIRE 2021)   241 - 254   2021.10

    　More details

    Language：English   Publishing type：Research paper (international conference proceedings)  

  • On the Approximation Ratio of LZ-End to LZ77 Reviewed International journal

    Takumi Ideue, Takuya Mieno, Mitsuru Funakoshi, Yuto Nakashima, Shunsuke Inenaga, Masayuki Takeda

    Proceedings of 28th International Symposium in String Processing and Information Retrieval (SPIRE 2021)   114 - 126   2021.10

    　More details

    Language：English   Publishing type：Research paper (international conference proceedings)  

  • Longest Common Rollercoasters Reviewed International journal

    Kosuke Fujita, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

    Proceedinds of 28th International Symposium in String Processing and Information Retrieval (SPIRE 2021)   21 - 32   2021.10

    　More details

    Language：English   Publishing type：Research paper (international conference proceedings)  

  • Grammar Index by Induced Suffix Sorting Reviewed International journal

    Proceedings of 28th International Symposium in String Processing and Information Retrieval (SPIRE 2021)   85 - 99   2021.10

    　More details

    Language：English   Publishing type：Research paper (international conference proceedings)  

  • Counting Lyndon Subsequence Reviewed

    Ryo Hirakawa, Yuto Nakashima, Shunsuke Inenaga, Masayuki Takeda

    Proceedings of the Prague Stringology Conference 2021 (PSC 2021)   53 - 60   2021.8

    　More details

    Language：English   Publishing type：Research paper (international conference proceedings)  

  • Computing Minimal Unique Substrings for a Sliding Window Reviewed

    Takuya Mieno, Yuta Fujishige, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

    Algorithmica   84 ( 3 )   670 - 693   2021.8   （ ISSN:0178-4617 eISSN:1432-0541 ）

    　More details

    Language：English   Publishing type：Research paper (scientific journal)   Publisher：Springer Science and Business Media LLC  

    <title>Abstract</title>A substring <italic>u</italic> of a string <italic>T</italic> is called a <italic>minimal unique substring</italic> (<italic>MUS</italic>) of <italic>T</italic> if <italic>u</italic> occurs exactly once in <italic>T</italic> and any proper substring of <italic>u</italic> occurs at least twice in <italic>T</italic>. In this paper, we study the problem of computing MUSs for a sliding window over a given string <italic>T</italic>. We first show how the set of MUSs can change when the window slides over <italic>T</italic>. We then present an <inline-formula><alternatives><tex-math>$$O(n\log \sigma ')$$</tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML">
    <mml:mrow>
    <mml:mi>O</mml:mi>
    <mml:mo>(</mml:mo>
    <mml:mi>n</mml:mi>
    <mml:mo>log</mml:mo>
    <mml:msup>
    <mml:mi>σ</mml:mi>
    <mml:mo>′</mml:mo>
    </mml:msup>
    <mml:mo>)</mml:mo>
    </mml:mrow>
    </mml:math></alternatives></inline-formula>-time and <italic>O</italic>(<italic>d</italic>)-space algorithm to compute MUSs for a sliding window of size <italic>d</italic> over the input string <italic>T</italic> of length <italic>n</italic>, where <inline-formula><alternatives><tex-math>$$\sigma '\le d$$</tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML">
    <mml:mrow>
    <mml:msup>
    <mml:mi>σ</mml:mi>
    <mml:mo>′</mml:mo>
    </mml:msup>
    <mml:mo>≤</mml:mo>
    <mml:mi>d</mml:mi>
    </mml:mrow>
    </mml:math></alternatives></inline-formula> is the maximum number of distinct characters in every window.

    DOI： 10.1007/s00453-021-00864-1

    Web of Science

    Scopus

    researchmap

    Other Link： https://link.springer.com/article/10.1007/s00453-021-00864-1/fulltext.html

  • Compressed Communication Complexity of Hamming Distance Reviewed

    Shiori Mitsuya, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

    Algorithms   14 ( 4 )   116 - 116   2021.4

    　More details

    Language：English   Publishing type：Research paper (scientific journal)  

    DOI： 10.3390/a14040116

  • Computing longest palindromic substring after single-character or block-wise edits. Reviewed

    Mitsuru Funakoshi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

    Theor. Comput. Sci.   859   116 - 133   2021.3

    　More details

    Language：Others   Publishing type：Research paper (scientific journal)  

    DOI： 10.1016/j.tcs.2021.01.014

  • Space-efficient algorithms for computing minimal/shortest unique substrings. Reviewed

    Theor. Comput. Sci.   845   230 - 242   2020.12

    　More details

    Language：Others   Publishing type：Research paper (scientific journal)  

    DOI： 10.1016/j.tcs.2020.09.017

  • Lyndon Words, the Three Squares Lemma, and Primitive Squares. Reviewed

    Hideo Bannai, Takuya Mieno, Yuto Nakashima

    Proceedings of 27th International Symposium on String Processing and Information Retrieval (SPIRE 2020)   265 - 273   2020.10

    　More details

    Language：Others   Publishing type：Research paper (other academic)  

    DOI： 10.1007/978-3-030-59212-7_19

  • Towards Efficient Interactive Computation of Dynamic Time Warping Distance. Reviewed

    Akihiro Nishi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

    Proceedings of 27th International Symposium on String Processing and Information Retrieval (SPIRE 2020)   27 - 41   2020.10

    　More details

    Language：Others   Publishing type：Research paper (other academic)  

    DOI： 10.1007/978-3-030-59212-7_3

  • On Repetitiveness Measures of Thue-Morse Words. Reviewed

    Kanaru Kutsukake, Takuya Matsumoto, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

    Proceedings of 27th International Symposium on String Processing and Information Retrieval (SPIRE 2020)   213 - 220   2020.10

    　More details

    Language：Others   Publishing type：Research paper (other academic)  

    DOI： 10.1007/978-3-030-59212-7_15

  • Grammar-compressed Self-index with Lyndon Words Reviewed

    13 ( 2 )   84 - 92   2020.8

    　More details

    Language：English  

    Grammar-compressed Self-index with Lyndon Words
    We introduce a new class of straight-line programs (SLPs), named the Lyndon SLP, inspired by the Lyndon trees (Barcelo, 1990). Based on this SLP, we propose a self-index data structure of O(g) words of spacethat can be built from a string T in O(n lg n) expected time, retrieving the starting positions of all occurrences of a pattern P of length m in O(m + lg m lg n + occ lg g) time, where n is the length of T, g is the size of the Lyndon SLP for T, and occ is the number of occurrences of P in T.We introduce a new class of straight-line programs (SLPs), named the Lyndon SLP, inspired by the Lyndon trees (Barcelo, 1990). Based on this SLP, we propose a self-index data structure of O(g) words of spacethat can be built from a string T in O(n lg n) expected time, retrieving the starting positions of all occurrences of a pattern P of length m in O(m + lg m lg n + occ lg g) time, where n is the length of T, g is the size of the Lyndon SLP for T, and occ is the number of occurrences of P in T.

  • DAWGs for Parameterized Matching Online Construction and Related Indexing Structures

    Katsuhito Nakashima, Noriki Fujisato, Diptarama Hendrian, Yuto Nakashima, Ryo Yoshinaka, Shunsuke Inenaga, Hideo Bannai, Ayumi Shinohara, Masayuki Takeda

    31st Annual Symposium on Combinatorial Pattern Matching, CPM 2020 31st Annual Symposium on Combinatorial Pattern Matching, CPM 2020   2020.6

    　More details

    Language：English   Publishing type：Research paper (other academic)  

    DOI： 10.4230/LIPIcs.CPM.2020.26

  • Detecting k-(Sub-)Cadences and Equidistant Subsequence Occurrences

    Mitsuru Funakoshi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Ayumi Shinohara

    31st Annual Symposium on Combinatorial Pattern Matching, CPM 2020 31st Annual Symposium on Combinatorial Pattern Matching, CPM 2020   2020.6

    　More details

    Language：English   Publishing type：Research paper (other academic)  

    DOI： 10.4230/LIPIcs.CPM.2020.12

  • Practical grammar compression based on maximal repeats Reviewed

    Isamu Furuya, Takuya Takagi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Takuya Kida

    Algorithms   13 ( 4 )   2020.4

    　More details

    Language：English   Publishing type：Research paper (scientific journal)  

    DOI： 10.3390/A13040103

  • C-Trie++ A dynamic trie tailored for fast prefix searches

    2020 Data Compression Conference, DCC 2020 Proceedings - DCC 2020 Data Compression Conference   243 - 252   2020.3

    　More details

    Language：English   Publishing type：Research paper (other academic)  

    DOI： 10.1109/DCC47342.2020.00032

  • Faster STR-EC-LCS Computation

    Kohei Yamada, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

    Proceedings of 46th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2020   125 - 135   2020.1

    　More details

    Language：English   Publishing type：Research paper (other academic)  

    DOI： 10.1007/978-3-030-38919-2_11

  • Fast Algorithms for the Shortest Unique Palindromic Substring Problem on Run-Length Encoded Strings Reviewed

    Kiichi Watanabe, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

    Theory of Computing Systems   2020.1

    　More details

    Language：English   Publishing type：Research paper (scientific journal)  

    DOI： 10.1007/s00224-020-09980-x

  • Minimal Unique Substrings and Minimal Absent Words in a Sliding Window

    Takuya Mieno, Yuki Kuhara, Tooru Akagi, Yuta Fujishige, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

    Proceedings of 46th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2020   148 - 160   2020.1

    　More details

    Language：English   Publishing type：Research paper (other academic)  

    DOI： 10.1007/978-3-030-38919-2_13

  • An improved data structure for left-right maximal generic words problem

    Yuta Fujishige, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

    Proceedings of 30th International Symposium on Algorithms and Computation, ISAAC 2019   2019.12

    　More details

    Language：English   Publishing type：Research paper (other academic)  

    DOI： 10.4230/LIPIcs.ISAAC.2019.40

  • On the size of the smallest alphabet for Lyndon trees Reviewed

    Yuto Nakashima, Takuya Takagi, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

    Theoretical Computer Science   792   131 - 143   2019.11

    　More details

    Language：English   Publishing type：Research paper (scientific journal)  

    DOI： 10.1016/j.tcs.2018.06.044

  • Compact Data Structures for Shortest Unique Substring Queries

    Proceedings of 26th International Symposium on String Processing and Information Retrieval, SPIRE 2019   107 - 123   2019.10

    　More details

    Language：English   Publishing type：Research paper (other academic)  

    DOI： 10.1007/978-3-030-32686-9_8

  • Direct Linear Time Construction of Parameterized Suffix and LCP Arrays for Constant Alphabets

    Noriki Fujisato, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

    Proceedings of 26th International Symposium on String Processing and Information Retrieval, SPIRE 2019   382 - 391   2019.10

    　More details

    Language：English   Publishing type：Research paper (other academic)  

    DOI： 10.1007/978-3-030-32686-9_27

  • On Longest Common Property Preserved Substring Queries

    Kazuki Kai, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Tomasz Kociumaka

    Proceedings of 26th International Symposium on String Processing and Information Retrieval, SPIRE 2019   162 - 174   2019.10

    　More details

    Language：English   Publishing type：Research paper (other academic)  

    DOI： 10.1007/978-3-030-32686-9_12

  • Computing maximal palindromes and distinct palindromes in a trie

    Mitsuru Funakoshi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

    23rd Prague Stringology Conference, PSC 2019 Proceedings of the Prague Stringology Conference, PSC 2019   3 - 15   2019.8

    　More details

    Language：English   Publishing type：Research paper (other academic)  

  • Shortest unique palindromic substring queries on run-length encoded strings

    Kiichi Watanabe, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

    Proceedings of 30th International Workshop on Combinatorial Algorithms, IWOCA 2019   430 - 441   2019.7

    　More details

    Language：English   Publishing type：Research paper (other academic)  

    DOI： 10.1007/978-3-030-25005-8_35

  • Computing runs on a trie

    Ryo Sugahara, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

    Proceedings of 30th Annual Symposium on Combinatorial Pattern Matching, CPM 2019   2019.6

    　More details

    Language：English   Publishing type：Research paper (other academic)  

    DOI： 10.4230/LIPIcs.CPM.2019.23

  • On the size of overlapping Lempel-Ziv and Lyndon factorizations

    Yuki Urabe, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

    Proceedings of 30th Annual Symposium on Combinatorial Pattern Matching, CPM 2019   2019.6

    　More details

    Language：English   Publishing type：Research paper (other academic)  

    DOI： 10.4230/LIPIcs.CPM.2019.29

  • Faster queries for longest substring palindrome after block edit

    Mitsuru Funakoshi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

    Proceedings of 30th Annual Symposium on Combinatorial Pattern Matching, CPM 2019   2019.6

    　More details

    Language：English   Publishing type：Research paper (other academic)  

    DOI： 10.4230/LIPIcs.CPM.2019.27

  • The Parameterized Position Heap of a Trie

    Noriki Fujisato, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

    Proceedings of 11th International Conference on Algorithms and Complexity, CIAC 2019   237 - 248   2019.5

    　More details

    Language：English   Publishing type：Research paper (other academic)  

    DOI： 10.1007/978-3-030-17402-6_20

  • MR-RePair Grammar Compression Based on Maximal Repeats

    Isamu Furuya, Takuya Takagi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Takuya Kida

    2019 Data Compression Conference, DCC 2019 Proceedings - DCC 2019 2019 Data Compression Conference   508 - 517   2019.3

    　More details

    Language：English   Publishing type：Research paper (other academic)  

    DOI： 10.1109/DCC.2019.00059

  • Recovering, counting and enumerating strings from forward and backward suffix arrays

    Yuki Kuhara, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

    25th International Symposium on String Processing and Information Retrieval, SPIRE 2018 String Processing and Information Retrieval - 25th International Symposium, SPIRE 2018, Proceedings   254 - 267   2018.10

    　More details

    Language：English   Publishing type：Research paper (other academic)  

    DOI： 10.1007/978-3-030-00479-8_21

  • Algorithms and combinatorial properties on shortest unique palindromic substrings Reviewed

    Hiroe Inoue, Yuto Nakashima, Takuya Mieno, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

    Journal of Discrete Algorithms   52-53   122 - 132   2018.9

    　More details

    Language：English   Publishing type：Research paper (scientific journal)  

    DOI： 10.1016/j.jda.2018.11.009

  • Right-to-left online construction of parameterized position heaps

    Noriki Fujisato, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

    22nd Prague Stringology Conference, PSC 2018 Proceedings of the Prague Stringology Conference, PSC 2018   91 - 102   2018.8

    　More details

    Language：English   Publishing type：Research paper (other academic)  

  • O(n log n)-time text compression by LZ-style longest first substitution

    Akihiro Nishi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

    22nd Prague Stringology Conference, PSC 2018 Proceedings of the Prague Stringology Conference, PSC 2018   12 - 26   2018.8

    　More details

    Language：English   Publishing type：Research paper (other academic)  

  • Faster online elastic degenerate string matching

    Kotaro Aoyama, Yuto Nakashima, I. Tomohiro, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

    29th Annual Symposium on Combinatorial Pattern Matching, CPM 2018 29th Annual Symposium on Combinatorial Pattern Matching, CPM 2018   91 - 910   2018.5

    　More details

    Language：English   Publishing type：Research paper (other academic)  

    DOI： 10.4230/LIPIcs.CPM.2018.9

  • Lyndon factorization of grammar compressed texts revisited

    Isamu Furuya, Yuto Nakashima, I. Tomohiro, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

    29th Annual Symposium on Combinatorial Pattern Matching, CPM 2018 29th Annual Symposium on Combinatorial Pattern Matching, CPM 2018   241 - 2410   2018.5

    　More details

    Language：English   Publishing type：Research paper (other academic)  

    DOI： 10.4230/LIPIcs.CPM.2018.24

  • Longest substring palindrome after edit

    Mitsuru Funakoshi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

    29th Annual Symposium on Combinatorial Pattern Matching, CPM 2018 29th Annual Symposium on Combinatorial Pattern Matching, CPM 2018   105   121 - 1214   2018.5

    　More details

    Language：English   Publishing type：Research paper (other academic)  

    DOI： 10.4230/LIPIcs.CPM.2018.12

  • Longest lyndon substring after edit

    Yuki Urabe, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

    29th Annual Symposium on Combinatorial Pattern Matching, CPM 2018 29th Annual Symposium on Combinatorial Pattern Matching, CPM 2018   191 - 1910   2018.5

    　More details

    Language：English   Publishing type：Research paper (other academic)  

    DOI： 10.4230/LIPIcs.CPM.2018.19

  • Shortest unique palindromic substring queries in optimal time

    Yuto Nakashima, Hiroe Inoue, Takuya Mieno, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

    28th International Workshop on Combinational Algorithms, IWOCA 2017 Combinatorial Algorithms - 28th International Workshop, IWOCA 2017, Revised Selected Papers   397 - 408   2018.1

    　More details

    Language：English   Publishing type：Research paper (other academic)  

    DOI： 10.1007/978-3-319-78825-8_32

  • Almost linear time computation of maximal repetitions in run length encoded strings

    Yuta Fujishige, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

    28th International Symposium on Algorithms and Computation, ISAAC 2017 28th International Symposium on Algorithms and Computation, ISAAC 2017   2017.12

    　More details

    Language：English   Publishing type：Research paper (other academic)  

    DOI： 10.4230/LIPIcs.ISAAC.2017.33

  • The "runs" theorem Reviewed

    Hideo Bannai, Tomohiro I, Shunsuke Inenaga, Yuto Nakashima, Masayuki Takeda, Kazuya Tsuruta

    SIAM Journal on Computing   46 ( 5 )   1501 - 1514   2017.9

    　More details

    Language：English   Publishing type：Research paper (scientific journal)  

    DOI： 10.1137/15M1011032

  • On reverse engineering the Lyndon tree

    Yuto Nakashima, Takuya Takagi, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

    21st Prague Stringology Conference, PSC 2017 Proceedings of the Prague Stringology Conference, PSC 2017   108 - 117   2017.8

    　More details

    Language：English   Publishing type：Research paper (other academic)  

  • Inferring strings from Lyndon factorization Reviewed

    Yuto Nakashima, Takashi Okabe, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

    Theoretical Computer Science   689   147 - 156   2017.8

    　More details

    Language：English   Publishing type：Research paper (scientific journal)  

    DOI： 10.1016/j.tcs.2017.05.038

  • On the size of Lempel-Ziv and Lyndon factorizations

    34th Symposium on Theoretical Aspects of Computer Science, STACS 2017 34th Symposium on Theoretical Aspects of Computer Science, STACS 2017   2017.3

    　More details

    Language：English   Publishing type：Research paper (other academic)  

    DOI： 10.4230/LIPIcs.STACS.2017.45

  • Faster Lyndon factorization algorithms for SLP and LZ78 compressed text Reviewed

    Tomohiro I, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

    Theoretical Computer Science   656   215 - 224   2016.12

    　More details

    Language：English   Publishing type：Research paper (scientific journal)  

    DOI： 10.1016/j.tcs.2016.03.005

  • Longest common Abelian factors and large alphabets

    Golnaz Badkobeh, Travis Gagie, Szymon Grabowski, Yuto Nakashima, Simon J. Puglisi, Shiho Sugimoto

    23rd International Symposium on String Processing and Information Retrieval, SPIRE 2016 String Processing and Information Retrieval - 23rd International Symposium, SPIRE 2016, Proceedings   254 - 259   2016.10

    　More details

    Language：English   Publishing type：Research paper (other academic)  

    DOI： 10.1007/978-3-319-46049-9_24

  • Computing smallest and largest repetition factorizations in O(n log n) time

    Hiroe Inoue, Yoshiaki Matsuoka, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

    20th Prague Stringology Conference, PSC 2016 Proceedings of the Prague Stringology Conference, PSC 2016   135 - 145   2016.8

    　More details

    Language：English   Publishing type：Research paper (other academic)  

  • Constructing LZ78 tries and position heaps in linear time for large alphabets Reviewed

    Yuto Nakashima, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

    Information Processing Letters   115 ( 9 )   655 - 659   2015.9

    　More details

    Language：English   Publishing type：Research paper (scientific journal)  

    DOI： 10.1016/j.ipl.2015.04.002

  • A new characterization of maximal repetitions by Lyndon trees

    Hideo Bannai, Tomohiro I, Shunsuke Inenaga, Yuto Nakashima, Masayuki Takeda, Kazuya Tsuruta

    26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015 Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015   562 - 571   2015.1

    　More details

    Language：English   Publishing type：Research paper (other academic)  

    DOI： 10.1137/1.9781611973730.38

  • Computing left-right maximal generic words

    Takaaki Nishimoto, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

    19th Prague Stringology Conference, PSC 2015 Proceedings of the Prague Stringology Conference 2015, PSC 2015   5 - 16   2015.1

    　More details

    Language：English   Publishing type：Research paper (other academic)  

  • Inferring strings from Lyndon factorization

    Yuto Nakashima, Takashi Okabe, I. Tomohiro, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

    39th International Symposium on Mathematical Foundations of Computer Science, MFCS 2014 Mathematical Foundations of Computer Science 2014 - 39th International Symposium, MFCS 2014, Proceedings   565 - 576   2014.1

    　More details

    Language：English   Publishing type：Research paper (other academic)  

    DOI： 10.1007/978-3-662-44465-8_48

  • Faster lyndon factorization algorithms for SLP and LZ78 compressed text

    Tomohiro I, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

    20th International Symposium on String Processing and Information Retrieval, SPIRE 2013 String Processing and Information Retrieval - 20th International Symposium, SPIRE 2013, Proceedings   174 - 185   2013.10

    　More details

    Language：English   Publishing type：Research paper (other academic)  

    DOI： 10.1007/978-3-319-02432-5_21

  • Efficient Lyndon factorization of grammar compressed text

    Tomohiro I, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

    24th Annual Symposium on Combinatorial Pattern Matching, CPM 2013 Combinatorial Pattern Matching - 24th Annual Symposium, CPM 2013, Proceedings   153 - 164   2013.1

    　More details

    Language：English   Publishing type：Research paper (other academic)  

    DOI： 10.1007/978-3-642-38905-4_16

  • The position heap of a trie

    Yuto Nakashima, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

    19th International Symposium on String Processing and Information Retrieval, SPIRE 2012 String Processing and Information Retrieval - 19th International Symposium, SPIRE 2012, Proceedings   360 - 371   2012.10

    　More details

    Language：English   Publishing type：Research paper (other academic)  

    DOI： 10.1007/978-3-642-34109-0-38

▼display all

Presentations

  • Optimal LZ-End Parsing Is Hard International conference

    Hideo Bannai, Mitsuru Funakoshi, Kazuhiro Kurita, Yuto Nakashima, Kazuhisa Seto, Takeaki Uno

    34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)  2023.6 

    　More details

    Event date： 2023.6

    Language：English   Presentation type：Oral presentation (general)  

    Country：France  

  • Space-Efficient STR-IC-LCS Computation International conference

    Yuuki Yonemoto, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai

    48th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2023)  2023.1 

    　More details

    Event date： 2023.1 - 2020.1

    Language：English  

    Country：Slovakia  

  • Minimal Absent Words on Run-Length Encoded Strings International conference

    Tooru Akagi, Kouta Okabe, Takuya Mieno, Yuto Nakashima, Shunsuke Inenaga

    33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022)  2022.6 

    　More details

    Event date： 2022.6

    Language：English   Presentation type：Oral presentation (general)  

    Country：Czech Republic  

  • Longest Common Rollercoasters International conference

    Kosuke Fujita, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

    28th International Symposium on String Processing and Information Retrieval (SPIRE 2021)  2021.10 

    　More details

    Event date： 2021.10

    Language：English  

    Country：France  

  • On the approximation ratio of LZ-End to LZ77 International conference

    Takumi Ideue, Takuya Mieno, Mitsuru Funakoshi, Yuto Nakashima, Shunsuke Inenaga, Masayuki Takeda

    28th International Symposium on String Processing and Information Retrieval (SPIRE 2021)  2021.10 

    　More details

    Event date： 2021.10

    Language：English  

    Country：France  

  • Position Heaps for Cartesian-tree Matching on Strings and Tries International conference

    Akio Nishimoto, Noriki. Fujisato, Yuto Nakashima, Shunsuke Inenaga

    28th International Symposium on String Processing and Information Retrieval (SPIRE 2021)  2021.10 

    　More details

    Event date： 2021.10

    Language：English  

    Country：France  

  • Grammar Index By Induced Suffix Sorting International conference

    28th International Symposium on String Processing and Information Retrieval (SPIRE 2021)  2021.10 

    　More details

    Event date： 2021.10

    Language：English  

    Country：France  

  • Counting Lyndon Subsequence International conference

    Ryo Hirakawa, Yuto Nakashima, Shunsuke Inenaga, Masayuki Takeda

    Prague Stringology Conference 2021 (PSC 2021)  2021.8 

    　More details

    Event date： 2021.8

    Language：English  

    Country：Czech Republic  

  • The Parameterized Suffix Tray International conference

    Noriki Fujisato, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda

    12th International Conference on Algorithms and Complexity (CIAC 2021)  2021.5 

    　More details

    Event date： 2021.5

    Language：English  

    Country：Cyprus  

  • On repetitiveness measures of Thue-Morse words International conference

    Kanaru Kutsukake, Takuya Matsumoto, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

    27th International Symposium on String Processing and Information Retrieval (SPIRE 2020)  2020.10 

    　More details

    Event date： 2020.10

    Language：English  

    Country：United States  

  • Lyndon Words, the Three Squares Lemma, and Primitive Squares International conference

    Hideo Bannai, Takuya Mieno, Yuto Nakashima

    27th International Symposium on String Processing and Information Retrieval (SPIRE 2020)  2020.10 

    　More details

    Event date： 2020.10

    Language：English   Presentation type：Oral presentation (general)  

    Country：United States  

  • Towards Efficient Interactive Computation of Dynamic Time Warping Distance International conference

    Akihiro Nishi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

    27th International Symposium on String Processing and Information Retrieval (SPIRE 2020)  2020.10 

    　More details

    Event date： 2020.10

    Language：English  

    Country：United States  

  • DAWGs for Parameterized Matching: Online Construction and Related Indexing Structures International conference

    Katsuhito Nakashima, Noriki Fujisato, Diptarama Hendrian, Yuto Nakashima, Ryo Yoshinaka, Shunsuke Inenaga, Hideo Bannai, Ayumi Shinohara, Masayuki Takeda

    31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020)  2020.6 

    　More details

    Event date： 2020.6

    Language：English   Presentation type：Oral presentation (general)  

    Country：Denmark  

  • Detecting k-(Sub-)Cadences and Equidistant Subsequence Occurrences International conference

    Mitsuru Funakoshi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Ayumi Shinohara

    31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020)  2020.6 

    　More details

    Event date： 2020.6

    Language：English   Presentation type：Oral presentation (general)  

    Country：Denmark  

  • c-Trie++: A Dynamic Trie Tailored for Fast Prefix Searches International conference

    Data Compression Conference 2020  2020.3 

    　More details

    Event date： 2020.3

    Language：English  

    Country：Other  

  • Faster STR-EC-LCS Computation International conference

    Kohei Yamada, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

    46th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2020  2020.1 

    　More details

    Event date： 2020.1

    Language：English  

    Country：Cyprus  

  • Minimal Unique Substrings and Minimal Absent Words in a Sliding Window International conference

    Takuya Mieno, Yuki Kuhara, Tooru Akagi, Yuta Fujishige, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

    46th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2020  2020.1 

    　More details

    Event date： 2020.1

    Language：English  

    Country：Cyprus  

  • An improved data structure for left-right maximal generic words problem International conference

    Yuta Fujishige, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

    30th International Symposium on Algorithms and Computation, ISAAC 2019  2019.12 

    　More details

    Event date： 2019.12

    Language：English  

    Country：China  

  • Compact Data Structures for Shortest Unique Substring Queries International conference

    26th International Symposium on String Processing and Information Retrieval, SPIRE 2019  2019.10 

    　More details

    Event date： 2019.10

    Language：English  

    Country：Spain  

  • On Longest Common Property Preserved Substring Queries International conference

    Kazuki Kai, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Tomasz Kociumaka

    26th International Symposium on String Processing and Information Retrieval, SPIRE 2019  2019.10 

    　More details

    Event date： 2019.10

    Language：English  

    Country：Spain  

  • Direct Linear Time Construction of Parameterized Suffix and LCP Arrays for Constant Alphabets International conference

    Noriki Fujisato, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

    26th International Symposium on String Processing and Information Retrieval, SPIRE 2019  2019.10 

    　More details

    Event date： 2019.10

    Language：English  

    Country：Spain  

  • Computing Maximal Palindromes and Distinct Palindromes in a Trie International conference

    Mitsuru Funakoshi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

    Prague Stringology Conference 2019  2019.8 

    　More details

    Event date： 2019.8

    Language：English  

    Country：Czech Republic  

  • Shortest unique palindromic substring queries on run-length encoded strings International conference

    Kiichi Watanabe, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

    30th International Workshop on Combinatorial Algorithms, IWOCA 2019  2019.7 

    　More details

    Event date： 2019.7

    Language：English  

    Country：Italy  

  • Computing runs on a trie International conference

    Ryo Sugahara, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

    30th Annual Symposium on Combinatorial Pattern Matching, CPM 2019  2019.6 

    　More details

    Event date： 2019.6

    Language：English  

    Country：Italy  

  • On the size of overlapping Lempel-Ziv and Lyndon factorizations International conference

    Yuki Urabe, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

    30th Annual Symposium on Combinatorial Pattern Matching, CPM 2019  2019.6 

    　More details

    Event date： 2019.6

    Language：English  

    Country：Italy  

  • Faster queries for longest substring palindrome after block edit International conference

    Mitsuru Funakoshi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

    30th Annual Symposium on Combinatorial Pattern Matching, CPM 2019  2019.6 

    　More details

    Event date： 2019.6

    Language：English  

    Country：Italy  

  • The Parameterized Position Heap of a Trie International conference

    Noriki Fujisato, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

    11th International Conference on Algorithms and Complexity, CIAC 2019  2019.5 

    　More details

    Event date： 2019.5

    Language：English  

    Country：Italy  

  • MR-RePair Grammar Compression Based on Maximal Repeats

    Isamu Furuya, Takuya Takagi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Takuya Kida

    2019 Data Compression Conference, DCC 2019  2019.3 

    　More details

    Event date： 2019.3

    Language：English  

    Country：United States  

  • Recovering, counting and enumerating strings from forward and backward suffix arrays International conference

    Yuki Kuhara, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

    25th International Symposium on String Processing and Information Retrieval, SPIRE 2018  2018.10 

    　More details

    Event date： 2018.10

    Language：English  

    Country：Peru  

  • Right-to-left online construction of parameterized position heaps International conference

    Noriki Fujisato, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda.

    Prague Stringology Conference 2018  2018.8 

    　More details

    Event date： 2018.8

    Language：English   Presentation type：Oral presentation (general)  

    Country：Czech Republic  

  • O(n log n)-time text compression by LZ-style longest first substitution International conference

    Akihiro Nishi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda.

    Prague Stringology Conference 2018  2018.8 

    　More details

    Event date： 2018.8

    Language：English   Presentation type：Oral presentation (general)  

    Country：Czech Republic  

  • Faster online elastic degenerate string matching

    Kotaro Aoyama, Yuto Nakashima, I. Tomohiro, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

    29th Annual Symposium on Combinatorial Pattern Matching, CPM 2018  2018.7 

    　More details

    Event date： 2018.7

    Language：English  

    Country：China  

  • Longest substring palindrome after edit

    Mitsuru Funakoshi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

    29th Annual Symposium on Combinatorial Pattern Matching, CPM 2018  2018.7 

    　More details

    Event date： 2018.7

    Language：English  

    Country：China  

  • Longest lyndon substring after edit

    Yuki Urabe, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

    29th Annual Symposium on Combinatorial Pattern Matching, CPM 2018  2018.7 

    　More details

    Event date： 2018.7

    Language：English  

    Country：China  

  • Lyndon 文字列とテキスト圧縮 Invited

    中島祐人

    2018年電子情報通信学会総合大会  2018.3 

    　More details

    Event date： 2018.6

    Language：Japanese   Presentation type：Oral presentation (general)  

    Venue：東京電機大学（東京）   Country：Japan  

  • ストリーミングモデルにおける最長Lyndon文字列

    中島祐人

    冬のLAシンポジウム2017  2018.2 

    　More details

    Event date： 2018.6

    Language：Japanese   Presentation type：Oral presentation (general)  

    Venue：京都大学（京都市）   Country：Japan  

  • Almost linear time computation of maximal repetitions in run length encoded strings International conference

    Yuta Fujishige, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

    The 28th International Symposium on Algorithms and Computation (ISAAC 2017)  2017.12 

    　More details

    Event date： 2017.12

    Language：English   Presentation type：Oral presentation (general)  

    Country：Thailand  

  • On Reverse Engineering the Lyndon Tree International conference

    Yuto Nakashima, Takuya Takagi, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

    The Prague Stringology Conference 2017 (PSC 2017)  2017.8 

    　More details

    Event date： 2017.8

    Language：English   Presentation type：Oral presentation (general)  

    Country：Czech Republic  

  • Almost linear time computation of maximal repetitions in run length encoded strings International conference

    Yuta Fujishige, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

    12th Workshop on Compression, Text and Algorithms  2017.9 

    　More details

    Event date： 2017.6

    Language：English   Presentation type：Oral presentation (general)  

    Country：Italy  

  • On Sensitivity of Compact Directed Acyclic Word Graphs International conference

    Hiroto Fujimaru, Yuto Nakashima, Shunsuke Inenaga

    14th International Conference on Words (WORDS 2023)  2023.6 

    　More details

    Language：English   Presentation type：Oral presentation (general)  

    Country：Sweden  

  • Computing SEQ-IC-LCS of Labeled Graphs International conference

    Yuki Yonemoto, Yuto Nakashima, Shunsuke Inenaga

    Prague Stringology Conference 2023 (PSC 2023)  2023.8 

    　More details

    Language：English  

    Country：Czech Republic  

  • Optimally Computing Compressed Indexing Arrays Based on the Compact Directed Acyclic Word Graph International conference

    Hiroki Arimura, Shunsuke Inenaga, Yasuaki Kobayashi, Yuto Nakashima, Mizuki Sue

    30th International Symposium on String Processing and Information Retrieval (SPIRE 2023)  2023.9 

    　More details

    Language：English  

    Country：Czech Republic  

  • Largest Repetition Factorization of Fibonacci Words International conference

    Kaisei Kishi, Yuto Nakashima, Shunsuke Inenaga

    30th International Symposium on String Processing and Information Retrieval (SPIRE 2023)  2023.9 

    　More details

    Language：English  

    Country：Czech Republic  

  • Linear-Time Computation of Generalized Minimal Absent Words for Multiple Strings International conference

    Kouta Okabe, Takuya Mieno, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai

    30th International Symposium on String Processing and Information Retrieval (SPIRE 2023)  2023.9 

    　More details

    Language：English  

    Country：Czech Republic  

▼display all

Committee Memberships

  • 情報処理学会 アルゴリズム研究運営委員会   幹事  

    2024.4 - Present   

    　 More details

  • EATCS Japan Chapter   Organizer   Foreign country

    2023.1 - Present   

  • EATCS Japan Chapter   Secretary  

    2023.1 - Present   

    　 More details

  • 電子情報通信学会 情報・システムソサイエティ誌 編集委員会   編集委員  

    2022.6 - Present   

    　 More details

  • 情報処理学会   アルゴリズム研究会運営委員   Domestic

    2022.6 - 2026.6   

  • 情報処理学会 アルゴリズム研究運営委員会   運営委員  

    2022.4 - 2024.3   

    　 More details

  • 電子情報通信学会 コンピュテーション研究専門委員会   専門委員  

    2020.6 - Present   

    　 More details

  • 電子情報通信学会   コンピュテーション研究会 専門委員   Domestic

    2020.6 - 2022.5   

▼display all

Academic Activities

  • 組織委員長 International contribution

    （ 福岡 ） 2024.6

    　More details

    Type：Competition, symposium, etc. 

  • PC memer International contribution

    34th Annual Symposium on Combinatorial Pattern Matching  （ France ） 2023.6

    　More details

    Type：Competition, symposium, etc. 

  • Screening of academic papers

    Role(s)： Peer review

    2023

    　More details

    Type：Peer review 

    Proceedings of International Conference Number of peer-reviewed papers：8

  • 運営委員

    STRセミナー2022　若手研究者のための大学間合同研究集会  （ 神戸市 ） 2022.9

    　More details

    Type：Competition, symposium, etc. 

  • 電子情報通信学会　情報・システムソサイエティ誌

    2022.6 - 2024.6

    　More details

    Type：Academic society, research group, etc. 

  • Screening of academic papers

    Role(s)： Peer review

    2022

    　More details

    Type：Peer review 

    Number of peer-reviewed articles in foreign language journals：3

    Proceedings of International Conference Number of peer-reviewed papers：7

  • Screening of academic papers

    Role(s)： Peer review

    2021

    　More details

    Type：Peer review 

    Number of peer-reviewed articles in foreign language journals：2

    Proceedings of International Conference Number of peer-reviewed papers：4

  • 座長

    冬のLAシンポジウム2019  （ 京都大学数理解析研究所（京都府京都市） ） 2020.2

    　More details

    Type：Competition, symposium, etc. 

  • Screening of academic papers

    Role(s)： Peer review

    2020

    　More details

    Type：Peer review 

    Number of peer-reviewed articles in foreign language journals：4

    Proceedings of International Conference Number of peer-reviewed papers：4

  • 座長

    コンピュテーション研究会  （ 北海道大学札幌キャンパス（北海道札幌市） ） 2019.10

    　More details

    Type：Competition, symposium, etc. 

  • コメンテータ

    第11回データ工学と情報マネジメントに関するフォーラム  （ ホテルオークラJRハウステンボス（長崎県佐世保市） ） 2019.3

    　More details

    Type：Competition, symposium, etc. 

  • Screening of academic papers

    Role(s)： Peer review

    2019

    　More details

    Type：Peer review 

    Number of peer-reviewed articles in foreign language journals：0

    Number of peer-reviewed articles in Japanese journals：0

    Proceedings of International Conference Number of peer-reviewed papers：6

    Proceedings of domestic conference Number of peer-reviewed papers：0

  • 座長

    夏のLAシンポジウム2018  （ サンライズ九十九里（千葉県山武郡） ） 2018.7

    　More details

    Type：Competition, symposium, etc. 

  • 座長

    2018年電子情報通信学会総合大会  （ 東京電機大学（東京） ） 2018.3

    　More details

    Type：Competition, symposium, etc. 

  • 座長

    アルゴリズム研究会（167回）  （ サンポートホール高松（香川県高松市） ） 2018.3

    　More details

    Type：Competition, symposium, etc. 

  • 座長

    冬のLAシンポジウム2017  （ 京都大学（京都市） ） 2018.2

    　More details

    Type：Competition, symposium, etc. 

  • Screening of academic papers

    Role(s)： Peer review

    2018

    　More details

    Type：Peer review 

    Number of peer-reviewed articles in foreign language journals：4

    Number of peer-reviewed articles in Japanese journals：0

    Proceedings of International Conference Number of peer-reviewed papers：3

    Proceedings of domestic conference Number of peer-reviewed papers：0

  • Screening of academic papers

    Role(s)： Peer review

    2017

    　More details

    Type：Peer review 

    Number of peer-reviewed articles in foreign language journals：1

    Number of peer-reviewed articles in Japanese journals：0

    Proceedings of International Conference Number of peer-reviewed papers：2

    Proceedings of domestic conference Number of peer-reviewed papers：0

▼display all

Research Projects

  • 辞書式順序依存問題の複雑さの解明

    Grant number：23H04386  2023 - 2024

    日本学術振興会・文部科学省  科学研究費助成事業  学術変革領域研究(A)

    中島 祐人

    　 More details

    Authorship：Principal investigator  Grant type：Scientific research funding

    効率的な文字列アルゴリズムの開発には，文字列が持つ数理的性質の理解が重要である.文字列の特徴を捉える際に利用される構造や性質は，辞書式順序依存な構造と辞書式順序非依存な構造に大別される.辞書式順序依存な構造におけるこれまでの研究では，暗に与えられた辞書式順序のみを考えているに過ぎなかった.本研究では辞書式順序に依存する問題に着目し，組合せ論・計算量理論・アルゴリズム論の三方向から，辞書式順序が与える文字列構造への影響を解明する．

    CiNii Research

  • 広義文字列のアルゴリズムと組合せ論

    Grant number：23K24808  2022.4 - 2026.3

    科学研究費助成事業  基盤研究(B)

    稲永 俊介, 坂内 英夫, 中島 祐人, Koeppl Dominik

    　 More details

    Grant type：Scientific research funding

    文字列とは，文字あるいは記号の一本鎖列である．自然言語テキスト，サーバログ，DNA配列など，計算機処理可能な様々なデータを文字列と見なすことができる．1970年代から半世紀にわたって，検索・圧縮・比較・解析・発見などの重要タスクを文字列データ上で高速実行するアルゴリズムが多数提案されてきた．本提案課題では，文字列の定義域を拡張した「広義文字列」という新概念を提唱し，木型文字列／グラフ型文字列／２次元文字列／時系列の高速処理アルゴリズム開発と，それを支える組合せ論的性質の解明に取り組む．

    CiNii Research

  • 広義文字列のアルゴリズムと組合せ論

    Grant number：22H03551  2022 - 2025

    日本学術振興会  科学研究費助成事業  基盤研究(B)

    　 More details

    Authorship：Coinvestigator(s)  Grant type：Scientific research funding

  • Lyndon文字列による反復性指標解析

    Grant number：21K17705  2021 - 2024

    日本学術振興会  科学研究費助成事業  若手研究

    中島 祐人

    　 More details

    Authorship：Principal investigator  Grant type：Scientific research funding

    文字列データを対象としたデータ圧縮においては，辞書式圧縮と呼ばれる様々な手法が知られている．一般に，部分文字列の反復(繰り返し)が多いほど，文字列は圧縮されやすい傾向にあるため，LZ 分解などの文字列構造のサイズは，文字列の反復性を捉えた反復性指標と見なすことができる．最近では，String attractor や部分文字列複雑性に基づいた反復性指標が提案され，反復性への理解が進められているが，本申請課題では，辞書式圧縮とは直接関係のない Lyndon 文字列および関連する文字列構造を導入することで，新たな視点から反復性指標の解析を行い，その本質を明らかにする．

    CiNii Research

  • 辞書式順序に基づいた文字列データ処理法の構築

    2020 - 2022

    戦略的創造研究推進事業 (文部科学省)

    　 More details

    Authorship：Principal investigator  Grant type：Contract research

  • 情報爆縮に基づくIoTデータ処理基盤の構築

    Grant number：18H04098  2018 - 2022

    日本学術振興会  科学研究費助成事業  基盤研究(A)

    竹田 正幸, 定兼 邦彦, 坂内 英夫, 井 智弘, 瀧本 英二, 坂本 比呂志, 畑埜 晃平, 稲永 俊介, 喜田 拓也, 中島 祐人

    　 More details

    Authorship：Coinvestigator(s)  Grant type：Scientific research funding

    IoT時代が到来し, 製造・産業界, モビリティ・交通インフラ, 医療・ヘルスケアなど, 広範な分野において技術革新が生み出され新たな価値が創出されると期待されている. 一方, IoTデータの急増に伴い, クラウドサーバへのデータ処理の集中, ネットワーク回線の逼迫, データ送信の遅延などの技術的問題が深刻化している. 現在のIoTに対する取り組みは実証フェーズのものが多くIoTを用いた価値創出に重点が置かれているため, 上記の問題の抜本的な解決は後回しとなっている. 代表者らは, これまでに, 入力データや計算に用いるデータ構造に潜む冗長性の除去に基づいて計算そのものの効率化を図る「情報爆縮」の研究を行ってきた. 本研究プロジェクトでは, この情報爆縮技術を核に据え, 理論と実用的の両面から, エッジ側とクラウド側の処理を効率化する技術を開発し低コストでデータを収集・集約・送信・蓄積・検索・解析できる新しいIoTデータ処理基盤の構築を目指す.
    このために, 以下の3つの研究項目をおいて研究を行った.
    (A) 圧縮データストリームに対するリアルタイム抽出・集計技術.
    (B) 圧縮データに対する高速質問処理技術.
    (C) 解釈可能な圧縮データ錬成技術.
    前年度に引き続き, 特に(A), (B)に力点を置いて研究を行い、(A)スライド窓における極小ユニーク文字列の列挙・回文木の構築/維持のアルゴリズム、(B)接尾辞配列構築アルゴリズムを基にした高速な圧縮索引構造の提案等、多くの研究成果を得た.

    CiNii Research

  • Lyndon文字列による簡潔で高速な文字列処理アルゴリズム

    Grant number：18K18002  2018 - 2020

    日本学術振興会  科学研究費助成事業  若手研究

    中島 祐人

    　 More details

    Authorship：Principal investigator  Grant type：Scientific research funding

    本研究の目的は，Lyndon文字列の性質に基づいて，簡潔で高速な文字列処理アルゴリズムを開発することである．
    本目的の達成のために，Lyndon文字列を中心に，繰り返し構造や回文構造など広く文字列処理アルゴリズムや文字列組合せ論の問題に取り組んだ．Lyndon文字列を中心に，様々な文字列構造の性質の理解や，それらの性質を利用した効率的なアルゴリズムを提案した．

    CiNii Research

  • 情報爆縮基盤技術

    Grant number：25240003  2017

    日本学術振興会  科学研究費助成事業  基盤研究(A)

    　 More details

    Authorship：Coinvestigator(s)  Grant type：Scientific research funding

  • ストリーミングモデルにおける文字列処理アルゴリズム基盤

    Grant number：17H06923  2017

    日本学術振興会  科学研究費助成事業  研究活動スタート支援

    　 More details

    Authorship：Principal investigator  Grant type：Scientific research funding

▼display all

Class subject

  • 情報科学

    2024.10 - 2025.3   Second semester

  • 情報代数学演習

    2024.4 - 2024.9   First semester

  • 形式言語理論演習

    2024.4 - 2024.9   First semester

  • 形式言語理論演習

    2023.4 - 2023.9   First semester

  • 情報代数学演習

    2023.4 - 2023.9   First semester

  • 情報代数学演習

    2022.4 - 2022.9   First semester

  • 情報論理学演習

    2022.4 - 2022.9   First semester

  • 形式言語理論演習

    2022.4 - 2022.9   First semester

  • 情報論理学演習

    2021.4 - 2021.9   First semester

  • 情報代数学演習

    2021.4 - 2021.9   First semester

  • 形式言語理論演習

    2021.4 - 2021.9   First semester

  • 形式言語理論演習

    2020.4 - 2020.9   First semester

  • 情報代数学演習

    2020.4 - 2020.9   First semester

  • 情報論理学演習

    2020.4 - 2020.9   First semester

  • 形式言語理論演習

    2019.4 - 2019.9   First semester

  • 情報代数学演習

    2019.4 - 2019.9   First semester

  • 情報論理学演習

    2019.4 - 2019.9   First semester

  • 情報科学

    2018.10 - 2019.3   Second semester

  • 形式言語理論演習

    2018.4 - 2018.9   First semester

  • 情報代数学演習

    2018.4 - 2018.9   First semester

  • 情報論理学演習

    2018.4 - 2018.9   First semester

  • 情報論理学演習

    2017.4 - 2017.9   First semester

  • 形式言語理論演習

    2017.4 - 2017.9   First semester

  • 情報代数学演習

    2017.4 - 2017.9   First semester

▼display all

FD Participation

  • 2024.3   Role：Participation   Title：【シス情FD】高度データサイエンティスト育成事業の取り組みについて

    Organizer：[Undergraduate school/graduate school/graduate faculty]

  • 2023.10   Role：Participation   Title：【シス情FD】価値創造型半導体人材育成センターについて

    Organizer：[Undergraduate school/graduate school/graduate faculty]

  • 2023.4   Role：Speech   Title：【シス情FD】若手教員による研究紹介⑧

    Organizer：[Undergraduate school/graduate school/graduate faculty]

  • 2022.5   Role：Participation   Title：【シス情FD】若手教員による研究紹介④「量子コンピュータ・システム・アーキテクチャの研究～道具になることを目指して～」

    Organizer：[Undergraduate school/graduate school/graduate faculty]

  • 2022.4   Role：Participation   Title：【シス情FD】第4期中期目標・中期計画等について

    Organizer：[Undergraduate school/graduate school/graduate faculty]

  • 2022.1   Role：Participation   Title：【シス情FD】シス情関連の科学技術に対する国の政策動向（に関する私見）

    Organizer：[Undergraduate school/graduate school/graduate faculty]

  • 2021.10   Role：Participation   Title：【シス情FD】熊本高専と九大システム情報との交流・連携に向けて ー 3年半で感じた高専の実像 ー

    Organizer：[Undergraduate school/graduate school/graduate faculty]

  • 2021.7   Role：Participation   Title：若手教員による研究紹介　及び　科研取得のポイント、その他について　②

    Organizer：[Undergraduate school/graduate school/graduate faculty]

  • 2021.6   Role：Participation   Title：若手教員による研究紹介　及び　科研取得のポイントについて　①

    Organizer：[Undergraduate school/graduate school/graduate faculty]

  • 2020.11   Role：Participation   Title：マス・フォア・イノベーション卓越大学院について

    Organizer：[Undergraduate school/graduate school/graduate faculty]

  • 2020.4   Role：Participation   Title：新型コロナウイルスが誘起した社会変化に対するシステム情報科学からの提言

    Organizer：[Undergraduate school/graduate school/graduate faculty]

  • 2018.7   Role：Participation   Title：論文剽窃ソフトの活用方法について

    Organizer：[Undergraduate school/graduate school/graduate faculty]

▼display all