Publication List of Shunsuke Inenaga

[home in English] [home in Japanese]

Editing

  1. Shunsuke Inenaga, Combinatorial Methods for String Processing, Special Issue of Algorithms, 2021. [link]

  2. Shunsuke Inenaga, Kunihiko Sadakane, and Tetsuya Sakai, String Processing and Information Retrieval (SPIRE 2016), Lecture Notes in Computer Science 9954, Springer, October 2016. [link]

  3. Shunsuke Inenaga and Carlos Martín-Vide, Special issue of Language and Automata Theory and Applications 2011 (LATA 2011), International Journal of Computer Mathematics, 90(6), June 2013. [link]

  4. Adrian Horia Dediu, Shunsuke Inenaga, and Carlos Martín-Vide, Language and Automata Theory and Applications 2011 (LATA 2011), Lecture Notes in Computer Science 6638, Springer, May 2011. [link]

Journal Articles

  1. Yuki Yonemoto, Yuto Nakashima, Shunsuke Inenaga, and Hideo Bannai, Faster Space-Efficient STR-IC-LCS Computation, Theoretical Computer Science, 1003:114607, July 2024. [link] [arxiv]

  2. Yuta Fujishige, Yuki Tsujimaru, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda, Linear-time Computation of DAWGs, Symmetric Indexing Structures, and MAWs for Integer Alphabets, Theoretical Computer Science, 973:114093, September 2023. [link] [arxiv]

  3. Tooru Akagi, Mitsuru Funakoshi, and Shunsuke Inenaga, Sensitivity of string compressors and repetitiveness measures, Information and Computation, 291:104999, March 2023. [link] [arxiv]

  4. Katsuhito Nakashima, Noriki Fujisato, Diptarama Hendrian, Yuto Nakashima, Ryo Yoshinaka, Shunsuke Inenaga, Hideo Bannai, Ayumi Shinohara, and Masayuki Takeda, Parameterized DAWGs: Efficient constructions and bidirectional pattern searches, Theoretical Computer Science, 933:21-42, October 2022. [link] [arxiv]

  5. Tooru Akagi, Yuki Kuhara, Takuya Mieno, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, Combinatorics of minimal absent words for a sliding window, Theoretical Computer Science, 927:109-119, August 2022. [link] [arxiv]

  6. Yoshifumi Sakai and Shunsuke Inenaga, A faster reduction of the dynamic time warping distance to the longest increasing subsequence length, Algorithmica, 84:2581-2596, May 2022. [link] [arxiv]

  7. Hiroe Inoue, Yoshiaki Matsuoka, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, Factorizing Strings into Repetitions, Theory of Computing Systems, April 2022. [link]

  8. Takuya Mieno, Kiichi Watanabe, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, Palindromic trees for a sliding window and its applications, Information Processing Letters, 173:106174, January 2022. [link]

  9. Ryo Sugahara, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, Efficiently computing runs on a trie, Theoretical Computer Science, 887:143-151, October 2021. [link]

  10. Takuya Mieno, Yuta Fujishige, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, Computing Minimal Unique Substrings for a Sliding Window, Algorithmica, August 2021. [link]

  11. Hideo Bannai, Shunsuke Inenaga, and Neerja Mhaskar, Longest previous overlapping factor array, Information Processing Letters, 168:106097, June 2021. [link]

  12. Shiori Mitsuya, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, Compressed Communication Complexity of Hamming Distance, Algorithms 14(4):116, April 2021. [link] [arxiv]

  13. Shunsuke Inenaga, Towards a complete perspective on labeled tree indexing: new size bounds, efficient constructions, and beyond, Journal of Information Processing, 29:1-13, January 2021, IPSJ 60th Anniversary Best Paper. [link] [arxiv]

  14. Mitsuru Funakoshi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, Computing longest palindromic substring after single-character or block-wise edits, Theoretical Computer Science, 859(6):116-133, March 2021. [link] [arxiv]

  15. Hideo Bannai, Momoko Hirayama, Danny Hucke, Shunsuke Inenaga, Artur Jeż, and Markus Lohrey, The Smallest Grammar Problem Revisited, IEEE Transactions on Information Theory, 67(1):317-328, January 2021. [link] [arxiv]

  16. Takuya Mieno, Dominik Köppl, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, Space-efficient algorithms for computing minimal/shortest unique substrings, Theoretical Computer Science, 845:230-242, December 2020. [link] [arxiv]

  17. Kazuya Tsuruta, Dominik Köppl, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda, Grammar-compressed Self-index with Lyndon Words, IPSJ Transactions on Mathematical Modeling and its Applications, 13(2):84-92, August 2020. [link] [arxiv]

  18. Kiichi Watanabe, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda, Fast Algorithms for the Shortest Unique Palindromic Substring Problem on Run-Length Encoded Strings, Theory of Computing Systems, May 2020. [link] [arxiv]

  19. Isamu Furuya, Takuya Takagi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai and Takuya Kida, Practical Grammar Compression Based on Maximal Repeats, Algorithms, 13(4):103, April 2020. [link]

  20. Shintaro Narisada, Diptarama Hendrian, Kazuyuki Narisada, Shunsuke Inenaga, and Ayumi Shinohara, Efficient computation of longest single-arm-gapped palindromes in a string, Theoretical Computer Science, 812:160-173, April 2020. [link] [arxiv]

  21. Takuya Takagi, Shunsuke Inenaga, Hiroki Arimura, Dany Breslauer, and Diptarama Hendrian, Fully-Online Suffix Tree and Directed Acyclic Word Graph Construction for Multiple Texts, Algorithmica, 82:1346-1377, 2020. [link] [arxiv]

  22. Takaaki Nishimoto, Tomohiro I, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda, Dynamic index and LZ factorization in compressed space, Discrete Applied Mathematics, 274:116-129, March 2020. [link] [arxiv]

  23. Diptarama Hendrian, Shunsuke Inenaga, Ryo Yoshinaka, and Ayumi Shinohara, Efficient Dynamic Dictionary Matching with DAWGs and AC-automata, Theoretical Computer Science, 792:161-172, November 2019. [link] [arxiv]

  24. Yuto Nakashima, Takuya Takagi, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, On the size of the smallest alphabet for Lyndon trees, Theoretical Computer Science, 792:131-143, November 2019. [link]

  25. Hiroe Inoue, Yuto Nakashima, Takuya Mieno, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, Algorithms and combinatorial properties on shortest unique palindromic substrings, Journal of Discrete Algorithms (special issue for IWOCA 2017), 52:122-132, September 2018. [link]

  26. Heikki Hyyrö and Shunsuke Inenaga, Dynamic RLE-compressed edit distance tables under general weighted cost functions, International Journal of Foundations of Computer Science (special issue for SOFSEM 2016), 29(4):623-645, 2018. [link]

  27. 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, International Journal of Foundations of Computer Science (special issue for DLT 2015), 29(2):143-163, February 2018. [link] [arxiv]

  28. Paweł Gawrychowski, Tomohiro I, Shunsuke Inenaga, Dominik Köppl, and Florin Manea, Tighter Bounds and Optimal Algorithms for All Maximal α-gapped Repeats and Palindromes, Theory of Computing Systems (special issue for STACS 2016), 62(1):162-191, January 2018. [link]

  29. Shunsuke Inenaga and Heikki Hyyrö, A hardness result and new algorithm for the longest common palindromic subsequence problem, Information Processing Letters, 129:11-15, January 2018. [link] [arxiv]

  30. Hideo Bannai, Tomohiro I, Shunsuke Inenaga, Yuto Nakashima, Masayuki Takeda, and Kazuya Tsuruta, The "Runs" Theorem, SIAM Journal of Computing, 46(5):1501-1514, September 2017. [link] [arxiv]

  31. 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, E100-A(9):1785-1793, September 2017. [link] [arxiv]

  32. Yuto Nakashima, Takashi Okabe, Tomohiro I, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda, Inferring strings from Lyndon factorization, Theoretical Computer Science, 689:147-156, August 2017. [link]

  33. Tomohiro I, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, Faster Lyndon factorization algorithms for SLP and LZ78 compressed text, Theoretical Computer Science, 656(B):215-224, December 2016. [link]

  34. Yoshiaki Matsuoka, Takahiro Aoki, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, Generalized pattern matching and periodicity under substring consistent equivalence relations, Theoretical Computer Science, 656(B):225-233, December 2016. [link]

  35. Golnaz Badkobeh, Hideo Bannai, Keisuke Goto, Tomohiro I, Costas S. Iliopoulos, Shunsuke Inenaga, Simon J. Puglisi, and Shiho Sugimoto, Closed Factorization, Discrete Applied Mathematics, 212:23-29, October 2016. [link]

  36. Kazuyuki Narisawa, Hideharu Hiratsuka, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, Efficient Computation of Substring Equivalence Classes with Suffix Arrays, Algorithmica, August 2016. [link]

  37. Heikki Hyyrö, Kazuyuki Narisawa, and Shunsuke Inenaga, Dynamic Edit Distance Table under a General Weighted Cost Function, Journal of Discrete Algorithms, 34:2-17, September 2015. [link]

  38. Yuto Nakashima, Tomohiro I, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda, Constructing LZ78 Tries and Position Heaps in Linear Time for Large Alphabets, Information Processing Letters, 115(9):655-659, September 2015. [link]

  39. Tomohiro I, Takaaki Nishimoto, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, Compressed automata for dictionary matching, Theoretical Computer Science, 578:30-41, May 2015. [link]

  40. Tomohiro I, Wataru Matsubara, Kouji Shimohira, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Kazuyuki Narisawa, and Ayumi Shinohara, Detecting regularities on grammar-compressed strings, Information and Computation, 240:74-89, February 2015. [link]

  41. Tomohiro I, Hideo Bannai, Shunsuke Inenaga, and Masayuki Takeda, Inferring Strings from Suffix Trees and Links on a Binary Alphabet, Discrete Applied Mathematics, 163(3): 316 325, January 2014. [link]

  42. Tomohiro I, Shunsuke Inenaga, and Masayuki Takeda, Palindrome Pattern Matching, Theoretical Computer Science, 483: 162-170, April 2013. [link]

  43. Keisuke Goto, Hideo Bannai, Shunsuke Inenaga, and Masayuki Takeda, Fast q-gram mining on SLP compressed strings, Journal of Discrete Algorithms, 18: 89-99, January 2013. [link]

  44. Hideo Bannai, Travis Gagie, Tomohiro I, Shunsuke Inenaga, Gad M. Landau, and Moshe Lewenstein, An efficient algorithm to test square-freeness of strings compressed by straight-line programs, Information Processing Letters, 122(9):711-714, October 2012. [link]

  45. Shunsuke Inenaga and Hideo Bannai, Finding Characteristic Substrings from Compressed Texts, International Journal of Foundations of Computer Science, 23(2):261-280, February 2012. [link]

  46. Tomohiro I, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, Verifying and Enumerating Parameterized Border Arrays, Theoretical Computer Science, 412(50):6959-6981, November 2011. [link]

  47. Stanislav Angelov, Shunsuke Inenaga, Teemu Kivioja, and Veli Mäkinen, Finding Missing Patterns, Journal of Discrete Algorithms, 9(2):153-165, June 2011. [link]

  48. 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, April 2011.

  49. 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, October 2010. [pdf (c) IPSJ]

  50. 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, October 2010. [pdf (c) IPSJ]

  51. 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, June 2010. [link]

  52. Ryosuke Nakamura, Shunsuke Inenaga, Hideo Bannai, Takashi Funamoto, Masayuki Takeda, and Ayumi Shinohara, Linear-Time Text Compression by Longest-First Substitution, Algorithms, 2(4):1429-1448, November 2009. [link]

  53. 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, March 2009. [link] [pdf (c) Elsevier]

  54. Yasuto Higa, Hideo Bannai, Shunsuke Inenaga, and Masayuki Takeda, Reachability on Suffix Tree Graphs, International Journal of Foundations of Computer Science, 19(1):147-162, February 2008. [link]

  55. Shunsuke Inenaga, Ayumi Shinohara, Masayuki Takeda, A Fully Compressed Pattern Matching Algorithm for Simple Collage Systems, International Journal of Foundations of Computer Science, 16(6):1155-1166, December 2005. [link] [pdf (c) World Scientific]

  56. 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, 146(2):156-179, March 2005. [link] [pdf (c) Elsevier]

  57. Satoru Miyamoto, Shunsuke Inenaga, Masayuki Takeda, and Ayumi Shinohara, Ternary Directed Acyclic Word Graphs, Theoretical Compututer Science, 328(1-2):97-111, November 2004. [link] [pdf (c) Elsevier]

  58. Hideo Bannai, Shunsuke Inenaga, Ayumi Shinohara, Masayuki Takeda, and Satoru Miyano, Efficiently finding regulatory elements using correlation with gene expression, Journal of Bioinformatics and Computational Biology, 2(2):273-288, June 2004. [link] [pdf (c) World Scientific]

  59. 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, March 2004. [link] [pdf (c) Elsevier]

  60. Shunsuke Inenaga, Bidirectional Construction of Suffix Trees, Nordic Journal of Computing, 10(1):52-67, Spring 2003. [pdf (c) NJC]

  61. Kensuke Baba, Ayumi Shinohara, Masayuki Takeda, Shunsuke Inenaga, and Setsuo Arikawa, A Note on Randomized Algorithm for String Matching with Mismatches, Nordic Journal of Computing, 10(1):2-12, Spring 2003.

