Publication List of Shunsuke Inenaga

[home in English] [home in Japanese]

Editing

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

  2. 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]

  3. 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. Takuya Takagi, Shunsuke Inenaga, Hiroki Arimura, Dany Breslauer, and Diptarama Hendrian, Fully-Online Suffix Tree and Directed Acyclic Word Graph Construction for Multiple Texts, Accepted for Algorithmica. [arxiv]

  2. Shintaro Narisada, Diptarama Hendrian, Kazuyuki Narisada, Shunsuke Inenaga, and Ayumi Shinohara, Efficient computation of longest single-arm-gapped palindromes in a string, Accepted for Theoretical Computer Science. [arxiv]

  3. Takaaki Nishimoto, Tomohiro I, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda, Dynamic index and LZ factorization in compressed space, Accepted for Dicrete Applied Mathematics (special issue for PSC 2016) [link] [arxiv]

  4. 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]

  5. 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]

  6. 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]

  7. 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]

  8. 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]

  9. 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]

  10. 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]

  11. 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]

  12. 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]

  13. 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]

  14. 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]

  15. 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]

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

  17. 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]

  18. 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]

  19. 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]

  20. 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]

  21. 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]

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

  23. 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]

  24. 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]

  25. 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]

  26. 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]

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

  28. 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.

  29. 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]

  30. 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]

  31. 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]

  32. 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]

  33. 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]

  34. 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]

  35. 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]

  36. 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]

  37. 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]

  38. 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]

  39. 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]

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

  41. 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. Kohei Yamada, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda, Faster STR-EC-LCS Computation, Accepted for 46th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2020), January 2020.

  2. 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, Accepted for 46th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2020), January 2020. [arxiv]

  3. Noriki Fujisato, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki TakedaDirect 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]

  4. 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]

  5. 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]

  6. 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.

  7. 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.

  8. 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]

  9. 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].

  10. 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]

  11. 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]

  12. 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].

  13. 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].

  14. 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]

  15. 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]

  16. 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]

  17. 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].

  18. 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].

  19. 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]

  20. 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].

  21. 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]

  22. 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]

  23. 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]

  24. 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]

  25. 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]

  26. 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]

  27. 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]

  28. 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]

  29. 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]

  30. 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]

  31. 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]

  32. Takuya