九州大学 研究者情報
研究者情報 (研究者の方へ)入力に際してお困りですか?
基本情報 研究活動 教育活動 社会活動
稲永 俊介(いねなが しゆんすけ) データ更新日:2019.06.24

准教授 /  システム情報科学研究院 情報学部門 数理情報


主な研究テーマ
文字列処理アルゴリズムとその応用
キーワード:組み合わせパターン照合, パターン発見, テキスト圧縮
2000.04~2021.03.
従事しているプロジェクト研究
Text compression and compressed data structures on texts (JSPS summer program)
2016.07~2017.08, 代表者:Dominik Koppl, TU Dortmund.
圧縮データマイニング処理基盤技術の研究
2011.07~2015.03, 代表者:竹田正幸, 九州大学, 九州大学
圧縮データから知識や規則を半自動的に抽出する技術に関する研究開発を行う..
圧縮データマイニング処理基盤技術の研究
2011.07~2014.03, 代表者:竹田正幸, 九州大学, 九州大学
圧縮データから知識や規則を半自動的に抽出する技術に関する研究開発を行う..
研究業績
主要著書
1. Shunsuke Inenaga, Kunihiko Sadakane, Tetsuya Sakai, String Processing and Information Retrieval (SPIRE 2016), Springer, LNCS 9954, 2016.10.
2. Adrian Horia Dediu, Shunsuke Inenaga, Carlos Martín-Vide, Special issue of Language and Automata Theory and Applications 2011 (LATA 2011), International Journal of Computer Mathematics (Taylor & Francis), 2013.06.
3. Adrian Horia Dediu, Shunsuke Inenaga, Carlos Martín-Vide, Language and Automata Theory and Applications 2011 (LATA 2011), Springer, LNCS 6638, 2011.05.
主要原著論文
1. Isamu Furuya, Takuya Takagi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai and Takuya Kida, MR-RePair: Grammar Compression based on Maximal Repeats, Data Compression Conference 2019 (DCC 2019), 2019.03.
2. Yuki Kuhara, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, Recovering, Counting and Enumerating Strings from Forward and Backward Suffix Arrays, 25th International Symposium on String Processing and Information Retrieval (SPIRE 2018), 2018.10.
3. Keisuke Goto, Tomohiro I, Hideo Bannai and Shunsuke Inenaga, Block Palindromes: A New Generalization of Palindromes, 25th International Symposium on String Processing and Information Retrieval (SPIRE 2018), 2018.10.
4. Noriki Fujisato, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, Right-to-left Online Construction of Parameterized Position Heaps, Prague Stringology Conference 2018 (PSC 2018), 2018.08.
5. Akihiro Nishi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, O(n log n)-time Text Compression by LZ-style Longest First Substitution, Prague Stringology Conference 2018 (PSC 2018), 2018.08.
6. Isamu Furuya, Yuto Nakashima, Tomohiro I, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda, Lyndon Factorization of Grammar Compressed Texts Revisited, Proc. the 29th Annual Symposium on Combinatorial Pattern Matching (CPM 2018), 2018.07.
7. Yuki Urabe, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, Longest Lyndon Substring After Edit, Proc. the 29th Annual Symposium on Combinatorial Pattern Matching (CPM 2018), 2018.07.
8. Takafumi Inoue, Shunsuke Inenaga, Heikki Hyyrö, Hideo Bannai, and Masayuki Takeda, Computing longest common square subsequences, Proc. the 29th Annual Symposium on Combinatorial Pattern Matching (CPM 2018), 2018.07.
9. Mitsuru Funakoshi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, Longest substring palindrome after edit, Proc. the 29th Annual Symposium on Combinatorial Pattern Matching (CPM 2018), 2018.07.
10. Kotaro Aoyama, Yuto Nakashima, Tomohiro I, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda, Faster Online Elastic Degenerate String Matching, Proc. the 29th Annual Symposium on Combinatorial Pattern Matching (CPM 2018), 2018.07.
11. Hideo Bannai, Travis Gagie, Shunsuke Inenaga, Juha Kärkkäinen, Dominik Kempa, Marcin Piatkowski, Simon J. Puglisi, Shiho Sugimoto, Diverse Palindromic Factorization is NP-Complete, Journal of Foundations of Computer Science, http://dx.doi.org/10.1142/S0129054118400014, 143-163, 29(2):143-163, 2018.02.
12. Takaaki Nishimoto, I. Tomohiro, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Dynamic index and LZ factorization in compressed space, Discrete Applied Mathematics, 10.1016/j.dam.2019.01.014, 2019.01, [URL].
13. Hiroe Inoue, Yuto Nakashima, Takuya Mieno, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Algorithms and combinatorial properties on shortest unique palindromic substrings, Journal of Discrete Algorithms, 10.1016/j.jda.2018.11.009, 52-53, 122-132, 2018.09, [URL], A palindrome is a string that reads the same forward and backward. A palindromic substring P of a string S is called a shortest unique palindromic substring (SUPS) for an interval [s,t] in S, if P occurs exactly once in S, this occurrence of P contains interval [s,t], and every palindromic substring of S which contains interval [s,t] and is shorter than P occurs at least twice in S. The SUPS problem is, given a string S, to preprocess S so that for any subsequent query interval [s,t] all the SUPSs for interval [s,t] can be answered quickly. We present an optimal solution to this problem. Namely, we show how to preprocess a given string S of length n in O(n) time and space so that all SUPSs for any subsequent query interval can be answered in O(α+1) time, where α is the number of outputs. We also discuss the number of SUPSs in a string..
14. Heikki Hyyrö, Shunsuke Inenaga, Dynamic RLE-Compressed Edit Distance Tables under General Weighted Cost Functions, International Journal of Foundations of Computer Science, 10.1142/S0129054118410083, 29, 4, 623-645, 2018.06, [URL], Kim and Park [A dynamic edit distance table, J. Disc. Algo., 2:302-312, 2004] proposed a method (KP) based on a "dynamic edit distance table" that allows one to efficiently maintain unit cost edit distance information between two strings A of length m and B of length n when the strings can be modified by single-character edits to their left or right ends. This type of computation is useful e.g. in cyclic string comparison. KP uses linear time, O(m + n), to update the distance representation after each single edit. Recently Hyyrö et al. [Incremental string comparison, J. Disc. Algo., 34:2-17, 2015] presented an efficient method for maintaining the dynamic edit distance table under general weighted edit distance, running in O(c(m + n)) time per single edit, where c is the maximum weight of the cost function. The work noted that the Θ(mn) space requirement, and not the running time, may be the main bottleneck in using the dynamic edit distance table. In this paper we take the first steps towards reducing the space usage of the dynamic edit distance table by RLE compressing A and B. Let M and N be the lengths of RLE compressed versions of A and B, respectively. We propose how to store the dynamic edit distance table using Θ(mN + Mn) space while maintaining the same time complexity as the previous methods for uncompressed strings..
15. Hideo Bannai, Travis Gagie, Shunsuke Inenaga, Juha Karkkainen, Dominik Kempa, Marcin Piatkowski, Simon J. Puglisi, Shiho Sugimoto, Diverse Palindromic Factorization is NP-Complete, International Journal of Foundations of Computer Science, 10.1142/S0129054118400014, 29, 2, 143-163, 2018.02.
16. Shunsuke Inenaga and Heikki Hyyro, A hardness result and new algorithm for the longest common palindromic subsequence problem, Information Processing Letters, 10.1016/j.ipl.2017.08.006, 129, 11-15, 2018.01.
17. Pawel Gawrychowski, Tomohiro I, Shunsuke Inenaga, Dominik Koppl, and Florin Manea, Inferring strings from Lyndon factorization, Theory of Computing Systems, 10.1007/s00224-017-9794-5, 62, 1, 162-191, 2018.01.
18. Diptarama Hendrian, Shunsuke Inenaga, Ryo Yoshinaka, Ayumi Shinohara, Efficient dynamic dictionary matching with DAWGs and AC-automata, Theoretical Computer Science, 10.1016/j.tcs.2018.04.016, 2018.01, [URL], The dictionary matching is a task to find all occurrences of pattern strings in a set D (called a dictionary) on a text string T. The Aho–Corasick-automaton (AC-automaton) which is built on D is a fundamental data structure which enables us to solve the dictionary matching problem in O(dlog⁡σ) preprocessing time and O(nlog⁡σ+occ) matching time, where d is the total length of the patterns in the dictionary D, n is the length of the text, σ is the alphabet size, and occ is the total number of occurrences of all the patterns in the text. The dynamic dictionary matching is a variant where patterns may dynamically be inserted into and deleted from the dictionary D. This problem is called semi-dynamic dictionary matching if only insertions are allowed. In this paper, we propose two efficient algorithms that can solve both problems with some modifications. For a pattern of length m, our first algorithm supports insertions in O(mlog⁡σ+log⁡d/log⁡log⁡d) time and pattern matching in O(nlog⁡σ+occ) for the semi-dynamic setting. This algorithm also supports both insertions and deletions in O(σm+log⁡d/log⁡log⁡d) time and pattern matching in O(n(log⁡d/log⁡log⁡d+log⁡σ)+occ(log⁡d/log⁡log⁡d)) time for the dynamic dictionary matching problem by some modifications. This algorithm is based on the directed acyclic word graph (DAWG) of Blumer et al. (JACM 1987). Our second algorithm, which is based on the AC-automaton, supports insertions in O(mlog⁡σ+uf+uo) time for the semi-dynamic setting and supports both insertions and deletions in O(σm+uf+uo) time for the dynamic setting, where uf and uo respectively denote the numbers of states in which the failure function and the output function need to be updated. This algorithm performs pattern matching in O(nlog⁡σ+occ) time for both settings. Our algorithm achieves optimal update time for AC-automaton based methods over constant-size alphabets, since any algorithm which explicitly maintains the AC-automaton requires Ω(m+uf+uo) update time..
19. Yuto Nakashima, Takuya Takagi, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, On the size of the smallest alphabet for Lyndon trees, Theoretical Computer Science, 10.1016/j.tcs.2018.06.044, 2018.01, [URL], We consider the problem of reverse-engineering the Lyndon tree, i.e., given a full binary ordered tree T with n leaves as input, we are to compute a string w of length n of which Lyndon tree is isomorphic to the input tree T. Hereby we call such a string a solution string. Although the problem is easily solvable in linear time for binary alphabets and unbounded-size alphabets, it is not known how to efficiently find the smallest alphabet size for a solution string. In this paper, we show several new observations concerning this problem. Namely, we show that: 1) For any positive integer n, there exists a full binary ordered tree T with n leaves, s.t. the smallest alphabet size of a solution string for T is ⌊[Formula presented]⌋+1. 2) For any full binary ordered tree T with n leaves, there exists a solution string w over an alphabet of size at most ⌊[Formula presented]⌋+1. 3) For any full binary ordered tree T, there exists a solution string w over an alphabet of size at most h+1, where h is the height of T. 4) For any complete binary ordered tree T with 2k leaves, there exists a solution string w over an alphabet of size at most 4..
20. Yuta Fujishige, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Almost linear time computation of maximal repetitions in run length encoded strings, 28th International Symposium on Algorithms and Computation, ISAAC 2017, 10.4230/LIPIcs.ISAAC.2017.33, 92, 2017.12, [URL], We consider the problem of computing all maximal repetitions contained in a string that is given in run-length encoding. Given a run-length encoding of a string, we show that the maximum number of maximal repetitions contained in the string is at most m+k-1, where m is the size of the run-length encoding, and k is the number of run-length factors whose exponent is at least 2. We also show an algorithm for computing all maximal repetitions in O(m α (m)) time and O(m) space, where α denotes the inverse Ackermann function..
21. Golnaz Badkobeh, Travis Gagie, Shunsuke Inenaga, Tomasz Kociumaka, Dmitry Kosolobov and Simon Puglisi, On Two LZ78-style Grammars: Compression Bounds and Compressed-Space Computation, Proc. 24th International Symposium on String Processing and Information Retrieval (SPIRE 2017), 10.1007/978-3-319-67428-5_5, LNCS 10508, 51-67, 2017.09.
22. Takuya Takagi, Keisuke Goto, Yuta Fujishige, Shunsuke Inenaga and Hiroki Arimura, Linear-size CDAWG: new repetition-aware indexing and grammar compression, Proc. 24th International Symposium on String Processing and Information Retrieval (SPIRE 2017), 10.1007/978-3-319-67428-5_26, LNCS 10508, 304-316, 2017.09.
23. Tenma Nakamura, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda, Order preserving pattern matching on trees and DAGs, Proc. 24th International Symposium on String Processing and Information Retrieval (SPIRE 2017), 10.1007/978-3-319-67428-5_23, LNCS 10508, 271-277, 2017.09.
24. Hideo Bannai, Tomohiro I, Shunsuke Inenaga, Yuto Nakashima, Masayuki Takeda, and Kazuya Tsuruta, The "Runs" Theorem, SIAM Journal of Computing, 10.1137/15M1011032, 46, 5, 1501-1514, 2017.09.
25. Takuya Takagi, Shunsuke Inenaga, Kunihiko Sadakane, and Hiroki Arimura, Packed Compact Tries: A Fast and Efficient Data Structure for Online String Processing, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 10.1587/transfun.E100.A.1785, E100-A, 9, 1785-1793, 2017.09.
26. Yuto Nakashima, Takuya Takagi, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda, On Reverse Engineering the Lyndon Tree, Prague Stringology Conference 2017 (PSC 2017), 108-117, 2017.08, [URL].
27. Yuka Tanimura, Takaaki Nishimoto, Hideo Bannai, Shunsuke Inenaga and Masayuki Takeda, Small-space LCE data structure with constant-time queries, Proc. 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017), 10.4230/LIPIcs.dMFCS.2017.10, 10:1-10:15, 2017.08.
28. Pawel Gawrychowski, Tomohiro I, Shunsuke Inenaga, Dominik Koppl, and Florin Manea, Inferring strings from Lyndon factorization, Theory of Computing Systems, 10.1007/s00224-017-9794-5, 62, 1, 162-191, 2017.08.
29. Hideo Bannai, Shunsuke Inenaga, Dominik Köppl, Computing All Distinct Squares in Linear Time for Integer Alphabets, Proc. the 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017), 2017.07.
30. Keita Kuboi, Yuta Fujishige, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Faster STR-IC-LCS computation via RLE, Proc. the 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017), 2017.07.
31. Takuya Mieno, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Tight bounds on the maximum number of shortest unique substrings, Proc. the 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017), 2017.07.
32. Yuto Nakashima, Hiroe Inoue, Takuya Mieno, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Shortest Unique Palindromic Substring Queries in Optimal Time, The 28th International Workshop on Combinatorial Algorithms (IWOCA 2017), 2017.07.
33. Shiho Sugimoto, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Computing Abelian string regularities based on RLE, The 28th International Workshop on Combinatorial Algorithms (IWOCA 2017), 2017.07.
34. Yohei Ueki, Diptarama, Masatoshi Kurihara, Yoshiaki Matsuoka, Kazuyuki Narisawa, Ryo Yoshinaka, Hideo Bannai, Shunsuke Inenaga, Ayumi Shinohara, Longest Common Subsequence in at Least k Length Order-isomorphic Substrings, 43rd International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2017), 10.1007/978-3-319-51963-0_28, LNCS 10139, 363-374, 2017.01.
35. Shintaro Narisada, Diptarama, Kazuyuki Narisawa, Shunsuke Inenaga, Ayumi Shinohara, Computing longest single-arm-gapped palindromes in a string, 43rd International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2017), 10.1007/978-3-319-51963-0_29, LNCS 10139, 375-386, 2017.01.
36. Tomohiro I, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Faster Lyndon factorization algorithms for SLP and LZ78 compressed text, Theoretical Computer Science, 10.1016/j.tcs.2016.03.005, 656(B), 215-224, 2016.11.
37. Yoshiaki Matsuoka, Takahiro Aoki, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Generalized pattern matching and periodicity under substring consistent equivalence relations, Theoretical Computer Science, 10.1016/j.tcs.2016.02.017, 656(B), 215-224, 2016.11.
38. Golnaz Badkobeh, Hideo Bannai, Keisuke Goto, Tomohiro I, Shunsuke Inenaga, Costas S. Iliopoulos, Simon J. Puglisi, Shiho Sugimoto, Closed Factorization, Discrete Applied Mathematics, 10.1016/j.dam.2016.04.009, 212, 23-29, 2016.10.
39. Yuta Fujishige, Michitaro Nakamura, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Finding gapped palindromes online, Proc. 27th International Workshop on Combinatorial Algorithms (IWOCA 2016), 10.1007/978-3-319-44543-4_15, Lecture Notes in Computer Science 9843, 191-202, 2016.08.
40. Takuya Takagi, Shunsuke Inenaga, Kunihiko Sadakane, Hiroki Arimura, Packed Compact Tries: A Fast and Efficient Data Structure for Online String Processing, Proc. 27th International Workshop on Combinatorial Algorithms (IWOCA 2016), 10.1007/978-3-319-44543-4_17, LNCS 9843, 213-225, 2016.08.
41. Takaaki Nishimoto, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Fully dynamic data structure for LCE queries in compressed space, Proc. the 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016), 10.4230/LIPIcs.MFCS.2016.72, 72:1-72:15, 2016.08.
42. Takuya Mieno, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Shortest Unique Substring Queries on Run-Length Encoded Strings, Proc. the 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016), 10.4230/LIPIcs.MFCS.2016.69, 69:1-69:11, 2016.08.
43. Yuta Fujishige, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Computing DAWGs and Minimal Absent Words in Linear Time for Integer Alphabets, Proc. the 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016), 10.4230/LIPIcs.MFCS.2016.38, 38:1-38:14, 2016.08.
44. Takaaki Nishimoto, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Dynamic index and LZ factorization in compressed space, Proc. Prague Stringology Conference 2016, 153-171, 2016.08.
45. Hiroe Inoue, Yoshiaki Matsuoka, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Computing Smallest and Largest Repetition Factorizations in O(n log n) time, Proc. Prague Stringology Conference 2016 (PSC 2016), 135-145, 2016.08.
46. Kazuyuki Narisawa, Hideharu Hiratsuka, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Efficient Computation of Substring Equivalence Classes with Suffix Arrays, Algorithmica, 10.1007/s00453-016-0178-z, 2016.08.
47. Yoshiaki Matsuoka, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Factorizing a string into squares in linear time, Proc. the 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016), 10.4230/LIPIcs.CPM.2016.27, 27:1-27:12, 2016.06.
48. Yuka Tanimura, Tomohiro I, Hideo Bannai, Shunsuke Inenaga, Simon Puglisi, Masayuki Takeda, Deterministic sub-linear space LCE data structures with efficient construction, Proc. the 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016), 10.4230/LIPIcs.CPM.2016.1, 2016.06.
49. Takuya Takagi, Shunsuke Inenaga, Hiroki Arimura, Fully-online construction of suffix trees for multiple texts, Proc. the 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016), 10.4230/LIPIcs.CPM.2016.22, 22:1-22:13, 2016.06.
50. Paweł Gawrychowski, Tomohiro I, Shunsuke Inenaga, Dominik Köppl, Florin Manea, Efficiently Finding All Maximal α-gapped Repeats, Proc. the 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016), 10.4230/LIPIcs.STACS.2016.39, 39:1-39:14, 2016.02.
51. Heikki Hyyro, Shunsuke Inenaga, Compacting a dynamic edit distance table by RLE compression, 42nd International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2016), 34, 302-313, 2016.01.
52. Makoto Nishida, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Inferring Strings from Full Abelian Periods, Proc. 26th International Symposium on Algorithms and Computation (ISAAC 2015), Lecture Notes in Computer Science, 2015.12.
53. Yuto Nakashima, Tomihiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Constructing LZ78 Tries and Position Heaps in Linear Time for Large Alphabets, Information Processing Letters, 115, 9, 655-659, 2015.09.
54. Heikki Hyyro, Kazuyuki Narisawa, Shunsuke Inenaga, Dynamic Edit Distance Table under a General Weighted Cost Function, Journal of Discrete Algorithms, 34, 2-17, 2015.09.
55. Hideo Bannai, Shunsuke Inenaga, Tomasz Kociumaka, Arnaud Lefebvre, Jakub Radoszewski, Wojciech Rytter, Shiho Sugimoto, Tomasz Waleń, Efficient Algorithms for Longest Closed Factor Array, Proc. the 22nd Symposium on String Processing and Information Retrieval (SPIRE 2015), 10.1007/978-3-319-23826-5_10, Lecture Notes in Computer Science 9309, 95-102, 2015.09.
56. Yuka Tanimura, Yuta Fujishige, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, A faster algorithm for computing maximal α-gapped repeats in a string, Proc. the 22nd Symposium on String Processing and Information Retrieval (SPIRE 2015), 10.1007/978-3-319-23826-5_13, Lecture Notes in Computer Science 9309, 124-136, 2015.09.
57. Takaaki Nishimoto, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Computing Left-Right Maximal Generic Words, Proc. the Prague Stringology Conference 2015 (PSC 2015), 5-16, 2015.08.
58. Shunsuke Inenaga, A Faster Longest Common Extension Algorithm on Compressed Strings and its Applications, Proc. the Prague Stringology Conference 2015 (PSC 2015), 1-4, 2015.08.
59. Hideo Bannai, Travis Gagie, Shunsuke Inenaga, Juha Kärkkäinen, Dominik Kempa, Marcin Piatkowski, Simon J. Puglisi, Shiho Sugimoto, Diverse Palindromic Factorization is NP-Complete, Proc. the 19th International Conference on Developments in Language Theory (DLT 2015), 10.1007/978-3-319-21500-6_6, Lecture Notes in Computer Science 9168, 85-96, 2015.07.
60. Yoshiaki Matsuoka, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Semi-dynamic compact index for short patterns and succinct van Emde Boas tree, Proc. 26th Annual Symposium on Combinatorial Pattern Matching (CPM 2015), 10.1007/978-3-319-19929-0_30, Lecture Notes in Computer Science 9133, 355-366, 2015.06.
61. Keisuke Goto, Hideo Bannai, Shunsuke Inenaga, Masayuki Takeda, LZD Factorization: Simple and Practical Online Grammar Compression with Variable-to-Fixed Encoding, Proc. 26th Annual Symposium on Combinatorial Pattern Matching (CPM 2015), 10.1007/978-3-319-19929-0_19, Lecture Notes in Computer Science 9133, 219-230, 2015.06.
62. Tomihiro I, Takaaki Nishimoto, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Compressed automata for dictionary matching, Theoretical Computer Science, 578, 30-41, 2015.05.
63. Yuya Tamakoshi, Keisuke Goto, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, An opportunistic text indexing structure based on run length encoding, Proc. the 9th International Conference on Algorithms and Complexity (CIAC 2015), 10.1007/978-3-319-18173-8_29, Lecture Notes in Computer Science 9079, 390-402, 2015.05.
64. Tomohiro I, Kouji Shimohira, Wataru Matsubara, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Kazuyuki Narisawa, Ayumi Shinohara, Detecting regularities on grammar-compressed strings, Information and Computation, 10.1016/j.ic.2014.09.009, 240, 74-89, 2015.02.
65. Hideo Bannai, Tomohiro I, Shunsuke Inenaga, Yuto Nakashima, Masayuki Takeda, Kazuya Tsuruta, A new characterization of maximal repetitions by Lyndon trees, Proc. ACM-SIAM Symposium on Discrete Algorithms 2015 (SODA 2015), 10.1137/1.9781611973730.38, 562-571, 2015.01.
66. Golnaz Badkobeh, Hideo Bannai, Keisuke Goto, Tomohiro I, Shunsuke Inenaga, Costas S. Iliopoulos, Simon J. Puglisi, Shiho Sugimoto, Closed Factorization, Proc. the Prague Stringology Conference 2014 (PSC 2014), 162-168, 2014.09.
67. Shohei Matsuda, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Computing Abelian Covers and Abelian Runs, Proc. the Prague Stringology Conference 2014 (PSC 2014), 43-51, 2014.09.
68. Yuto Nakashima, Takashi Okabe, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Inferring strings from Lyndon factorization, Proc. the 39th International Symposium on Mathematical Foundations of Computer Science (MFCS 2014), 10.1007/978-3-662-44465-8_48, Lecture Notes in Computer Science 8635, 565-576, 2014.08.
69. Shiho Sugimoto, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Computing Palindromic Factorizations and Palindromic Covers On-line, Proc. 25th Annual Symposium on Combinatorial Pattern Matching (CPM 2014), 10.1007/978-3-319-07566-2_16, Lecture Notes in Computer Science 8486, 150-161, 2014.06.
70. Jun'ichi Yamamoto, Tomohiro I, Hideo Bannai, Shunsuke Inenaga, Masayuki Takeda, Faster Compact On-Line Lempel-Ziv Factorization, Proc. 31st Symposium on Theoretical Aspects of Computer Science (STACS 2014), 10.4230/LIPIcs.STACS.2014.675, Leibniz International Proceedings in Informatics (LIPIcs) 25, 675-686, 2014.03.
71. Tomohiro I, Hideo Bannai, Shunsuke Inenaga, Masayuki Takeda, Inferring Strings from Suffix Trees and Links on a Binary Alphabet, Discrete Applied Mathematics, dx.doi.org/10.1016/j.dam.2013.02.033, 163, 3, 316-325, 2014.01.
72. Kazuya Tsuruta, Hideo Bannai, Shunsuke Inenaga, Masayuki Takeda, Shortest Unique Substrings Queries in Optimal Time, Proc. 40th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2014), 10.1007/978-3-319-04298-5_44, LNCS 8327, 503-513, 2014.01.
73. Tomohiro I, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Faster Lyndon Factorization Algorithms for SLP and LZ78 Compressed Text, Proc. the 20th Symposium on String Processing and Information Retrieval (SPIRE 2013), 10.1007/978-3-319-02432-5_21, Lecture Notes in Computer Science 8214, 174-185, 2013.10.
74. Tomohiro I, Takaaki Nishimoto, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Compressed Automata for Dictionary Matching, Proc. the 18th International Conference on Implementation and Application of Automata (CIAA 2013), 10.1007/978-3-642-39274-0_28, Lecture Notes in Computer Science 7982, 319-330, 2013.10.
75. Hideo Bannai, Pawel Gawrychowski, Shunsuke Inenaga, Masayuki Takeda, Converting SLP to LZ78 in almost linear time, Proc. 24th Annual Symposium on Combinatorial Pattern Matching (CPM 2013), 10.1007/978-3-642-38905-4_6, Lecture Notes in Computer Science 7922, 38-49, 2013.10.
76. Tomohiro I, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Efficient Lyndon factorization of grammar compressed text, Proc. 24th Annual Symposium on Combinatorial Pattern Matching (CPM 2013), 10.1007/978-3-642-38905-4_16, Lecture Notes in Computer Science 7922, 153-164, 2013.10.
77. Shiho Sugimoto, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Computing Reversed Lempel-Ziv Factorization Online, Proc. the Prague Stringology Conference 2013 (PSC 2013), 107-118, 2013.08.
78. Tomohiro I, Wataru Matsubara, Kouji Shimohira, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Kazuyuki Narisawa, Ayumi Sninohara, Detecting Regularities on Grammar-compressed Strings, Proc. the 38th International Symposium on Mathematical Foundations of Computer Science (MFCS 2013), 10.1007/978-3-642-40313-2_51, Lecture Notes in Computer Science 8087, 571-582, 2013.08.
79. Tomohiro I, Shunsuke Inenaga, Masayuki Takeda, Palindrome Pattern Matching, Theoretical Computer Science, dx.doi.org/10.1016/j.tcs.2012.01.047, 483, 162-170, 2013.04.
80. Yuya Tamakoshi, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, From Run Length Encoding to LZ78 and Back Again, Proc. Data Compression Conference 2013 (DCC 2013), 2013.03.
81. Toshiya Tanaka, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Computing convolution on grammar-compressed text, Proc. Data Compression Conference 2013 (DCC 2013), 2013.03.
82. Takashi Katsura, Kazuyuki Narisawa, Ayumi Shinohara, Hideo Bannai, Shunsuke Inenaga, Permuted Pattern Matching on Multi-Track Strings, Proc. the 39th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2013), dx.doi.org/10.1007/978-3-642-35843-2_25, Lecture Notes in Computer Science 7741, 280-291, 2013.01.
83. Keisuke Goto, Hideo Bannai, Shunsuke Inenaga, Masayuki Takeda, Fast q-gram mining on SLP compressed strings, Journal of Discrete Algorithms, dx.doi.org/10.1016/j.jda.2012.07.006, 18, 89-99, 2013.01.
84. Hideo Bannai, Shunsuke Inenaga, Masayuki Takeda, Efficient LZ78 Factorization of Grammar Compressed Text, Proc. the 19th Symposium on String Processing and Information Retrieval (SPIRE 2012), dx.doi.org/10.1007/978-3-642-34109-0_10, Lecture Notes in Computer Science 7608, 86-98, 2012.10.
85. Yuto Nakashima, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, The Position Heap of a Trie, Proc. the 19th Symposium on String Processing and Information Retrieval (SPIRE 2012), dx.doi.org/10.1007/978-3-642-34109-0_38, Lecture Notes in Computer Science 7608, 360-371, 2012.10.
86. Hideo Bannai, Travis Gagie, Tomohiro I, Shunsuke Inenaga, Gad M. Landau, Moshe Lewenstein, An efficient algorithm to test square-freeness of strings compressed by straight-line programs, Information Processing Letters, dx.doi.org/10.1016/j.ipl.2012.06.017, 122, 9, 711-714, 2012.10.
87. Keisuke Goto, Hideo Bannai, Shunsuke Inenaga, Masayuki Takeda, Speeding-up q-gram mining on grammar-based compressed texts, Proc. the 23rd Annual Symposium on Combinatorial Pattern Matching (CPM 2012), dx.doi.org/10.1007/978-3-642-31265-6_18, Lecture Notes in Computer Science 7354, 220-231, 2012.07.
88. Shunsuke Inenaga and Hideo Bannai, Finding Characteristic Substrings from Compressed Texts, International Journal of Foundations of Computer Science, dx.doi.org/10.1142/S0129054112400126, 23, 2, 261-280, 2012.02.
89. Shunsuke Inenaga, Hideo Bannai, Finding Characteristic Substrings from Compressed Texts, International Journal of Foundations of Computer Science, dx.doi.org/10.1142/S0129054112400126, 23, 2, 261-280, 2012.02.
90. Keisuke Goto, Hideo Bannai, Shunsuke Inenaga, and Masayuki Takeda, Computing q-gram Non-overlapping Frequencies on SLP Compressed Texts, Proc. the 38th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2012), dx.doi.org/10.1007/978-3-642-27660-6_25, Lecture Notes in Computer Science 7147, 301-312, 2012.01.
91. Tomohiro I, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, Verifying and Enumerating Parameterized Border Arrays, Theoretical Computer Science, dx.doi.org/10.1016/j.tcs.2011.09.008, 412, 50, 6959-6981, 2011.11.
92. Tomohiro I, Shunsuke Inenaga and Masayuki Takeda, Palindrome Pattern Matching, Proc. the 22nd Annual Symposium on Combinatorial Pattern Matching (CPM 2011), LNCS 6661, 232-245, 2011.06.
93. Stanislav Angelov, Shunsuke Inenaga, Teemu Kivioja, and Veli Mäkinen,, Finding Missing Patterns, Journal of Discrete Algorithms, 9, 2, 153-165, 2011.06.
94. Toru Nakamura, Shunsuke Inenaga, Daisuke Ikeda, Kensuke Baba, and Hiroto Yasuura, Password Based Anonymous Authentication with Private Information Retrieval, Journal of Digital Information Management, 9, 2, 72-78, 2011.04.
95. Toru Nakamura, Shunsuke Inenaga, Daisuke Ikeda, Kensuke Baba, and Hiroto Yasuura, An Anonymous Authentication Protocol with Single-database PIR, Proc. Australasian Information Security Conference 2011 (AISC 2011), CRPIT Series Vol. 116, 3-8, 2011.01.
96. Tomohiro I, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda, Counting and Verifying Maximal Palindromes, Proc. the 17th Symposium on String Processing and Information Retrieval (SPIRE 2010), LNCS 6393, 135-146, 2010.10.
97. Toru Nakamura, Shunsuke Inenaga, Daisuke Ikeda, Kensuke Baba, and Hiroto Yasuura, An Identifiable yet Unlinkable Authentication System with Smart Cards for Multiple Services, IPSJ Transactions on Mathematical Modeling and its Applications, 3, 3, 54-66, 2010.10.
98. Shunsuke Inenaga, Kenichiro Oyama, and Hiroto Yasuura, Towards Modeling Stored-Value Electronic Money Systems, IPSJ Transactions on Mathematical Modeling and its Applications, 3, 3, 107-116, 2010.10.
99. Tomohiro I, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda, Verifying a Parameterized Border Array in $O(n^{1.5})$ Time, Proc. the 21st Annual Symposium on Combinatorial Pattern Matching (CPM 2010),, LNCS 6129, 238-250, 2010.06.
100. Wataru Matsubara, Shunsuke Inenaga, and Ayumi Shinohara, An Efficient Algorithm to Test Square-Freeness of Strings Compressed by Balanced Straight Line Programs, Chicago Journal of Theoretical Computer Science, Special Issue: CATS 2009, Article 4, 2010.06.
101. Toru Nakamura, Shunsuke Inenaga, Daisuke Ikeda, Kensuke Baba, and Hiroto Yasuura, An Identifiable yet Unlinkable Authentication System with Smart Cards for Multiple Services, Proc. The 2010 International Conference on Computational Science and Its Applications (ICCSA 2010), LNCS 6019, 236-251, 2010.03.
102. Shunsuke Inenaga, Kenichiro Oyama, and Hiroto Yasuura, Towards Modeling Stored-Value Electronic Money Systems, Proc. 8th International Conference on Computer Information Systems and Industrial Management Applications (CISIM 2009), 902-907, 2009.12.
103. Ryosuke Nakamura, Shunsuke Inenaga, Hideo Bannai, Takashi Funamoto, Masayuki Takeda, and Ayumi Shinohara, Linear-Time Off-Line Text Compression by Longest-First Substitution, Algorithms, 2, 24, 1429-1448, 2009.11.
104. Shunsuke Inenaga and Hideo Bannai, Finding Characteristic Substrings from Compressed Texts, Proc. The Prague Stringology Conference 2009 (PSC 2009), 40-54, 2009.08.
105. Tomomi Yamasaki, Shunsuke Inenaga, Daisuke Ikeda, and Hiroto Yasuura, Modeling Costs of Access Control with Various Key Management Systems, Proc. The 2009 International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA 2009), 676-682, 2009.07.
106. Toru Nakamura, Shunsuke Inenaga, Daisuke Ikeda, Kensuke Baba, and Hiroto Yasuura, Anonymous Authentication Systems Based on Private Information Retrieval, Proc. 1st International Conference on Networked Digital Technologies (NDT 2009), 53-58, 2009.07.
107. Tomohiro I, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda, Counting Parameterized Border Arrays for a Binary Alphabet, Proc. 3rd International Conference on Language and Automata Theory and Applications (LATA 2009), LNCS 5457, 422-433, 2009.04.
108. Wataru Matsubara, Shunsuke Inenaga, Akira Ishino, Ayumi Shinohara, Tomoyuki Nakamura, and Kazuo Hashimoto, Efficient Algorithms to Compute Compressed Longest Common Substrings and Compressed Palindromes, Theoretical Computer Science, 410, 8-10, 900-913, 2009.03.
109. Wataru Matsubara, Shunsuke Inenaga, and Ayumi Shinohara, Testing Square-Freeness of Strings Compressed by Balanced Straight Line Program, Proc. 15th Computing: The Australasian Theory Symposium (CATS 2009), CRPIT Series Vol. 94, 19-28, 2009.01.
110. Wataru Matsubara, Shunsuke Inenaga, Akira Ishino, Ayumi Shinohara, Tomoyuki Nakamura, and Kazuo Hashimoto, Computing longest common substring and all palindromes from compressed strings, Proc. 34th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2008), LNCS 4910, 364-375, 2008.01.
111. Kazuyuki Narisawa, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, Efficient Computation of Substring Equivalence Classes with Suffix Arrays, Proc. 18th Annual Symposium on Combinatorial Pattern Matching (CPM 2007), LNCS 4580, 340-351, 2007.07.
112. Ryosuke Nakamura, Hideo Bannai, Shunsuke Inenaga, and Masayuki Takeda, Simple Linear-Time Off-Line Text Compression by Longest-First Substitution, Proc. Data Compression Conference 2007 (DCC 2007), 123-132, 2007.03.
113. Shunsuke Inenaga and Masayuki Takeda, Sparse Directed Acyclic Word Graphs, 13th International Symposium on String Processing and Information Retrieval (SPIRE'06), Lecture Notes in Computer Science (LNCS4209), pp. 61-73, Springer-Verlag, 2006.10.
114. Shunsuke Inenaga and Masayuki Takeda, Sparse Compact Directed Acyclic Word Graphs, The Prague Stringology Conference '06 (PSC'06), pp. 195-211, Czech Technical University, 2006.08.
115. Yasuto Higa, Hideo Bannai, Shunsuke Inenaga, and Masayuki Takeda, Reachability on Suffix Tree Graphs, The Prague Stringology Conference '06 (PSC'06), pp. 212-225, Czech Technical University, 2006.08.
116. Shunsuke Inenaga and Masayuki Takeda, On-line Linear-time Construction of Word Suffix Trees, 17th Annual Symposium on Combinatorial Pattern Matching (CPM'06), Lecture Notes in Computer Science (LNCS4009), pp. 60-71, Springer-Verlag, 2006.07.
117. Shunsuke Inenaga, Ayumi Shinohara, Masayuki Takeda, A Fully Compressed Pattern Matching Algorithm for Simple Collage Systems, International Journal of Foundations of Computer Science, 10.1142/S0129054105003728, 16, 6, 1155-1166, 2005.12.
118. Stanislav Angelov and Shunsuke Inenaga, Composite Pattern Discovery for PCR Application, 12th International Symposium on String Processing and Information Retrieval (SPIRE'05), Lecture Notes in Computer Science (LNCS3772), pp. 167-178, Springer-Verlag, 2005.11.
119. Yusuke Ishida, Shunsuke Inenaga, Ayumi Shinohara, and Masayuki Takeda, Fully Incremental LCS Computation, 15th International Symposium on Fundamentals of Computation Theory (FCT'05), 3623, 563-574, Lecture Notes in Computer Science (LNCS3623), pp. 563-574, Springer-Verlag, 2005.08.
120. Shunsuke Inenaga, Hiromasa Hoshino, Ayumi Shinohara, Masayuki Takeda, Setsuo Arikawa, Giancarlo Mauri, and Giulio Pavesi, On-Line Construction of Compact Directed Acyclic Word Graphs, Discrete Applied Mathematics, 10.1016/dam.2004.04.012, 146, 2, 156-179, 2005.03.
121. Shunsuke Inenaga, Ayumi Shinohara, and Masayuki Takeda, An Efficient Pattern Matching Algorithm on a Subclass of Context Free Grammars, Eighth International Conference on Developments in Language Theory (DLT'04), 3340, 225-236, Lecture Notes in Computer Science (LNCS3340), pp. 225-236, Springer-Verlag, 2004.12.
122. Satoru Miyamoto, Shunsuke Inenaga, Masayuki Takeda, and Ayumi Shinohara, Ternary Directed Acyclic Word Graphs, Theoretical Compututer Science, 10.1016/j.tcs.2004.07.008, 328, 1-2, 97-111, 2004.11.
123. Shunsuke Inenaga, Hideo Bannai, Heikki Hyyrö, Ayumi Shinohara, Masayuki Takeda, Kenta Nakai, and Satoru Miyano, Finding Optimal Pairs of Cooperative and Competing Patterns with Bounded Distance, 7th International Conference on Discovery Science (DS 2004), 3245, 32-46, Lecture Notes in Artificial Intelligence (LNAI3245), pp. 32-46, Springer-Verlag, 2004.10.
124. Shunsuke Inenaga, Teemu Kivioja, and Veli Mäkinen, Finding Missing Patterns, 4th Workshop on Algorithms in Bioinformatics (WABI 2004), Lecture Notes in Bioinformatics (LNBI3240), pp. 461-474, Springer-Verlag, 2004.09.
125. Shunsuke Inenaga, Ayumi Shinohara, and Masayuki Takeda, A Fully Compressed Pattern Matching Algorithm for Simple Collage Systems, The Prague Stringology Conference '04 (PSC '04), 10.1142/S0129054105003728, 16, 6, 1155-1166, pp. 98-113, Czech Technical University, 2004.08.
126. Shunsuke Inenaga, Ayumi Shinohara, Masayuki Takeda, and Setsuo Arikawa, Compact Directed Acyclic Word Graphs for a Sliding Window, Journal of Discrete Algorithms, 2, 1, 33-51, 2004.03.
127. Shunsuke Inenaga, Takashi Funamoto, Masayuki Takeda, and Ayumi Shinohara, Linear-Time Off-Line Text Compression by Longest-First Substitution, 10th International Symposium on String Processing and Information Retrieval (SPIRE 2003), 2857, 137-152, Lecture Notes in Computer Science (LNCS2857), pp. 137-152, Springer-Verlag, 2003.10.
128. Hideo Bannai, Shunsuke Inenaga, Ayumi Shinohara, and Masayuki Takeda, Inferring Strings from Graphs and Arrays, 28th International Symposium on Mathematical Foundations of Computer Science (MFCS 2003), 2747, 208-217, Lecture Notes in Computer Science (LNCS2747), pp. 208-217, Springer-Verlag, 2003.08.
129. Satoru Miyamoto, Shunsuke Inenaga, Masayuki Takeda, and Ayumi Shinohara, Ternary Directed Acyclic Word Graphs, Eighth International Conference on Implementation and Application of Automata (CIAA 2003, 2759, 120-130, Lecture Notes in Computer Science (LNCS2759), pp. 121-130, 2003.07.
130. Shunsuke Inenaga, Bidirectional Construction of Suffix Trees, Nordic Journal of Computing, 10, 1, 52-67, 2003.04.
131. Shunsuke Inenaga, Hideo Bannai, Ayumi Shinohara, Masayuki Takeda, and Setsuo Arikawa, Discovering Best Variable-Length-Don't-Care Patterns, The Fifth International Conference on Discovery Science (DS '02), 2534, 86-97, Lecture Notes in Computer Science (LNCS2534), pp. 86-97, 2002.11.
132. Shunsuke Inenaga, Ayumi Shinohara, Masayuki Takeda, and Setsuo Arikawa, Compact Directed Acyclic Word Graphs for a Sliding Window, 9th International Symposium on String Processing and Information Retrieval (SPIRE 2002), Lecture Notes in Computer Science (LNCS 2476), pp. 310-324, 2002.09.
133. Shunsuke Inenaga, Bidirectional Construction of Suffix Trees, The Prague Stringology Conference '02 (PSC '02), pp. 75-87, Czech Technical University, 2002.09.
134. Shunsuke Inenaga, Masayuki Takeda, Ayumi Shinohara, Hiromasa Hoshino, and Setsuo Arikawa, The Minimum DAWG for All Suffixes of a String and Its Applications, 13th Annual Symposium on Combinatorial Pattern Matching (CPM 2002), 2373, 153-167, Lecture Notes in Computer Science (LNCS 2373), pp. 153-167, 2002.07.
135. Shunsuke Inenaga, Hiromasa Hoshino, Ayumi Shinohara, Masayuki Takeda, and Setsuo Arikawa, On-Line Construction of Symmetric Compact Directed Acyclic Word Graphs, 8th International Symposium on String Processing and Information Retrieval (SPIRE '01), 96-110, pp. 96-110, IEEE Computer Society, 2001.11.
136. Masahiro Hirao, Shunsuke Inenaga, Ayumi Shinohara, Masayuki Takeda, and Setsuo Arikawa, A Practical Algorithm to Find the Best Episode Patterns, The Fourth International Conference on Discovery Science (DS '01), Lecture Notes in Artificial Intelligence (LNAI 2226), pp. 435-440, 2001.11.
137. Shunsuke Inenaga, Hiromasa Hoshino, Ayumi Shinohara, Masayuki Takeda, and Setsuo Arikawa, Construction of the CDAWG for a Trie, The Prague Stringology Conference '01 (PSC '01), pp. 37-48, Czech Technical University, 2001.09.
138. Shunsuke Inenaga, Hiromasa Hoshino, Ayumi Shinohara, Masayuki Takeda, Setsuo Arikawa, Giancarlo Mauri, and Giulio Pavesi, On-Line Construction of Compact Directed Acyclic Word Graphs, 12th Annual Symposium on Combinatorial Pattern Matching (CPM 2001), 10.1016/dam.2004.04.012, 146, 2, 156-179, Lecture Notes in Computer Science (LNCS 2089), pp. 169-180, 2001.07.
主要学会発表等
1. Akihiro Nishi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, O(n log n)-time Text Compression by LZ-style Longest First Substitution, Prague Stringology Conference 2018 (PSC 2018), 2018.08.
2. Prague Stringology Conference 2018 (PSC 2018), Right-to-left Online Construction of Parameterized Position Heaps, Prague Stringology Conference 2018 (PSC 2018), 2018.08.
3. Noriki Fujisato, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, The Parameterized Position Heap of a Trie, 11th International Conference on Algorithms and Complexity (CIAC 2019), 2019.05.
4. Yuki Kuhara, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Recovering, counting and enumerating strings from forward and backward suffix arrays, 25th International Symposium on String Processing and Information Retrieval, SPIRE 2018, 2018.10, [URL], The suffix array SAw of a string w of length n is a permutation of [1..n] such that SAw[i]=j iff w[j, n] is the lexicographically i-th suffix of w. In this paper, we consider variants of the reverse-engineering problem on suffix arrays with two given permutations P and Q of [1..n], such that P refers to the forward suffix array of some string w and Q refers to the backward suffix array of the reversed string wR. Our results are the following: (1) An algorithm which computes a solution string over an alphabet of the smallest size, in O(n) time. (2) The exact number of solution strings over an alphabet of size σ. (3) An efficient algorithm which computes all solution strings in the lexicographical order, in time near optimal up to log n factor..
5. Yuki Urabe, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Longest lyndon substring after edit, 29th Annual Symposium on Combinatorial Pattern Matching, CPM 2018, 2018.07, [URL], The longest Lyndon substring of a string T is the longest substring of T which is a Lyndon word. LLS(T) denotes the length of the longest Lyndon substring of a string T. In this paper, we consider computing LLS(T′) where T′ is an edited string formed from T. After O(n) time and space preprocessing, our algorithm returns LLS(T′) in O(log n) time for any single character edit. We also consider a version of the problem with block edits, i.e., a substring of T is replaced by a given string of length l. After O(n) time and space preprocessing, our algorithm returns LLS(T′) in O(l log σ + log n) time for any block edit where σ is the number of distinct characters in T. We can modify our algorithm so as to output all the longest Lyndon substrings of T′ for both problems..
6. Mitsuru Funakoshi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Longest substring palindrome after edit, 29th Annual Symposium on Combinatorial Pattern Matching, CPM 2018, 2018.07, [URL], It is known that the length of the longest substring palindromes (LSPals) of a given string T of length n can be computed in O(n) time by Manacher's algorithm [J. ACM '75]. In this paper, we consider the problem of finding the LSPal after the string is edited. We present an algorithm that uses O(n) time and space for preprocessing, and answers the length of the LSPals in O(log(min{ω, log n})) time after single character substitution, insertion, or deletion, where ω denotes the number of distinct characters appearing in T. We also propose an algorithm that uses O(n) time and space for preprocessing, and answers the length of the LSPals in O(ℓ+log n) time, after an existing substring in T is replaced by a string of arbitrary length ℓ..
7. Isamu Furuya, Yuto Nakashima, I. Tomohiro, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Lyndon factorization of grammar compressed texts revisited, 29th Annual Symposium on Combinatorial Pattern Matching, CPM 2018, 2018.07, [URL], We revisit the problem of computing the Lyndon factorization of a string w of length N which is given as a straight line program (SLP) of size n. For this problem, we show a new algorithm which runs in O(P(n,N) + Q(n,N)n log logN) time and O(n logN + S(n,N)) space where P(n,N), S(n,N), Q(n,N) are respectively the pre-processing time, space, and query time of a data structure for longest common extensions (LCE) on SLPs. Our algorithm improves the algorithm proposed by I et al. (TCS '17), and can be more efficient than the O(N)-time solution by Duval (J. Algorithms '83) when w is highly compressible..
8. Shiho Sugimoto, Naoki Noda, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Computing abelian string regularities based on RLE, 28th International Workshop on Combinational Algorithms, IWOCA 2017, 2018.01, [URL], Two strings x and y are said to be Abelian equivalent if x is a permutation of y, or vice versa. If a string z satisfies z = xy with x and y being Abelian equivalent, then z is said to be an Abelian square. If a string w can be factorized into a sequence v1, …, vs of strings such that v1, …, vs-1 are all Abelian equivalent and vs is a substring of a permutation of v1, then w is said to have a regular Abelian period (p, t) where p = |v1| and t = |vs|. If a substring w1[i.i+l-1] of a string w1 and a substring w2[j.j + l - 1] of another string w2 are Abelian equivalent, then the substrings are said to be a common Abelian factor of w1 and w2 and if the length l is the maximum of such then the substrings are said to be a longest common Abelian factor of w1 and w2. We propose efficient algorithms which compute these Abelian regularities using the run length encoding (RLE) of strings. For a given string w of length n whose RLE is of size m, we propose algorithms which compute all Abelian squares occurring in w in O(mn) time, and all regular Abelian periods of w in O(mn) time. For two given strings w1 and w2 of total length n and of total RLE size m, we propose an algorithm which computes all longest common Abelian factors in O(m2n) time..
9. Yuto Nakashima, Hiroe Inoue, Takuya Mieno, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Shortest unique palindromic substring queries in optimal time, 28th International Workshop on Combinational Algorithms, IWOCA 2017, 2018.01, [URL], palindrome is a string that reads the same forward and backward. A palindromic substring P of a string S is called a shortest unique palindromic substring (SUPS) for an interval [s, t] in S, if P occurs exactly once in S, this occurrence of P contains interval [s, t], and every palindromic substring of S which contains interval [s, t] and is shorter than P occurs at least twice in S. The SUPS problem is, given a string S, to preprocess S so that for any subsequent query interval [s, t] all the SUPSs for interval [s, t] can be answered quickly. We present an optimal solution to this problem. Namely, we show how to preprocess a given string S of length n in O(n) time and space so that all SUPSs for any subsequent query interval can be answered in O(α + 1) time, where α is the number of outputs..
10. Yuta Fujishige, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, Almost Linear Time Computation of Maximal Repetitions in Run Length Encoded Strings, 28th International Symposium on Algorithms and Computation (ISAAC 2017), 2017.12.
11. Golnaz Badkobeh, Travis Gagie, Shunsuke Inenaga, Tomasz Kociumaka, Dmitry Kosolobov and Simon Puglisi, On Two LZ78-style Grammars: Compression Bounds and Compressed-Space Computation, 24th International Symposium on String Processing and Information Retrieval (SPIRE 2017), 2017.09.
12. Tenma Nakamura, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda, Order preserving pattern matching on trees and DAGs, 24th International Symposium on String Processing and Information Retrieval (SPIRE 2017), 2017.09.
13. Takuya Takagi, Keisuke Goto, Yuta Fujishige, Shunsuke Inenaga and Hiroki Arimura, Linear-size CDAWG: new repetition-aware indexing and grammar compression, 24th International Symposium on String Processing and Information Retrieval (SPIRE 2017), 2017.09.
14. Yuto Nakashima, Takuya Takagi, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda, On Reverse Engineering the Lyndon Tree, Prague Stringology Conference 2017 (PSC 2017), 2017.08.
15. Yuka Tanimura, Takaaki Nishimoto, Hideo Bannai, Shunsuke Inenaga and Masayuki Takeda, Small-space LCE data structure with constant-time queries, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017), 2017.08.
16. Hideo Bannai, Shunsuke Inenaga, Dominik Köppl, Computing All Distinct Squares in Linear Time for Integer Alphabets, 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017), 2017.07.
17. Keita Kuboi, Yuta Fujishige, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Faster STR-IC-LCS computation via RLE, 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017), 2017.07.
18. Takuya Mieno, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Tight bounds on the maximum number of shortest unique substrings, 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017), 2017.07.
19. Shiho Sugimoto, Naoki Noda, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Computing Abelian string regularities based on RLE, 28th International Workshop on Combinatorial Algorithms (IWOCA 2017), 2017.07.
20. Yuto Nakashima, Hiroe Inoue, Takuya Mieno, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Shortest Unique Palindromic Substring Queries in Optimal Time, 28th International Workshop on Combinatorial Algorithms (IWOCA 2017), 2017.07.
21. Yohei Ueki, Diptarama, Masatoshi Kurihara, Yoshiaki Matsuoka, Kazuyuki Narisawa, Ryo Yoshinaka, Hideo Bannai, Shunsuke Inenaga, Ayumi Shinohara, Longest Common Subsequence in at Least k Length Order-isomorphic Substrings, 43rd International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2017), 2017.01.
22. Shintaro Narisada, Diptarama, Kazuyuki Narisawa, Shunsuke Inenaga, Ayumi Shinohara, Computing longest single-arm-gapped palindromes in a string, 43rd International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2017), 2017.01.
23. Yuta Fujishige, Michitaro Nakamura, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Finding gapped palindromes online, 27th International Workshop on Combinatorial Algorithms (IWOCA 2016), 2016.08.
24. Takaaki Nishimoto, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Fully dynamic data structure for LCE queries in compressed space, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016), 2016.08.
25. Yuta Fujishige, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Computing DAWGs and Minimal Absent Words in Linear Time for Integer Alphabets, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016), 2016.08.
26. Takaaki Nishimoto, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Dynamic index and LZ factorization in compressed space, Prague Stringology Conference 2016 (PSC 2016), 2016.08.
27. Hiroe Inoue, Yoshiaki Matsuoka, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Computing Smallest and Largest Repetition Factorizations in O(n log n) time, Prague Stringology Conference 2016 (PSC 2016), 2016.08.
28. Pawel Gawrychowski, Tomohiro I, Shunsuke Inenaga, Dominik Köppl, Florin Manea, Efficiently Finding All Maximal α-gapped Repeats, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016), 2016.02.
29. Heikki Hyyrö, Shunsuke Inenaga, Compacting a dynamic edit distance table by RLE compression, 42nd International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2016), 2016.01.
30. Makoto Nishida, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Inferring Strings from Full Abelian Periods, 26th International Symposium on Algorithms and Computation (ISAAC 2015), 2015.12.
31. Hideo Bannai, Shunsuke Inenaga, Tomasz Kociumaka, Arnaud Lefebvre, Jakub Radoszewski, Wojciech Rytter, Shiho Sugimoto, Tomasz Waleń, Efficient Algorithms for Longest Closed Factor Array, 22nd Symposium on String Processing and Information Retrieval (SPIRE 2015), 2015.09.
32. Yuka Tanimura, Yuta Fujishige, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, A faster algorithm for computing maximal α-gapped repeats in a string, 22nd Symposium on String Processing and Information Retrieval (SPIRE 2015), 2015.09.
33. Takaaki Nishimoto, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Computing Left-Right Maximal Generic Words, Proc. Prague Stringology Conference 2015 (PSC 2015), 2015.08.
34. Shunsuke Inenaga, A Faster Longest Common Extension Algorithm on Compressed Strings and its Applications, Proc. Prague Stringology Conference 2015 (PSC 2015), 2015.08.
35. Hideo Bannai, Travis Gagie, Shunsuke Inenaga, Juha Kärkkäinen, Dominik Kempa, Marcin Piatkowski, Simon J. Puglisi, Shiho Sugimoto, Diverse Palindromic Factorization is NP-Complete, 19th International Conference on Developments in Language Theory (DLT 2015), 2015.07.
36. Yoshiaki Matsuoka, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Semi-dynamic compact index for short patterns and succinct van Emde Boas tree, 26th Annual Symposium on Combinatorial Pattern Matching (CPM 2015), 2015.06.
37. Keisuke Goto, Hideo Bannai, Shunsuke Inenaga, Masayuki Takeda, LZD Factorization: Simple and Practical Online Grammar Compression with Variable-to-Fixed Encoding, 26th Annual Symposium on Combinatorial Pattern Matching (CPM 2015), 2015.06.
38. Yoshiaki Matsuoka, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Factorizing a string into squares in linear time, 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016), 2015.06.
39. Yuka Tanimura, Tomohiro I, Hideo Bannai, Shunsuke Inenaga, Simon J. Puglisi, Masayuki Takeda, Deterministic sub-linear space LCE data structures with efficient construction, 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016), 2015.06.
40. Takuya Takagi, Shunsuke Inenaga, Hiroki Arimura, Fully-online construction of suffix trees for multiple texts, 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016), 2015.06.
41. Takuya Takagi, Shunsuke Inenaga, Kunihiko Sadakane, Hiroki Arimura, Packed Compact Tries: A Fast and Efficient Data Structure for Online String Processing, 27th International Workshop on Combinatorial Algorithms (IWOCA 2016), 2015.06.
42. Yuya Tamakoshi, Keisuke Goto, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, An opportunistic text indexing structure based on run length encoding, 9th International Conference on Algorithms and Complexity (CIAC 2015), 2015.05.
43. 西本 崇晃, 井 智弘, 稲永 俊介, 坂内 英夫, 竹田 正幸, 動的な圧縮索引, LAシンポジウム 2014 冬, 2015.01.
44. 中島 祐人, 稲永 俊介, 坂内 英夫, 竹田 正幸, Lyndon ≦ LZ77 Conjecture, LAシンポジウム 2014 冬, 2015.01.
45. 青木 隆宏, 松岡 禎明, 稲永 俊介, 坂内 英夫, 竹田 正幸, 順序同型パターン照合アルゴリズム, LAシンポジウム 2014 冬, 2015.01.
46. 藤重 雄大, 稲永 俊介, 坂内 英夫, 竹田 正幸, 重複のない文字列における α-ギャップ repeat の列挙, LAシンポジウム 2014 冬, 2015.01.
47. 谷村 優佳, 稲永 俊介, 坂内 英夫, 竹田 正幸, 文字列中にある極大α-gapped repeatの列挙, LAシンポジウム 2014 冬, 2015.01.
48. 中村 道太郎, 稲永 俊介, 坂内 英夫, 竹田 正幸, 固定長ギャップ付き回文のオンライン計算, LAシンポジウム 2014 冬, 2015.01.
49. 久保井 啓太, 稲永 俊介, 坂内 英夫, 竹田 正幸, 制約柔軟パターンを含む最長共通柔軟パターン問題, LAシンポジウム 2014 冬, 2015.01.
50. Hideo Bannai, Tomohiro I, Shunsuke Inenaga, Yuto Nakashima, Masayuki Takeda, Kazuya Tsuruta, A new characterization of maximal repetitions by Lyndon trees, ACM-SIAM Symposium on Discrete Algorithms 2015 (SODA 2015), 2015.01.
51. Golnaz Badkobeh, Hideo Bannai, Keisuke Goto, Tomohiro I, Costas S. Iliopoulos, Shunsuke Inenaga, Simon J. Puglisi, Shiho Sugimoto, Closed Factorization, Prague Stringology Conference 2014 (PSC 2014), 2014.09.
52. Shohei Matsuda, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Computing Abelian Covers and Abelian Runs, Prague Stringology Conference 2014 (PSC 2014), 2014.09.
53. Yuto Nakashima, Takashi Okabe, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Inferring strings from Lyndon factorization, 39th International Symposium on Mathematical Foundations of Computer Science (MFCS 2014), 2014.08.
54. 西田 真, 稲永 俊介, 坂内 英夫, 竹田 正幸, 文字列のアーベル周期の逆問題について, 夏のLAシンポジウム2014, 2014.07.
55. 松田 奨平, 稲永 俊介, 坂内 英夫, 竹田 正幸, 文字列のアーベル被覆とアーベル連, 夏のLAシンポジウム2014, 2014.07.
56. Tomohiro I, Shiho Sugimoto, Hideo Bannai, Shunsuke Inenaga, Masayuki Takeda, Computing Palindromic Factorizations and Palindromic Covers On-line, 25th Annual Symposium on Combinatorial Pattern Matching (CPM 2014), 2014.06.
57. Jun'ichi Yamamoto, Tomohiro I, Hideo Bannai, Shunsuke Inenaga, Masayuki Takeda, Faster Compact On-Line Lempel-Ziv Factorization, 31st Symposium on Theoretical Aspects of Computer Science (STACS 2014), 2014.03.
58. 杉本 志穂, 井 智弘, 稲永 俊介, 坂内 英夫, 竹田 正幸, 回文による文字列の分解と被覆, 冬のLAシンポジウム2013, 2014.01.
59. 井 智弘, 中島 祐人, 稲永 俊介, 坂内 英夫, 竹田 正幸, LZ78圧縮されたテキストに対するLyndon分解アルゴリズム, 冬のLAシンポジウム2013, 2014.01.
60. 玉腰 裕也, 後藤 啓介, 稲永 俊介, 坂内 英夫, 竹田 正幸, 連長圧縮と接尾辞配列について, 冬のLAシンポジウム2013, 2014.01.
61. 山本 淳一, 井 智弘, 坂内 英夫, 稲永 俊介, 竹田 正幸, 省スペースオンラインLZ分解, 冬のLAシンポジウム2013, 2014.01.
62. 松岡 禎明, 井 智弘, 坂内 英夫, 稲永 俊介, 竹田 正幸, 動的でコンパクトな索引構造, 冬のLAシンポジウム2013, 2014.01.
63. Kazuya Tsuruta, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Shortest Unique Substrings Queries in Optimal Time, 40th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2014), 2014.01.
64. Tomohiro I, Yuto Nakashima, Hideo Bannai, Shunsuke Inenaga, Masayuki Takeda, Faster Lyndon Factorization Algorithms for SLP and LZ78 Compressed Text, 20th Symposium on String Processing and Information Retrieval (SPIRE 2013), 2013.10.
65. Tomohiro I, Wataru Matsubara, Kouji Shimohira, Hideo Bannai, Shunsuke Inenaga, Masayuki Takeda, Kazuyuki Narisawa, Ayumi Shinohara, Detecting Regularities on Grammar-compressed Strings, 38th International Symposium on Mathematical Foundations of Computer Science (MFCS 2013), 2013.08.
66. Shiho Sugimoto, Tomohiro I, Hideo Bannai, Shunsuke Inenaga, Masayuki Takeda, Computing Reversed Lempel-Ziv Factorization Online, Prague Stringology Conference 2013 (PSC 2013), 2013.08.
67. 中島 祐人, 岡部 駿志, 井 智弘, 稲永 俊介, 坂内 英夫, 竹田 正幸, Lyndon分解の逆問題, 夏のLAシンポジウム2013, 2013.07.
68. 西本 崇晃, 井 智弘, 稲永 俊介, 坂内 英夫, 竹田 正幸, Sorting, Indexing, Computing LCE and LCP of SLP Compressed Strings, 夏のLAシンポジウム2014, 2013.07.
69. Tomohiro I, Takaaki Nishimoto, Hideo Bannai, Shunsuke Inenaga, Masayuki Takeda, Compressed Automata for Dictionary Matching, 18th International Conference on Implementation and Application of Automata (CIAA 2013), 2013.07.
70. Tomohiro I, Yuto Nakashima, Hideo Bannai, Shunsuke Inenaga, Masayuki Takeda, Efficient Lyndon factorization of grammar compressed text, 24th Annual Symposium on Combinatorial Pattern Matching (CPM 2013), 2013.06.
71. Hideo Bannai, Pawel Gawrychowski, Shunsuke Inenaga, Masayuki Takeda, Converting SLP to LZ78 in almost linear time, 24th Annual Symposium on Combinatorial Pattern Matching (CPM 2013), 2013.06.
72. Yuya Tamakoshi, Tomohiro I, Hideo Bannai, Shunsuke Inenaga, Masayuki Takeda, From Run Length Encoding to LZ78 and Back Again, Data Compression Conference 2013 (DCC 2013), 2013.03.
73. Toshiya Tanaka, Tomohiro I, Hideo Bannai, Shunsuke Inenaga, Masayuki Takeda, Computing convolution on grammar-compressed text, Data Compression Conference 2013 (DCC 2013), 2013.03.
74. 西本 崇晃, 井 智弘, 稲永 俊介, 坂内 英夫, 竹田 正幸, 高速パターン照合を可能にする新しい文法圧縮型自己索引, 冬のLAシンポジウム2012, 2013.01.
75. 西田 真, 井 智弘, 稲永 俊介, 坂内 英夫, 竹田 正幸, 直線的プログラムに含まれる繰り返し構造の検出, 冬のLAシンポジウム2012, 2013.01.
76. 井 智弘, 中島 祐人, 稲永 俊介, 坂内 英夫, 竹田 正幸, 圧縮テキスト上で動作するLyndon分解アルゴリズム, 冬のLAシンポジウム2012, 2013.01.
77. 杉本 志穂, 井 智弘, 稲永 俊介, 坂内 英夫, 竹田 正幸, 逆向きLZ77分解のオンライン計算について, 冬のLAシンポジウム2012, 2013.01.
78. Takashi Katsura, Kazuyuki Narisawa, Ayumi Shinohara, Hideo Bannai, Shunsuke Inenaga, Permuted Pattern Matching on Multi-Track Strings, 39th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2013), 2013.01.
79. Hideo Bannai, Shunsuke Inenaga, Masayuki Takeda, Efficient LZ78 Factorization of Grammar Compressed Text, 19th Symposium on String Processing and Information Retrieval (SPIRE 2012), 2012.10.
80. Yuto Nakashima, Tomohiro I, Hideo Bannai, Shunsuke Inenaga, Masayuki Takeda, The Position Heap of a Trie, 19th Symposium on String Processing and Information Retrieval (SPIRE 2012), 2012.10.
81. Yuto Nakashima, Tomohiro I, Hideo Bannai, Shunsuke Inenaga, Masayuki Takeda, The Position Heap of a Trie, 19th Symposium on String Processing and Information Retrieval (SPIRE 2012), 2012.10.
82. 田中 俊弥, 稲永 俊介, 坂内 英夫, 竹田 正幸, 圧縮テキストに対する畳み込み計算, 夏のLAシンポジウム2012, 2012.07.
83. 杉本 志穂, 稲永 俊介, 坂内 英夫, 竹田 正幸, 極小不在パターンの列挙アルゴリズム, 夏のLAシンポジウム2012, 2012.07.
84. 井 智弘, 稲永 俊介, 坂内 英夫, 直線的プログラムで圧縮された文字列の非反復性検証アルゴリズム, 夏のLAシンポジウム2012, 2012.07.
85. 玉腰 裕也, 坂内 英夫, 稲永 俊介, 竹田 正幸, 木構造で表現された複数文字列に対する接尾辞配列の構築, 夏のLAシンポジウム2012, 2012.07.
86. 中島 祐人, 井 智弘, 稲永 俊介, 坂内 英夫, 竹田 正幸, 木構造で表現された複数文字列に対するポジションヒープ, 夏のLAシンポジウム2012, 2012.07.
87. 山本 淳一, 稲永 俊介, 坂内 英夫, 竹田 正幸, 連長圧縮に基づくLZ77分解, 夏のLAシンポジウム2012, 2012.07.
88. Keisuke Goto, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Speeding-up q-gram mining on grammar-based compressed texts, 23rd Annual Symposium on Combinatorial Pattern Matching (CPM 2012), 2012.07.
89. Keisuke Goto, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Computing q-gram Non-overlapping Frequencies on SLP Compressed Texts, 38th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2012), 2012.01.
90. Keisuke Goto, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Fast q-gram Mining on SLP Compressed Strings, 18th Symposium on String Processing and Information Retrieval (SPIRE 2011), 2011.10.
91. Tomohiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Inferring Strings from Suffix Trees and Links on a Binary Alphabet, The Prague Stringology Conference 2011 (PSC 2011), 2011.08.
92. Kouji Shimohira, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Computing Longest Common Substring/Subsequence of Non-linear Texts, The Prague Stringology Conference 2011 (PSC 2011), 2011.08.
93. Tomohiro I, Shunsuke Inenaga, Masayuki Takeda, Palindrome Pattern Matching, 22nd Annual Symposium on Combinatorial Pattern Matching (CPM 2011), 2011.06.
94. Takanori Yamamoto, Hideo Bannai, Shunsuke Inenaga, Masayuki Takeda, Faster Subsequence and Don't-Care Pattern Matching on Compressed Texts, 22nd Annual Symposium on Combinatorial Pattern Matching (CPM 2011), 2011.06.
95. Toru Nakamura, Shunsuke Inenaga, Daisuke Ikeda, Kensuke Baba, Hiroto Yasuura, An Anonymous Authentication Protocol with Single-database PIR, Australasian Information Security Conference 2011 (AISC 2011), 2011.01.
96. Tomohiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Counting and Verifying Maximal Palindromes, 17th Symposium on String Processing and Information Retrieval (SPIRE 2010), 2010.10.
97. Tomohiro I, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda, Counting and Verifying Maximal Palindromes, コンピュテーション研究会, 2010.09.
98. 井智弘,稲永俊介,坂内英夫,竹田正幸, Verifying a Parameterized Border Array in $O(n^{1.5})$ Time, 第9回情報科学技術フォーラム(FIT 2010), 2010.09.
99. 稲永俊介,坂内英夫, Finding Characteristic Substrings from Compressed Texts, 夏のLAシンポジウム2010, 2010.07.
100. Tomohiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Verifying a Parameterized Border Array in O(n^{1.5}) Time, 21st Annual Symposium on Combinatorial Pattern Matching (CPM 2010), 2010.06.
101. Tomomi Yamasaki, Shunsuke Inenaga, Daisuke Ikeda, and Hiroto Yasuura, Modeling Costs of Access Control with Various Key Management Systems, 第74回数理モデル化と問題解決(MPS)研究会, 2009.07.
102. 松原渉,稲永俊介,篠原歩, 平衡直線的プログラムで圧縮された文字列の非反復性検証アルゴリズム, コンピュテーション研究会, 2009.03.
103. 中村徹,稲永俊介,馬場謙介,池田大輔,安浦寛人, マルチサービス環境における署名手法のリンク不能性に関する研究, 2009年暗号と情報セキュリティシンポジウム(SCIS2009), 2009.01.
104. 中村徹,稲永俊介,馬場謙介,池田大輔,安浦寛人, プライバシ保護とメモリ効率性の両立を実現するマルチサービス環境向け認証方式, コンピュータセキュリティシンポジウム2008, 2008.10.
105. 松原渉,稲永俊介,石野明,篠原歩,中村智将,橋本和夫, 圧縮文字列における最長共通部分文字列および回文を求める多項式時間アルゴリズム, コンピュテーション研究会, 2008.03.
106. 中村徹,稲永俊介,池田大輔,馬場謙介,安浦寛人, 認証システムのプライバシ保護評価のためのフレームワークの提案, 暗号と情報セキュリティシンポジウム (SCIS2008), 2008.01.
107. 中村徹,稲永俊介,馬場謙介,池田大輔,安浦寛人, プライバシ保護技術の評価のための権限認証モデル, コンピュータセキュリティシンポジウム2007 (CSS2007), 2007.10.
108. 小山健一郎,稲永俊介,安浦寛人, 電子マネーシステムの価値保存形式を考慮したモデル化, 第63回数理モデル化と問題解決(MPS)研究会, 2007.03.
109. 稲永俊介,竹田正幸, 単語接尾辞木再考, 第61回人工知能基本問題研究会, 2005.11.
110. 石田祐介,稲永俊介,篠原歩,竹田正幸, 漸増的最長共通部分列問題, 日本応用数理学会2005年度年会, 2005.09.
111. 稲永俊介, 欠如パターン発見問題, 情報検索と発見科学に関する研究会, 2003.03.
112. 稲永俊介,星野弘雅,篠原歩,竹田正幸,有川節夫, Unification of Algorithms to Construct Index Structures for Texts, 夏のLAシンポジウム2001, 2001.07.
学会活動
所属学会名
EATCS
情報処理学会
LAシンポジウム
学会大会・会議・シンポジウム等における役割
2018.07.02~2018.07.05, 29th Annual Symposium on Combinatorial Pattern Matching (CPM 2018), Session Chair (座長).
2018.08.28~2018.08.30, Prague Stringology Conference 2018 (PSC 2018), Session Chair (座長).
2018.10.09~2018.10.11, 25th International Symposium on String Processing and Information Retrieval (SPIRE 2018), Steering Committee member.
2018.08.28~2018.08.30, Prague Stringology Conference 2018 (PSC 2018), PC member.
2018.07.02~2018.07.05, 29th Annual Symposium on Combinatorial Pattern Matching (CPM 2018), PC member.
2017.12.09~2017.12.12, 28th International Symposium on Algorithms and Computation (ISAAC 2017), 座長(Chairmanship).
2017.09.26~2017.09.29, 24th International Symposium on String Processing and Information Retrieval (SPIRE 2017), Steering Committee member.
2017.09.26~2017.09.29, 24th International Symposium on String Processing and Information Retrieval (SPIRE 2017), PC member.
2017.08.28~2017.08.30, The Prague Stringology Conference 2016 (PSC 2017), PC co-chair.
2016.10.18~2016.10.20, 23rd International Symposium on String Processing and Information Retrieval (SPIRE 2016), PC co-chair.
2016.10.18~2016.10.20, 23rd International Symposium on String Processing and Information Retrieval (SPIRE 2016), 座長(Chairmanship).
2016.10~2016.10, 23rd edition of the International Symposium on String Processing and Information Retrieval (SPIRE 2016), 座長(Chairmanship).
2016.08.29~2016.08.31, The Prague Stringology Conference 2016 (PSC 2016), PC Member.
2016.08~2016.08.01, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016), 座長(Chairmanship).
2016.08~2016.08, 27th International Workshop on Combinatorial Algorithms (IWOCA 2016), 座長(Chairmanship).
2016.06.27~2016.06.29, 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016), PC member.
2015.09.01~2015.09.04, 22nd edition of the International Symposium on String Processing and Information Retrieval (SPIRE 2015), 座長(Chairmanship).
2015.08.24~2015.08.26, The Prague Stringology Conference 2015 (PSC 2015), PC Member.
2015.08.24~2015.08.26, Prague Stringology Conference 2015 (PSC 2015), 座長(Chairmanship).
2015.07~2015.07, LAシンポジウム 2016 夏, 座長(Chairmanship).
2015.01.28~2015.01.30, LAシンポジウム 2014 冬, 座長(Chairmanship).
2014.10.20~2014.10.23, The 21st International Symposium on String Processing and Information Retrieval (SPIRE 2014), PC Member .
2014.09.02~2014.09.04, The Prague Stringology Conference 2014 (PSC 2014), PC Member.
2013.10.07~2013.10.09, The 20th International Symposium on String Processing and Information Retrieval (SPIRE 2013), PC Member .
2013.09.24~2013.09.25, 電気関係学会九州支部連合大会, プログラム編集委員長.
2013.09.02~2013.09.04, The Prague Stringology Conference 2013 (PSC 2013), PC Member.
2013.09.02~2013.09.04, Prague Stringology Conference 2013 (PSC 2013), 座長(Chairmanship).
2012.09.24~2012.09.25, 電気関係学会九州支部連合大会, プログラム編集副委員長.
2012.08.27~2012.08.31, The Prague Stringology Conference 2012 (PSC 2012), PC Member.
2011.10.18~2011.10.20, The 18th International Symposium on String Processing and Information Retrieval (SPIRE 2011), PC Member .
2011.08.29~2001.08.31, The Prague Stringology Conference 2011 (PSC 2011), PC Member.
2011.08.29~2011.08.31, The Prague Stringology Conference 2011 (PSC 2011), 座長(Chairmanship).
2011.05.30~2011.06.03, The 5th International Conference on Language and Automata Theory and Applications (LATA 2011), PC Co-chair.
2011.05.30~2011.06.03, The 5th International Conference on Language and Automata Theory and Applications (LATA 2011), 座長(Chairmanship).
2010.08.30~2010.09.01, The Prague Stringology Conference 2010 (PSC 2010), PC Member.
2010.08.30~2010.09.01, The Prague Stringology Conference 2010 (PSC 2010), 座長(Chairmanship).
2010.06.21~2010.06.23, The 21st Annual Symposium on Combinatorial Pattern Matching (CPM 2010), PC Member.
2010.06.21~2010.06.23, The 21st Annual Symposium on Combinatorial Pattern Matching (CPM 2010), 座長(Chairmanship).
2010.03.23~2010.03.26, Workshop on Information Retrieval, Security and Innovative Applications (RSIA 2010), PC Member.
2009.04.02~2009.04.08, The 3rd International Conference on Language and Automata Theory and Applications (LATA 2009), 座長(Chairmanship).
2008.11.10~2008.11.12, The 15th International Symposium on String Processing and Information Retrieval (SPIRE 2008), PC Member.
2008.10.15~2011.10.17, The 3rd IAPR International Conference on Pattern Recognition in Bioinformatics (PRIB 2008), PC Member.
2008.09.01~2008.09.03, The Prague Stringology Conference 2008 (PSC2008), 座長(Chairmanship).
学会誌・雑誌・著書の編集への参加状況
2017.10~2018.07, Proc. 29th Annual Symposium on Combinatorial Pattern Matching (CPM 2018), 国際, 編集委員.
2018.03~2018.08, Proceedings of the Prague Stringology Conference 2018 (PSC 2018), 国際, 編集委員.
2017.01~2017.08, Proceedings of the Prague Stringology Conference 2017 (PSC 2017), 国際, 編集委員長.
2017.01~2017.09, Proc. 23rd International Symposium on String Processing and Information Retrieval (SPIRE 2017), 国際, 編集委員.
2016.03~2016.08, Proceedings of the Prague Stringology Conference 2016 (PSC 2016), 国際, 編集委員.
2015.11~2016.06, Proc. the 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016), 国際, 査読委員.
2015.10~2016.10, Proc. 23rd International Symposium on String Processing and Information Retrieval (SPIRE 2016), 国際, 編集委員長.
2015.03~2015.08, Proceedings of the Prague Stringology Conference 2015 (PSC 2015), 国際, 編集委員.
2014.04~2014.10, Proc. 21st International Symposium on String Processing and Information Retrieval (SPIRE 2014), 国際, 編集委員.
2014.03~2014.09, Proceedings of the Prague Stringology Conference 2014 (PSC 2014), 国際, 編集委員.
2011.10~2013.06, Special issue of Language and Automata Theory and Applications 2011 (LATA 2011), 国際, 編集委員長.
2013.03~2013.08, Proceedings of the Prague Stringology Conference 2013 (PSC 2013), 国際, 編集委員.
2012.03~2012.08, Proceedings of the Prague Stringology Conference 2012 (PSC 2012), 国際, 編集委員.
2013.04~2013.06, Proc. 20th International Symposium on String Processing and Information Retrieval (SPIRE 2013), 国際, 編集委員.
2010.10~2011.05, Proceedings of the 5th International Conference on Language and Automata Theory and Applications (LATA 2011), 国際, 編集委員長.
2008.03~2008.10, Proceedings of the 3rd IAPR International Conference on Pattern Recognition in Bioinformatics (PRIB 2008), 国際, 査読委員.
2008.03~2008.10, Proceedings of the 15th International Symposium on String Processing and Information Retrieval (SPIRE 2008), 国際, 査読委員.
2009.12~2010.03, Proceedings of Workshop on Information Retrieval, Security and Innovative Applications (RSIA 2010), 国際, 査読委員.
2009.09~2010.07, Proceedings of the 21st Annual Symposium on Combinatorial Pattern Matching (CPM 2010), 国際, 査読委員.
2010.03~2010.08, Proceedings of the Prague Stringology Conference 2010 (PSC 2010), 国際, 査読委員.
2011.03~2011.08, Proceedings of the Prague Stringology Conference 2011 (PSC 2011), 国際, 査読委員.
2011.03~2011.10, Proceedings of the 18th International Symposium on String Processing and Information Retrieval (SPIRE 2011), 国際, 査読委員.
学術論文等の審査
年度 外国語雑誌査読論文数 日本語雑誌査読論文数 国際会議録査読論文数 国内会議録査読論文数 合計
2018年度 12 
2017年度 14  22 
2016年度 10 
2015年度 10  16 
2014年度 17 
2013年度 11  14 
2012年度  
2011年度 11  17 
2010年度 13 
2009年度 13  19 
その他の研究活動
海外渡航状況, 海外での教育研究歴
LSD/LAW 2019, Japan, 2019.02~2019.02.
DSB 2019, Germany, 2019.02~2019.02.
PSC 2018, CzechRepublic, 2018.08~2018.08.
University of Tampere, Finland, 2018.01~2018.01.
CPM 2018, China, 2018.07~2018.07.
PWA 2018, Italy, 2018.07~2018.07.
Dagstuhl Seminar 18281, Germany, 2018.07~2018.07.
SOFSEM 2017, Ireland, 2017.01~2017.01.
IWOCA 2017, Australia, 2017.07~2017.07.
CPM 2017, Poland, 2017.07~2017.07.
MFCS 2017, Denmark, 2017.08~2017.08.
ISAAC 2017, Thailand, 2017.12~2017.12.
SOFSEM 2016, CzechRepublic, 2016.01~2016.01.
STACS 2016, France, 2016.02~2016.02.
CPM 2016, Israel, 2016.06~2016.07.
AxA workshop, Italy, 2016.06~2016.06.
Bioinformatics summer school, Finland, 2016.08~2016.08.
IWOCA 2016, Finland, 2016.08~2016.08.
MFCS 2016, Poland, 2016.08~2016.08.
LSD/LAW 2015, UnitedKingdom, 2015.02~2015.02.
STACS 2015, Germany, 2015.03~2015.03.
CIAC 2015, France, 2015.05~2015.05.
CPM 2015, Italy, 2015.06~2015.07.
PSC 2015, CzechRepublic, 2015.08~2015.08.
SPIRE 2015, UnitedKingdom, 2015.09~2015.09.
STACS 2014, France, 2014.03~2014.03.
CPM 2014, Russia, 2014.06~2014.06.
MFCS 2014, Hungary, 2014.08~2014.08.
LSD/LAW 2014, UnitedKingdom, 2014.02~2014.02.
STACS 2013, Germany, 2013.02~2013.02.
SPIRE 2013, Israel, 2013.10~2013.10.
CPM 2013, Germany, 2013.06~2013.06.
MFCS 2013, Austria, 2013.08~2013.08.
PSC 2013, CzechRepublic, 2013.08~2013.08.
CIAA 2013, Canada, 2013.07~2013.07.
SOFSEM 2012, CzechRepublic, 2012.01~2012.01.
CPM 2012, Finland, 2012.07~2012.07.
SPIRE 2012, Colombia, 2012.10~2012.10.
Karlsruhe Institute of Technology, Germany, 2012.06~2012.06.
AISC 2011, Australia, 2011.01~2011.01.
LATA 2011, Spain, 2011.05~2011.05.
Alignment-free Sequence Comparison Workshop, CPM 2011, Italy, 2011.06~2011.06.
Czech technical University, CzechRepublic, 2011.08~2011.08.
LATA 2010, Germany, 2010.05~2010.05.
CPM 2010, UnitedStatesofAmerica, 2010.07~2010.07.
CATS 2009, NewZealand, 2009.01~2009.01.
LATA 2009, Spain, 2009.04~2009.04.
IWOCA 2009, CzechRepublic, 2009.06~2009.07.
PDPTA 2009, UnitedStatesofAmerica, 2009.07~2009.07.
Czech technical University, CzechRepublic, 2009.08~2009.09.
CISIM 2009, India, 2009.12~2009.12.
SOFSEM 2008, SlovakRepublic, 2008.01~2008.01.
University of Tampere, Finland, 2008.07~2008.07.
Czech technical University, CzechRepublic, 2008.09~2008.09.
DS 2008, Hungary, 2008.10~2008.10.
DCC 2007, UnitedStatesofAmerica, 2007.03~2007.03.
CPM 2007, Canada, 2007.07~2007.07.
CPM 2006, Spain, 2006.07~2006.07.
Czech technical University, CzechRepublic, 2006.09~2006.09.
SPIRE 2006, UnitedKingdom, 2006.10~2006.10.
CPM 2005, Korea, 2005.07~2005.07.
FCT 2005, Germany, 2005.08~2005.08.
DS 2005, Singapore, 2005.10~2005.10.
SPIRE 2005, Argentina, 2005.11~2005.11.
WABI 2004, Norway, 2004.09~2004.09.
DS 2004, SPIRE 2004, Italy, 2004.10~2004.10.
DLT 2004, NewZealand, 2004.12~2004.12.
University of Helsinki, Finland, 2003.05~2003.05.
MFCS 2003, SlovakRepublic, 2003.08~2003.08.
University of Helsinki, Finland, 2003.09~2004.10.
Czech technical University, CzechRepublic, 2003.09~2003.09.
MFCS 2002, Poland, 2002.08~2002.08.
SPIRE 2002, Portugal, 2002.09~2002.09.
Czech technical University, CzechRepublic, 2002.09~2002.09.
DS 2002, Germany, 2002.11~2002.11.
CPM 2001, Israel, 2001.06~2001.07.
University of Liverpool, UnitedKingdom, 2001.07~2001.07.
Czech Technical University, CzechRepublic, 2001.09~2001.09.
SPIRE 2001, Chile, 2001.11~2001.11.
DS 2001, UnitedStatesofAmerica, 2001.11~2001.11.
外国人研究者等の受入れ状況
2018.05~2018.06, University of Helsinki, Russia, 外国政府・外国研究機関・国際機関.
2017.09~2017.09, University of Siegen, Germany, 外国政府・外国研究機関・国際機関.
2017.12~2017.12, Universite Laval, Canada, 日本学術振興会.
2016.07~2016.08, TU Dortmund, Germany, 日本学術振興会.
2015.09~2015.09, 2週間未満, University of Helsinki, Australia.
2013.11~2013.11, 2週間以上1ヶ月未満, University of Helsinki, Australia.
2013.03~2013.03, 2週間未満, Max-Planck Institute, Poland.
受賞
Best paper award, 34th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM2008), 2008.01.
研究資金
科学研究費補助金の採択状況(文部科学省、日本学術振興会)
2017年度~2019年度, 基盤研究(B), 代表, 高度データ構造的手法に基づく文字列情報処理問題の上下界解明.
2014年度~2017年度, 基盤研究(B), 代表, 文字列情報処理の新展開-文字列組み合わせ論と高度データ構造技術の融合-.
2011年度~2013年度, 若手研究(B), 代表, データ圧縮に基づく高速パラメタ化文字列照合技法の開発.
寄附金の受入状況
2015年度, 栢森情報科学振興財団, 栢森情報科学振興財団 研究助成.
2014年度, 栢森情報科学振興財団, 栢森情報科学振興財団 研究助成.
2013年度, 稲盛財団, 稲盛財団研究助成.
2008年度, 大川情報通信基金, 研究助成金/電子マネーシステムの情報科学的モデル化に関する研究.

九大関連コンテンツ

pure2017年10月2日から、「九州大学研究者情報」を補完するデータベースとして、Elsevier社の「Pure」による研究業績の公開を開始しました。
 
 
九州大学知的財産本部「九州大学Seeds集」