Peer Reviewed Conference Papers

  1. Shunsuke Inenaga, Takuya Mieno, Hiroki Arimura, Mitsuru Funakoshi and Yuta Fujishige, Computing Minimal Absent Words and Extended Bispecial Factors with CDAWG Space, Accepted for the 35th International Workshop on Combinatorial Algorithms (IWOCA 2024), July 2024. [arxiv]

  2. Mitsuru Funakoshi, Takuya Mieno, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, Computing maximal palindromes in non-standard matching models, Accepted for the 35th International Workshop on Combinatorial Algorithms (IWOCA 2024), July 2024. [arxiv]

  3. Taketo Tsujimoto, Hiroki Shibata, Takuya Mieno, Yuto Nakashima, and Shunsuke Inenaga, Computing Longest Common Subsequence under Cartesian-Tree Matching Model, Accepted for the 35th International Workshop on Combinatorial Algorithms (IWOCA 2024), July 2024. [arxiv]

  4. Hiroki Arimura, Shunsuke Inenaga, Yasuaki Kobayashi, Yuto Nakashima and Mizuki Sue, Optimally Computing Compressed Indexing Arrays Based on the Compact Directed Acyclic Word Graph, Proc. 30th edition of the annual Symposium on String Processing and Information Retrieval (SPIRE 2023), LNCS 14240, pp. 28-34, September 2023. [link] [arxiv]

  5. Kouta Okabe, Takuya Mieno, Yuto Nakashima, Shunsuke Inenaga, and Hideo Bannai, Linear-Time Computation of Generalized Minimal Absent Words of Multiple Strings, Proc. 30th edition of the annual Symposium on String Processing and Information Retrieval (SPIRE 2023), pp. 331-344, September 2023. [link] [arxiv]

  6. Kaisei Kishi, Yuto Nakashima, and Shunsuke Inenaga, Largest Repetition Factorization of Fibonacci Words, Proc. 30th edition of the annual Symposium on String Processing and Information Retrieval (SPIRE 2023), LNCS 14240, pp. 284-296, September 2023. [link]

  7. Yuki Yonemoto, Yuto Nakashima, and Shunsuke Inenaga, Computing SEQ-IC-LCS of Labeled Graphs, The Prague Stringology Conference 2023 (PSC 2023), pp. 3-17, August 2023. [link] [arxiv]

  8. Hiroto Fujimaru, Yuto Nakashima, and Shunsuke Inenaga, On Sensitivity of Compact Directed Acyclic Word Graphs, Proc. 14th International Conference on Words (WORDS 2023), LNCS 13899, pp. 168-180, June 2023. [link] [arxiv]

  9. Sara Giuliani, Shunsuke Inenaga, Zsuzsanna Liptak, Giuseppe Romana, Marinella Sciortino, and Cristian Urbina, Bit catastrophes for the Burrows-Wheeler Transform, Proc. 27th International Conference on Developments in Language Theory (DLT 2023), LNCS 13911, pp. 86-99, June 2023. [link]

  10. Yuuki Yonemoto, Yuto Nakashima, Shunsuke Inenaga, and Hideo Bannai, Space-Efficient STR-IC-LCS Computation, Proc. 48th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2023), LNCS 13878, pp. 372-384, January 2023. [link] [arxiv]

  11. Takuya Mieno, Mitsuru Funakoshi, and Shunsuke Inenaga, Computing palindromes on a trie in linear time, Proc. 33rd International Symposium on Algorithms and Computation (ISAAC 2022), 15:1-15:15, December 2022. [link] [arxiv]

  12. Laurentius Leonard, Shunsuke Inenaga, Hideo Bannai, and Takuya Mieno, Online algorithms for finding distinct substrings with length and multiple prefix and suffix conditions, Proc. 29th edition of the annual Symposium on String Processing and Information Retrieval (SPIRE 2022), LNCS 13617, pp. 24-37, November 2022. [link] [arxiv]

  13. Tooru Akagi, Kouta Okabe, Takuya Mieno, Yuto Nakashima, and Shunsuke Inenaga, Minimal Absent Words on Run-Length Encoded Strings, Proc. 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022), 27:1-27:17, June 2022. [link] [arxiv]

  14. Takuya Mieno, Shunsuke Inenaga, and Takashi Horiyama, RePair Grammars are the Smallest Grammars for Fibonacci Words, Proc. 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022), 26:1-26:17, June 2022. [link] [arxiv]

  15. Tsubasa Oizumi, Takeshi Kai, Takuya Mieno, Shunsuke Inenaga, and Hiroki Arimura, Cartesian Tree Subsequence Matching, Proc. 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022), 14:1-14:18, June 2022. [link] [arxiv]

  16. Akio Nishimoto, Noriki Fujisato, Yuto Nakashima, and Shunsuke Inenaga, Position Heaps for Cartesian-tree Matching on Strings and Tries, Proc. 28th International Symposium on String Processing and Information Retrieval (SPIRE 2021), LNCS 12944, pp. 241-254, October 2021. [link] [arxiv]

  17. Takumi Ideue, Takuya Mieno, Mitsuru Funakoshi, Yuto Nakashima, Shunsuke Inenaga, and Masayuki Takeda, On the approximation ratio of LZ-End to LZ77, Proc. 28th International Symposium on String Processing and Information Retrieval (SPIRE 2021), LNCS 12944, pp. 114-126, October 2021. [link] [arxiv]

  18. Kosuke Fujita, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, Longest Common Rollercoasters, Proc. 28th International Symposium on String Processing and Information Retrieval (SPIRE 2021), LNCS 12944, pp. 21-32, October 2021. [link]

  19. Tooru Akagi, Dominik Köppl, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Grammar Index By Induced Suffix Sorting, Proc. 28th International Symposium on String Processing and Information Retrieval (SPIRE 2021), LNCS 12944, pp. 85-99, October 2021. [link] [arxiv]

  20. Ryo Hirakawa, Yuto Nakashima, Shunsuke Inenaga, and Masayuki Takeda, Counting Lyndon Subsequences, Proc. Prague Stringology Conference 2021 (PSC 2021), pp. 53-60, August 2021. [link] [arxiv]

  21. Noriki Fujisato, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, The Parameterized Suffix Tray, Proc. 12th International Conference on Algorithms and Complexity (CIAC 2021), LNCS 12701, pp. 258-270, May 2021. [link] [arxiv]

  22. Sara Giuliani, Shunsuke Inenaga, Zsuzsanna Lipták, Nicola Prezza, Marinella Sciortino, and Anna Toffanello, Novel Results on the Number of Runs of the Burrows-Wheeler-Transform, Proc. 47th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2021), LNCS 12607, pp. 249-262, January 2021. Best Paper Award [link] [arxiv]

  23. Shunsuke Inenaga, Suffix Trees, DAWGs, and CDAWGs for Forward and Backward Tries, Proc. 14th Latin American Theoretical Informatics Symposium (LATIN 2020), LNCS 12118, pp. 194-206, December 2020. [link] [arxiv]

  24. Yoshifumi Sakai and Shunsuke Inenaga, A reduction of the dynamic time warping distance to the longest increasing subsequence length, Proc. 31st International Symposium on Algorithms and Computation (ISAAC 2020), 6:1-6:16, December 2020. [link] [arxiv]

  25. Kanaru Kutsukake, Takuya Matsumoto, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, On repetitiveness measures of Thue-Morse words, Proc. 27th International Symposium on String Processing and Information Retrieval (SPIRE 2020), LNCS 12303, pp. 213-220, October 2020. Best Paper Award [link] [arxiv]

  26. Takafumi Inoue, Shunsuke Inenaga, and Hideo Bannai, Longest Square Subsequence Problem Revisited, Proc. 27th International Symposium on String Processing and Information Retrieval (SPIRE 2020), LNCS 12303, pp. 147-154, October 2020. [link] [arxiv]

  27. Akihiro Nishi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, Towards Efficient Interactive Computation of Dynamic Time Warping Distance, Proc. 27th International Symposium on String Processing and Information Retrieval (SPIRE 2020), LNCS 12303, pp. 27-41, October 2020. [link] [arxiv]

  28. Shunsuke Inenaga, Pointer-Machine Algorithms for Fully-Online Construction of Suffix Trees and DAWGs on Multiple Strings, Proc. Prague Stringology Conference 2020 (PSC 2020), pp. 111-124, August-September 2020. [link] [arxiv]

  29. Katsuhito Nakashima, Noriki Fujisato, Diptarama Hendrian, Yuto Nakashima, Ryo Yoshinaka, Shunsuke Inenaga, Hideo Bannai, Ayumi Shinohara, and Masayuki Takeda, DAWGs for Parameterized Matching: Online Construction and Related Indexing Structures, Proc. 31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020), 26:1-26:14, June 2020. [link] [arxiv]

  30. Mitsuru Funakoshi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, and Ayumi Shinohara, Detecting k-(Sub-)Cadences and Equidistant Subsequence Occurrences, Proc. 31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020), 12:1-12:11, June 2020. [link] [arxiv]

  31. Kazuya Tsuruta, Dominik Köppl, Shunsuke Kanda, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Dynamic Trie Tailored for Fast Prefix Searches, Proc. Data Compression Conference 2020 (DCC 2020), March 2020. [link] [arxiv]

  32. Kohei Yamada, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, Faster STR-EC-LCS Computation, Proc. 46th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2020), LNCS 12011, pp. 125-135, January 2020. [link] [arxiv]

  33. Takuya Mieno, Yuki Kuhara, Tooru Akagi, Yuta Fujishige, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, Minimal Unique Substrings and Minimal Absent Words in a Sliding Window, Proc. 46th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2020), LNCS 12011, pp. 148-160, January 2020. [link] [arxiv]

  34. Yuta Fujishige, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, An improved data structure for left-right maximal generic words problem, Proc. 30th International Symposium on Algorithms and Computation (ISAAC 2019), 40:1-40:12, December 2019. [link]

  35. Noriki Fujisato, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, Direct Linear Time Construction of Parameterized Suffix and LCP Arrays for Constant Alphabets, Proc. 26th International Symposium on String Processing and Information Retrieval (SPIRE 2019), LNCS 11811, pp. 382-391, October 2019. [link] [arxiv]

  36. Kazuki Kai, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, and Tomasz Kociumaka, On Longest Common Property Preserved Substring Queries, Proc. 26th International Symposium on String Processing and Information Retrieval (SPIRE 2019), LNCS 11811, pp. 162-174, October 2019. [link] [arxiv]

  37. Takuya Mieno, Dominik Köppl, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, Compact Data Structures for Shortest Unique Substring Queries, Proc. 26th International Symposium on String Processing and Information Retrieval (SPIRE 2019), LNCS 11811, pp. 107-123, October 2019. [link] [arxiv]

  38. Golnaz Badkobeh, Hideo Bannai, Maxime Crochemore, Tomohiro I, Shunsuke Inenaga and Shiho Sugimoto, k-Abelian pattern matching: Revisited, corrected, and extended, Proc. Prague Stringology Conference 2019 (PSC 2019), August 2019.

  39. Mitsuru Funakoshi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, Computing Maximal Palindromes and Distinct Palindromes in a Trie, Proc. Prague Stringology Conference 2019 (PSC 2019), August 2019.

  40. Kiichi Watanabe, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda, Shortest Unique Palindromic Substring Queries on Run-Length Encoded Strings, Proc. 30th International Workshop on Combinatorial Algorithms (IWOCA 2019), LNCS 11638, pp. 430-441, July 2019. [link] [arxiv]

  41. Diptarama Hendrian, Takuya Takagi, and Shunsuke Inenaga, Online Algorithms for Constructing Linear-size Suffix Trie, Proc. 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019), 30:1-30:19, June 2019. [link] [arxiv].

  42. Yuki Urabe, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, On the Size of Overlapping Lempel-Ziv and Lyndon Factorizations, Proc. 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019), 29:1-29:11, June 2019. [link]

  43. Mitsuru Funakoshi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, Faster queries for longest substring palindrome after block edit, Proc. 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019), 27:1-27:13, June 2019. [link] [arxiv]

  44. Ryo Sugahara, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, Computing runs on a trie, Proc. 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019), 23:1-23:11, June 2019. [link] [arxiv].

  45. Noriki Fujisato, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, The Parameterized Position Heap of a Trie, Proc. 11th International Conference on Algorithms and Complexity (CIAC 2019), LNCS 11485, pp. 237-248, May 2019. [link] [arxiv].

  46. Isamu Furuya, Takuya Takagi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai and Takuya Kida, MR-RePair: Grammar Compression based on Maximal Repeats, Proc. Data Compression Conference 2019 (DCC 2019), March 2019. [link] [arxiv]

  47. Yuki Kuhara, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, Recovering, Counting and Enumerating Strings from Forward and Backward Suffix Arrays, Proc. 25th International Symposium on String Processing and Information Retrieval (SPIRE 2018), LNCS 11147, pp. 254-267, October 2018. [link]

  48. Keisuke Goto, Tomohiro I, Hideo Bannai and Shunsuke Inenaga, Block Palindromes: A New Generalization of Palindromes, Proc. 25th International Symposium on String Processing and Information Retrieval (SPIRE 2018), LNCS 11147, pp. 183-190, October 2018. [link] [arxiv]

  49. Noriki Fujisato, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, Right-to-left Online Construction of Parameterized Position Heaps, Proc. Prague Stringology Conference 2018 (PSC 2018), pp. 91-102, August 2018. [link].

  50. Akihiro Nishi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, O(n log n)-time Text Compression by LZ-style Longest First Substitution, Proc. Prague Stringology Conference 2018 (PSC 2018), pp. 12-26, August 2018. [link].

  51. Isamu Furuya, Yuto Nakashima, Tomohiro I, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda, Lyndon Factorization of Grammar Compressed Texts Revisited, Proc. 29th Annual Symposium on Combinatorial Pattern Matching (CPM 2018), 24:1-24:10, July 2018. [link]

  52. Yuki Urabe, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, Longest Lyndon Substring After Edit, Proc. 29th Annual Symposium on Combinatorial Pattern Matching (CPM 2018), 19:1-19:10, July 2018. [link].

  53. Takafumi Inoue, Shunsuke Inenaga, Heikki Hyyrö, Hideo Bannai, and Masayuki Takeda, Computing longest common square subsequences, Proc. 29th Annual Symposium on Combinatorial Pattern Matching (CPM 2018), 15:1-15:13, July 2018. [link]

  54. Mitsuru Funakoshi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, Longest substring palindrome after edit, Proc. 29th Annual Symposium on Combinatorial Pattern Matching (CPM 2018), 12:1-12:14, July 2018. [link]

  55. Kotaro Aoyama, Yuto Nakashima, Tomohiro I, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda, Faster Online Elastic Degenerate String Matching, Proc. 29th Annual Symposium on Combinatorial Pattern Matching (CPM 2018), 9:1-9:10, July 2018. [link]

  56. Yuta Fujishige, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, Almost Linear Time Computation of Maximal Repetitions in Run Length Encoded Strings, Proc. 28th International Symposium on Algorithms and Computation (ISAAC 2017), 33:1-33:12, December 2017. [link]

  57. 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), LNCS 10508, pp. 304-316, September 2017. [link] [arxiv]

  58. 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), LNCS 10508, pp.271-277, September 2017. [link] [arxiv]

  59. 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), LNCS 10508, pp. 51-67, September 2017. [link] [arxiv]

  60. 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:1-10:15, August 2017. [link][arxiv]

  61. Yuto Nakashima, Takuya Takagi, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda, On Reverse Engineering the Lyndon Tree, Proc. Prague Stringology Conference 2017 (PSC 2017), pp. 108-117, Ausugt 2017. [link]

  62. Yuto Nakashima, Hiroe Inoue, Takuya Mieno, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda, Shortest Unique Palindromic Substring Queries in Optimal Time, Proc. 28th International Workshop on Combinatorial Algorithms (IWOCA 2017), LNCS 10765, pp. 397-408, 2018. [link][arxiv]

  63. Shiho Sugimoto, Naoki Noda, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda, Computing Abelian string regularities based on RLE, Proc. 28th International Workshop on Combinatorial Algorithms (IWOCA 2017), LNCS 10765, pp. 420-431, 2018. [link] [arxiv]

  64. Takuya Mieno, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda. Tight bounds on the maximum number of shortest unique substrings, Proc. 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017), 24:1-24:11, July 2017. [link] [arxiv]

  65. Hideo Bannai, Shunsuke Inenaga, and Dominik Köppl. Computing All Distinct Squares in Linear Time for Integer Alphabets, Proc. 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017), 22:1-22:18, July 2017. [link] [arxiv]

  66. Keita Kuboi, Yuta Fujishige, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda. Faster STR-IC-LCS computation via RLE, Proc. 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017), 20:1-20:12, July 2017. [link] [arxiv]

  67. Shintaro Narisada, Diptarama, Kazuyuki Narisawa, Shunsuke Inenaga, and Ayumi Shinohara, Computing longest single-arm-gapped palindromes in a string, Proc. 43rd International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2017), pp. 375-386, January 2017. [link] [arxiv]

  68. Yohei Ueki, Diptarama, Masatoshi Kurihara, Yoshiaki Matsuoka, Kazuyuki Narisawa, Ryo Yoshinaka, Hideo Bannai, Shunsuke Inenaga, and Ayumi Shinohara, Longest Common Subsequence in at Least k Length Order-isomorphic Substrings, Proc. 43rd International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2017), pp. 363-374, January 2017. [link] [arxiv]

  69. Hiroe Inoue, Yoshiaki Matsuoka, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, Computing Smallest and Largest Repetition Factorizations in O(n log n) time, Proc. Prague Stringology Conference 2016 (PSC 2016), pp. 135-145, August 2016. [link]

  70. Takaaki Nishimoto, Tomohiro I, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda, Dynamic index and LZ factorization in compressed space, Proc. Prague Stringology Conference 2016 (PSC 2016), pp. 153-171, August 2016. [link]

  71. Yuta Fujishige, Yuki Tsujimaru, Shunsuke Inenaga, Hideo Bannai and 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), 38:1-38:14, August 2016. [link]

  72. Takuya Mieno, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda, Shortest Unique Substring Queries on Run-Length Encoded Strings, Proc. the 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016), 69:1-69:11, August 2016. [link]

  73. Takaaki Nishimoto, Tomohiro I, Shunsuke Inenaga, Hideo Bannai and 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), 72:1-72:15, August 2016. [link] [arxiv]

  74. Takuya Takagi, Shunsuke Inenaga, Kunihiko Sadakane, and Hiroki Arimura, Packed Compact Tries: A Fast and Efficient Data Structure for Online String Processing, Proc. the 27th International Workshop on Combinatorial Algorithms (IWOCA 2016), LNCS 9843, pp. 213-225, August 2016. [link] [arxiv]

  75. Yuta Fujishige, Michitaro Nakamura, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda, Finding gapped palindromes online, Proc. the 27th International Workshop on Combinatorial Algorithms (IWOCA 2016), LNCS 9843, pp. 191-202, August 2016. [link]

  76. Takuya Takagi, Shunsuke Inenaga, and Hiroki Arimura, Fully-online construction of suffix trees for multiple texts, Proc. the 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016), 22:1-22:13, June 2016. [link] [arxiv]

  77. Yuka Tanimura, Tomohiro I, Hideo Bannai, Shunsuke Inenaga, Simon J. Puglisi, and Masayuki Takeda, Deterministic sub-linear space LCE data structures with efficient construction, Proc. the 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016), pp. 1:1-1:10, June 2016. [link] [arxiv]

  78. Yoshiaki Matsuoka, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, and Florin Manea, Factorizing a string into squares in linear time, Proc. the 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016), 27:1-27:12, June 2016. [link]

  79. Paweł Gawrychowski, Tomohiro I, Shunsuke Inenaga, Dominik Köppl, and Florin Manea, Efficiently Finding All Maximal α-gapped Repeats, Proc. the 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016), pp.39:1-39:14, February 2016. [link] [A full version is available at arxiv]

  80. Heikki Hyyrö and Shunsuke Inenaga, Compacting a dynamic edit distance table by RLE compression, Proc. the 42nd International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2016), LNCS 9587, pp. 302-313, January 2016. [link]

  81. Makoto Nishida, Tomohiro I, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda, Inferring Strings from Full Abelian Periods, Proc. the 26th International Symposium on Algorithms and Computation (ISAAC 2015), LNCS 9472, pp. 768-779, December 2015. [link]

  82. Yuka Tanimura, Yuta Fujishige, Tomohiro I, Shunsuke Inenaga, Hideo Bannai and 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), Lecture Notes in Computer Science 9309, pp. 124-136, September 2015. [link]

  83. Hideo Bannai, Shunsuke Inenaga, Tomasz Kociumaka, Arnaud Lefebvre, Jakub Radoszewski, Wojciech Rytter, Shiho Sugimoto and Tomasz Waleń, Efficient Algorithms for Longest Closed Factor Array, Proc. the 22nd Symposium on String Processing and Information Retrieval (SPIRE 2015), Lecture Notes in Computer Science 9309, pp. 95-102, September 2015. [link]

  84. Takaaki Nishimoto, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda, Computing Left-Right Maximal Generic Words, Proc. Prague Stringology Conference 2015 (PSC 2015), pp. 5-16, August 2015. [link]

  85. 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), Lecture Notes in Computer Science 9168, pp. 85-96, July 2015. [link] [arxiv]

  86. Keisuke Goto, Hideo Bannai, Shunsuke Inenaga, and Masayuki Takeda, LZD Factorization: Simple and Practical Online Grammar Compression with Variable-to-Fixed Encoding, In Proc. the 26th Annual Symposium on Combinatorial Pattern Matching (CPM 2015), Lecture Notes in Computer Science 9133, pp. 219-230, June-July 2015. [link]

  87. Yoshiaki Matsuoka, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, Semi-dynamic compact index for short patterns and succinct van Emde Boas tree, In Proc. the 26th Annual Symposium on Combinatorial Pattern Matching (CPM 2015), Lecture Notes in Computer Science 9133, pp. 355-366, June-July 2015. [link]

  88. Yuya Tamakoshi, Keisuke Goto, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, An opportunistic text indexing structure based on run length encoding, In Proc. the 9th International Conference on Algorithms and Complexity (CIAC 2015), Lecture Notes in Computer Science 9079, pp. 390-402, May 2015. [link]

  89. Hideo Bannai, Tomohiro I, Shunsuke Inenaga, Yuto Nakashima, Masayuki Takeda, and Kazuya Tsuruta, A new characterization of maximal repetitions by Lyndon trees, In Proc. ACM-SIAM Symposium on Discrete Algorithms 2015 (SODA 2015), pp. 562-571, January 2015. [link]

  90. Shohei Matsuda, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, Computing Abelian Covers and Abelian Runs, In Proc. Prague Stringology Conference 2014 (PSC 2014), pp. 43-51, September 2014. [link]

  91. Golnaz Badkobeh, Hideo Bannai, Keisuke Goto, Tomohiro I, Costas S. Iliopoulos, Shunsuke Inenaga, Simon J. Puglisi, and Shiho Sugimoto, Closed Factorization, In Proc. Prague Stringology Conference 2014 (PSC 2014), pp. 162-168, September 2014. [link]

  92. Yuto Nakashima, Takashi Okabe, Tomohiro I, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda, Inferring strings from Lyndon factorization, In Proc. the 39th International Symposium on Mathematical Foundations of Computer Science (MFCS 2014), Lecture Notes in Computer Science 8635, pp. 565-576, August 2014. [link]

  93. Tomohiro I, Shiho Sugimoto, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda, Computing Palindromic Factorizations and Palindromic Covers On-line, In Proc. the 25th Annual Symposium on Combinatorial Pattern Matching (CPM 2014), Lecture Notes in Computer Science 8486, pp. 150-161, June 2014. [link]

  94. Jun'ichi Yamamoto, Tomohiro I, Hideo Bannai, Shunsuke Inenaga, and Masayuki Takeda, Faster Compact On-Line Lempel-Ziv Factorization, In Proc. the 31st Symposium on Theoretical Aspects of Computer Science (STACS 2014), pp. 675-686, March 2014. [link]

  95. Kazuya Tsuruta, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, Shortest Unique Substrings Queries in Optimal Time, In Proc. the 40th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2014), Lecture Notes in Computer Science 8327, pp 503-513, January 2014. [link]

  96. Tomohiro I, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda, Faster Lyndon Factorization Algorithms for SLP and LZ78 Compressed Text, In Proc. the 20th Symposium on String Processing and Information Retrieval (SPIRE 2013), Lecture Notes in Computer Science 8214, pp. 174-185, October 2013. [link]

  97. Shiho Sugimoto, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, Computing Reversed Lempel-Ziv Factorization Online, In Proc. the Prague Stringology Conference 2013 (PSC 2013), pp. 107-118, August 2013. [link]

  98. Tomohiro I, Wataru Matsubara, Kouji Shimohira, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Kazuyuki Narisawa, Ayumi Shinohara, Detecting Regularities on Grammar-compressed Strings, In Proc. the 38th International Symposium on Mathematical Foundations of Computer Science (MFCS 2013), Lecture Notes in Computer Science 8087, pp. 571-582, August 2013. [link] [arxiv]

  99. Tomohiro I, Takaaki Nishimoto, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda, Compressed Automata for Dictionary Matching, In Proc. the 18th International Conference on Implementation and Application of Automata (CIAA 2013), Lecture Notes in Computer Science 7982, pp. 319-330, July 2013. [link]

  100. Hideo Bannai, Paweł Gawrychowski, Shunsuke Inenaga, and Masayuki Takeda, Converting SLP to LZ78 in almost linear time, In Proc. 24th Annual Symposium on Combinatorial Pattern Matching (CPM 2013), Lecture Notes in Computer Science 7922, pp. 38-49, June 2013. [link]

  101. Tomohiro I, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda, Efficient Lyndon factorization of grammar compressed text, In Proc. 24th Annual Symposium on Combinatorial Pattern Matching (CPM 2013), Lecture Notes in Computer Science 7922, pp. 153-164, June 2013. [link]

  102. Toshiya Tanaka, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, Computing convolution on grammar-compressed text, In Proc. Data Compression Conference 2013 (DCC 2013), IEEE Computer Society Press, pp. 451-460, March 2013. [link] [preprint]

  103. Yuya Tamakoshi, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, From Run Length Encoding to LZ78 and Back Again, In Proc. Data Compression Conference 2013 (DCC 2013), pp. 143-152, IEEE Computer Society Press, March 2013. [link]

  104. Takashi Katsura, Kazuyuki Narisawa, Ayumi Shinohara, Hideo Bannai, and Shunsuke Inenaga, Permuted Pattern Matching on Multi-Track Strings, In Proc. the 39th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2013), Lecture Notes in Computer Science 7741, pp. 280-291, Springer-Verlag, January 2013. [link]

  105. Yuto Nakashima, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, The Position Heap of a Trie, In Proc. the 19th Symposium on String Processing and Information Retrieval (SPIRE 2012), Lecture Notes in Computer Science 7608, pp. 360-371, Springer-Verlag, October 2012. [link]

  106. Hideo Bannai, Shunsuke Inenaga, and Masayuki Takeda, Efficient LZ78 Factorization of Grammar Compressed Text, In Proc. the 19th Symposium on String Processing and Information Retrieval (SPIRE 2012), Lecture Notes in Computer Science 7608, pp. 86-98, Springer-Verlag, October 2012. [link]

  107. Keisuke Goto, Hideo Bannai, Shunsuke Inenaga, and Masayuki Takeda, Speeding-up q-gram mining on grammar-based compressed texts, In Proc. the 23rd Annual Symposium on Combinatorial Pattern Matching (CPM 2012), Lecture Notes in Computer Science 7354, pp. 220-231, Springer-Verlag, July 2012. [link]

  108. Keisuke Goto, Hideo Bannai, Shunsuke Inenaga, and Masayuki Takeda, Computing q-gram Non-overlapping Frequencies on SLP Compressed Texts, In Proc. the 38th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2012), Lecture Notes in Computer Science 7147, pp. 301-312, Springer-Verlag, January 2012. [link]

  109. Keisuke Goto, Hideo Bannai, Shunsuke Inenaga, and Masayuki Takeda, Fast q-gram Mining on SLP Compressed Strings, In Proc. the 18th Symposium on String Processing and Information Retrieval (SPIRE 2011), Lecture Notes in Computer Science 7024, pp. 278-289, Springer-Verlag, October 2011. [link]

  110. Kouji Shimohira, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, Computing Longest Common Substring/Subsequence of Non-linear Texts, In Proc. The Prague Stringology Conference 2011 (PSC 2011), pp. 197-208, Czech Technical University, August 2011. [link]

  111. Tomohiro I, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, Inferring Strings from Suffix Trees and Links on a Binary Alphabet, In Proc. The Prague Stringology Conference 2011 (PSC 2011), pp. 121-131, Czech Technical University, August 2011. [link]

  112. Takanori Yamamoto, Hideo Bannai, Shunsuke Inenaga and Masayuki Takeda, Faster Subsequence and Don't-Care Pattern Matching on Compressed Texts, In Proc. the 22nd Annual Symposium on Combinatorial Pattern Matching (CPM 2011), Lecture Notes in Computer Science 6661, pp. 309-322, Springer-Verlag, June 2011. [link] [pdf (c) Springer-Verlag]

  113. Tomohiro I, Shunsuke Inenaga and Masayuki Takeda, Palindrome Pattern Matching, In Proc. the 22nd Annual Symposium on Combinatorial Pattern Matching (CPM 2011), Lecture Notes in Computer Science 6661, pp. 232-245, Springer-Verlag, June 2011. [link] [pdf (c) Springer-Verlag]

  114. Toru Nakamura, Shunsuke Inenaga, Daisuke Ikeda, Kensuke Baba, and Hiroto Yasuura, An Anonymous Authentication Protocol with Single-database PIR, In Proc. Australasian Information Security Conference 2011 (AISC 2011), CRPIT Series Vol. 116, pp. 3-8, January 2011. [link]

  115. Tomohiro I, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda, Counting and Verifying Maximal Palindromes, In Proc. the 17th Symposium on String Processing and Information Retrieval (SPIRE 2010), Lecture Notes in Computer Science 6393, pp. 135-146, Springer-Verlag, October 2010. [link] [pdf (c) Springer-Verlag]

  116. Tomohiro I, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda, Verifying a Parameterized Border Array in O(n1.5) Time, In Proc. the 21st Annual Symposium on Combinatorial Pattern Matching (CPM 2010), Lecture Notes in Computer Science (LNCS 6129), pp. 238-250, Springer-Verlag, June 2010. [link] [pdf (c) Springer-Verlag]

  117. Toru Nakamura, Shunsuke Inenaga, Daisuke Ikeda, Kensuke Baba, and Hiroto Yasuura, An Identifiable yet Unlinkable Authentication System with Smart Cards for Multiple Services, In Proc. The 2010 International Conference on Computational Science and Its Applications (ICCSA 2010), Lecture Notes in Computer Science (LNCS 6019), pp. 236-251, Springer-Verlag, March 2010. [link] [pdf (c) Springer-Verlag]

  118. Heikki Hyyrö, Kazuyuki Narisawa, and Shunsuke Inenaga, Dynamic Edit Distance Table under a General Weighted Cost Function, In Proc. 36th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2010), Lecture Notes in Computer Science (LNCS 5901), pp. 515-527, Springer-Verlag, January 2010. [link] [pdf (c) Springer-Verlag]

  119. 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), pp. 902-907, IEEE, December 2009. [link]

  120. Shunsuke Inenaga and Hideo Bannai, Finding Characteristic Substrings from Compressed Texts, In Proc. The Prague Stringology Conference 2009 (PSC 2009), pp. 40-54, Czech Technical University, August-September 2009. [link]

  121. Toru Nakamura, Shunsuke Inenaga, Daisuke Ikeda, Kensuke Baba, and Hiroto Yasuura, Anonymous Authentication Systems Based on Private Information Retrieval, In Proc. 1st International Conference on Networked Digital Technologies (NDT 2009), pp. 53-58, IEEE Computer Society, July 2009. [link] [pdf (c) IEEE Computer Society]

  122. Tomomi Yamasaki, Shunsuke Inenaga, Daisuke Ikeda, and Hiroto Yasuura, Modeling Costs of Access Control with Various Key Management Systems, In Proc. The 2009 International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA 2009), pp. 676-682, CSREA Press, July 2009. [pdf (c) CSREA Press]

  123. Tomohiro I, Satoshi Deguchi, Hideo Bannai, Shunsuke Inenaga, and Masayuki Takeda, Lightweight Parameterized Suffix Array Construction, In Proc. 20th International Workshop on Combinatorial Algorithms (IWOCA 2009), Lecture Notes in Computer Science (LNCS 5874), pp. 312-323, Springer-Verlag, June-July 2009. [link] [pdf (c) Springer-Verlag]

  124. Tomohiro I, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda, Counting Parameterized Border Arrays for a Binary Alphabet, In Proc. 3rd International Conference on Language and Automata Theory and Applications (LATA 2009), Lecture Notes in Computer Science (LNCS 5457), pp. 422-433, Springer-Verlag, April 2009. [link] [pdf (c) Springer-Verlag]

  125. Wataru Matsubara, Shunsuke Inenaga, and Ayumi Shinohara, Testing Square-Freeness of Strings Compressed by Balanced Straight Line Program, In Proc. 15th Computing: The Australasian Theory Symposium (CATS 2009), CRPIT Series Vol. 94, pp. 19-28, January 2009. [link]

  126. Kazuyuki Narisawa, Hideo Bannai, Kohei Hatano, Shunsuke Inenaga, and Masayuki Takeda, String Kernels Based on Variable-Length-Don't-Care Patterns, In Proc. 11th International Conference on Discovery Science (DS 2008), Lecture Notes in Artificial Intelligence (LNAI 5255), pp. 308-318, Springer-Verlag, October 2008. [link] [pdf (c) Springer-Verlag]

  127. Satoshi Deguchi, Fumihito Higashijima, Hideo Bannai, Shunsuke Inenaga, and Masayuki Takeda, Parameterized Suffix Arrays for Binary Strings, In Proc. The Prague Stringology Conference 2008 (PSC 2008), pp. 84-94, Czech Technical University, September 2008. [link]

  128. Wataru Matsubara, Shunsuke Inenaga, Akira Ishino, Ayumi Shinohara, Tomoyuki Nakamura, and Kazuo Hashimoto, Computing longest common substring and all palindromes from compressed strings, In Proc. 34th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2008), Lecture Notes in Computer Science (LNCS 4910), pp. 364-375, Springer-Verlag, January 2008. [link] [pdf (c) Springer-Verlag]

  129. Kazuyuki Narisawa, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, Efficient Computation of Substring Equivalence Classes with Suffix Arrays, In Proc. 18th Annual Symposium on Combinatorial Pattern Matching (CPM 2007), Lecture Notes in Computer Science (LNCS 4580), pp. 340-351, Springer-Verlag, July 2007. [link] [pdf (c) Springer-Verlag]

  130. Ryosuke Nakamura, Hideo Bannai, Shunsuke Inenaga, and Masayuki Takeda, Simple Linear-Time Off-Line Text Compression by Longest-First Substitution, In Proc. Data Compression Conference 2007 (DCC 2007), pp. 123-132, IEEE Computer Society Press, March 2007. [link] [pdf (c) IEEE Computer Society]

  131. Yasuto Higa, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, A New Family of String Classifiers Based on Local Relatedness, In Proc. 9th International Conference on Discovery Science (DS 2006), Lecture Notes in Artificial Intelligence (LNAI 4265), pp. 114-124, Springer-Verlag, October 2006. [link] [pdf (c) Springer-Verlag]

  132. Shunsuke Inenaga and Masayuki Takeda, Sparse Directed Acyclic Word Graphs, In Proc. 13th International Symposium on String Processing and Information Retrieval (SPIRE 2006), Lecture Notes in Computer Science (LNCS 4209), pp. 61-73, Springer-Verlag, October 2006. [link] [pdf (c) Springer-Verlag]

  133. Yasuto Higa, Hideo Bannai, Shunsuke Inenaga, and Masayuki Takeda, Reachability on Suffix Tree Graphs, In Proc. The Prague Stringology Conference 2006 (PSC 2006), pp. 212-225, Czech Technical University, August 2006. [link] [pdf]

  134. Shunsuke Inenaga and Masayuki Takeda, Sparse Compact Directed Acyclic Word Graphs, In Proc. The Prague Stringology Conference 2006 (PSC 2006), pp. 195-211, Czech Technical University, August 2006. [link] [pdf]

  135. Shunsuke Inenaga and Masayuki Takeda, On-line Linear-time Construction of Word Suffix Trees, In Proc. 17th Annual Symposium on Combinatorial Pattern Matching (CPM 2006), Lecture Notes in Computer Science (LNCS 4009), pp. 60-71, Springer-Verlag, July 2006. [link] [pdf (c) Springer-Verlag]

  136. Stanislav Angelov and Shunsuke Inenaga, Composite Pattern Discovery for PCR Application, In Proc. 12th International Symposium on String Processing and Information Retrieval (SPIRE 2005), Lecture Notes in Computer Science (LNCS 3772), pp. 167-178, Springer-Verlag, November 2005. [link] [pdf (c) Springer-Verlag]

  137. Hideo Bannai, Kohei Hatano, Shunsuke Inenaga, and Masayuki Takeda, Practical Algorithms for Pattern Based Linear Regression, In Proc. 8th International Conference on Discovery Science (DS 2005), Lecture Notes in Artificial Intelligence (LNAI 3735), pp. 44-56, Springer-Verlag, October 2005. [link] [pdf (c) Springer-Verlag]

  138. Yusuke Ishida, Shunsuke Inenaga, Ayumi Shinohara, and Masayuki Takeda, Fully Incremental LCS Computation, In Proc. 15th International Symposium on Fundamentals of Computation Theory (FCT 2005), Lecture Notes in Computer Science (LNCS 3623), pp. 563-574, Springer-Verlag, August 2005. [link] [pdf (c) Springer-Verlag]

  139. Shunsuke Inenaga, Ayumi Shinohara, and Masayuki Takeda, An Efficient Pattern Matching Algorithm on a Subclass of Context Free Grammars, In Proc. Eighth International Conference on Developments in Language Theory (DLT 2004), Lecture Notes in Computer Science (LNCS 3340), pp. 225-236, Springer-Verlag, December 2004. [link] [pdf (c) Springer-Verlag]

  140. 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, In Proc. The 7th International Conference on Discovery Science (DS 2004), Lecture Notes in Artificial Intelligence (LNAI 3245), pp. 32-46, Springer-Verlag, October 2004. [link] [pdf (c) Springer-Verlag]

  141. Shunsuke Inenaga, Teemu Kivioja, and Veli Mäkinen, Finding Missing Patterns, In Proc. 4th Workshop on Algorithms in Bioinformatics (WABI 2004), Lecture Notes in Bioinformatics (LNBI 3240), pp. 461-474, Springer-Verlag, September 2004. [link] [pdf (c) Springer-Verlag]

  142. Shunsuke Inenaga, Ayumi Shinohara, and Masayuki Takeda, A Fully Compressed Pattern Matching Algorithm for Simple Collage Systems, In Proc. The Prague Stringology Conference 2004 (PSC 2004), pp. 98-113, Czech Technical University, August-September 2004. [link] [pdf]

  143. Masayuki Takeda, Shunsuke Inenaga, Hideo Bannai, Ayumi Shinohara, and Setsuo Arikawa, Discovering Most Classificatory Patterns for Very Expressive Pattern Classes, In Proc. The 6th International Conference on Discovery Science (DS 2003), Lecture Notes in Artificial Intelligence (LNAI 2843), pp. 486-493, Springer-Verlag, October 2003. [link] [pdf (c) Springer-Verlag]

  144. Shunsuke Inenaga, Takashi Funamoto, Masayuki Takeda, and Ayumi Shinohara, Linear-Time Off-Line Text Compression by Longest-First Substitution, In Proc. 10th International Symposium on String Processing and Information Retrieval (SPIRE 2003), Lecture Notes in Computer Science (LNCS 2857), pp. 137-152, Springer-Verlag,October 2003. [link] [pdf (c) Springer-Verlag]

  145. Hideo Bannai, Shunsuke Inenaga, Ayumi Shinohara, and Masayuki Takeda, Inferring Strings from Graphs and Arrays, In Proc. 28th International Symposium on Mathematical Foundations of Computer Science (MFCS 2003), Lecture Notes in Computer Science (LNCS 2747), pp. 208-217, Springer-Verlag, August 2003. [link] [pdf (c) Springer-Verlag]

  146. Satoru Miyamoto, Shunsuke Inenaga, Masayuki Takeda, and Ayumi Shinohara, Ternary Directed Acyclic Word Graphs, In Proc. Eighth International Conference on Implementation and Application of Automata (CIAA 2003), Lecture Notes in Computer Science (LNCS 2759), pp. 121-130, Springer-Verlag, July 2003. [link] [pdf (c) Springer-Verlag]

  147. Hideo Bannai, Shunsuke Inenaga, Ayumi Shinohara, Masayuki Takeda, and Satoru Miyano, A String Pattern Regression Algorithm and Its Application to Pattern Discovery in Long Introns, In Proc. The 13th International Conference on Genome Informatics (GIW 2002), pp. 3-11, Universal Academy Press, December 2002. [link] [pdf (c) Japanese Society for Bioinformatics]

  148. Shunsuke Inenaga, Hideo Bannai, Ayumi Shinohara, Masayuki Takeda, and Setsuo Arikawa, Discovering Best Variable-Length-Don't-Care Patterns, In Proc. The Fifth International Conference on Discovery Science (DS 2002), Lecture Notes in Computer Science (LNCS 2534), pp. 86-97, Springer-Verlag, November 2002. [link] [pdf (c) Springer-Verlag]

  149. Shunsuke Inenaga, Bidirectional Construction of Suffix Trees, In Proc. The Prague Stringology Conference 2002 (PSC 2002), pp. 75-87, Czech Technical University, September 2002. [link] [pdf]

  150. Kensuke Baba, Ayumi Shinohara, Masayuki Takeda, Shunsuke Inenaga, and Setsuo Arikawa, A Note on Randomized Algorithm for String Matching with Mismatches, In Proc. The Prague Stringology Conference 2002 (PSC 2002), pp. 9-17, Czech Technical University, September 2002. [link]

  151. Shunsuke Inenaga, Ayumi Shinohara, Masayuki Takeda, and Setsuo Arikawa, Compact Directed Acyclic Word Graphs for a Sliding Window, In Proc. 9th International Symposium on String Processing and Information Retrieval (SPIRE 2002), Lecture Notes in Computer Science (LNCS 2476), pp. 310-324, Springer-Verlag, September 2002. [link] [pdf (c) Springer-Verlag]

  152. Shunsuke Inenaga, Ayumi Shinohara, Masayuki Takeda, Hideo Bannai, and Setsuo Arikawa, Space-Economical Construction of Index Structures for All Suffixes of a String, In Proc. 27th International Symposium on Mathematical Foundation of Computer Science (MFCS 2002), Lecture Notes in Computer Science (LNCS 2420), pp. 341-352, Springer-Verlag, August 2002. [link] [pdf (c) Springer-Verlag]

  153. Shunsuke Inenaga, Masayuki Takeda, Ayumi Shinohara, Hiromasa Hoshino, and Setsuo Arikawa, The Minimum DAWG for All Suffixes of a String and Its Applications, In Proc. 13th Annual Symposium on Combinatorial Pattern Matching (CPM 2002), Lecture Notes in Computer Science (LNCS 2373), pp. 153-167, Springer-Verlag, July 2002, [link] [pdf (c) Springer-Verlag]

  154. Masahiro Hirao, Shunsuke Inenaga, Ayumi Shinohara, Masayuki Takeda, and Setsuo Arikawa, A Practical Algorithm to Find the Best Episode Patterns, In Proc. The Fourth International Conference on Discovery Science (DS 2001), Lecture Notes in Artificial Intelligence (LNAI 2226), pp. 435-440, Springer-Verlag, November 2001. [link] [pdf (c) Springer-Verlag]

  155. Shunsuke Inenaga, Hiromasa Hoshino, Ayumi Shinohara, Masayuki Takeda, and Setsuo Arikawa, On-Line Construction of Symmetric Compact Directed Acyclic Word Graphs, In Proc. 8th International Symposium on String Processing and Information Retrieval (SPIRE 2001), pp. 96-110, IEEE Computer Society, November 2001. [link] [pdf (c) IEEE Computer Society]

  156. Shunsuke Inenaga, Hiromasa Hoshino, Ayumi Shinohara, Masayuki Takeda, and Setsuo Arikawa, Construction of the CDAWG for a Trie, In Proc. The Prague Stringology Conference 2001 (PSC 2001), pp. 37-48, Czech Technical University, September 2001. [link] [pdf]

  157. Shunsuke Inenaga, Hiromasa Hoshino, Ayumi Shinohara, Masayuki Takeda, Setsuo Arikawa, Giancarlo Mauri, and Giulio Pavesi, On-Line Construction of Compact Directed Acyclic Word Graphs, In Proc. 12th Annual Symposium on Combinatorial Pattern Matching (CPM 2001), Lecture Notes in Computer Science (LNCS 2089), pp. 169-180, Springer-Verlag, July 2001. [link] [pdf (c) Springer-Verlag]

Reports

  1. Shiho Sugimoto, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, Finding Absent Words from Grammar Compressed Strings, In the Festschrift for Bořivoj Melichar, August 2012. [link]

  2. Wataru Matsubara, Shunsuke Inenaga, and Ayumi Shinohara, An Efficient Algorithm to Test Square-Freeness of Strings Compressed by Balanced Straight Line Program, In Dagstuhl Seminar Proceedings 08261, November 2008. [link]

  3. Ayumi Shinohara, Masayuki Takeda, Setsuo Arikawa, Masahiro Hirao, Hiromasa Hoshino, and Shunsuke Inenaga, Finding Best Patterns Practically, In Progress in Discovery Science (Final Report of the Japanese Discovery Science), Lecture Notes in Artificial Intelligence (LNAI 2281), pp. 307-317, Springer-Verlag, 2002. [link] [pdf (c) Springer-Verlag]

Theses

  1. Shunsuke Inenaga, String Processing Algorithms, PhD Thesis, Department of Informatics, Kyushu University, March 2003. [pdf]

  2. Shunsuke Inenaga, On Data Structures for String Searching Problems, Master Thesis, Department of Informatics, Kyushu University, February 2002.
[home in English] [home in Japanese]