Updated on 2024/05/14

 
I Tomohiro
 
Scopus Paper Info  
Total Paper Count: 0  Total Citation Count: 0  h-index: 15

Citation count denotes the number of citations in papers published for a particular year.

Affiliation
Faculty of Computer Science and Systems Engineering Department of Artificial Intelligence
Job
Associate Professor
External link

Degree

  • Kyushu University  -  Doctor of Science   2012.04

Biography in Kyutech

  • 2019.01
     

    Kyushu Institute of Technology   Faculty of Computer Science and Systems Engineering   Department of Artificial Intelligence   Associate Professor  

  • 2015.10
    -
    2018.12
     

    Kyushu Institute of Technology   Frontier Research Academy for Young Researchers   Specially Appointed Assistant Professor  

Papers

  • Computing Longest (Common) Lyndon Subsequences Reviewed International journal

    Hideo Bannai, Tomohiro I, Tomasz Kociumaka, Dominik Köppl, Simon J. Puglisi

    International Workshop on Combinatorial Algorithms (IWOCA) 2022 ( Springer-Verlag )   128 - 142   2022.06

     More details

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

    DOI: 10.1007/978-3-031-06678-8_10

    DOI: 10.1007/978-3-031-06678-8_10

  • The "runs" theorem Reviewed International journal

    Bannai H., I T., Inenaga S., Nakashima Y., Takeda M., Tsuruta K.

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

     More details

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

    DOI: 10.1137/15M1011032

    Scopus

    Other Link: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85032917335&origin=inward

  • Longest bordered and periodic subsequences Reviewed International journal

    Bannai H., I T., Köppl D.

    Information Processing Letters   182   2023.08

     More details

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

    DOI: 10.1016/j.ipl.2023.106398

    Scopus

    Other Link: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85153571879&origin=inward

  • Substring Complexities on Run-Length Compressed Strings Reviewed International journal

    Kawamoto A., I T.

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   13617 LNCS   132 - 143   2022.11

     More details

    Authorship:Corresponding author   Language:English   Publishing type:Research paper (international conference proceedings)

    DOI: 10.1007/978-3-031-20643-6_10

    Scopus

    Other Link: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85142675895&origin=inward

  • Space-Efficient B Trees via Load-Balancing Reviewed International journal

    Tomohiro I, Dominik Köppl

    International Workshop on Combinatorial Algorithms (IWOCA) 2022 ( Springer-Verlag )   327 - 340   2022.06

     More details

    Authorship:Corresponding author   Language:English   Publishing type:Research paper (international conference proceedings)

    DOI: 10.1007/978-3-031-06678-8_24

    DOI: 10.1007/978-3-031-06678-8_24

  • A Compression-Based Multiple Subword Segmentation for Neural Machine Translation Reviewed

    Nonaka K., Yamanouchi K., I T., Okita T., Shimada K., Sakamoto H.

    Electronics (Switzerland)   11 ( 7 )   2022.04

     More details

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

    DOI: 10.3390/electronics11071014

    Scopus

    Other Link: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85126910361&origin=inward

  • Converting RLBWT to LZ77 in smaller space Reviewed

    Masaki Shigekuni, Tomohiro I

    Data Compression Conference (DCC) 2022 ( IEEE Computer Society Press CPS Online )   242 - 251   2022.03

     More details

    Authorship:Last author, Corresponding author   Language:English   Publishing type:Research paper (international conference proceedings)

    DOI: 10.1109/DCC52660.2022.00032

    DOI: 10.1109/DCC52660.2022.00032

  • PHONI: Streamed Matching Statistics with Multi-Genome References Reviewed International journal

    Boucher C., Gagie T., Tomohiro I., Koppl D., Langmead B., Manzini G., Navarro G., Pacheco A., Rossi M.

    Data Compression Conference Proceedings   2021-March   193 - 202   2021.03

     More details

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

    DOI: 10.1109/DCC50243.2021.00027

    Scopus

    Other Link: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85106006610&origin=inward

  • Extracting the Sparse Longest Common Prefix Array from the Suffix Binary Search Tree Reviewed

    I T., Irving R.W., Köppl D., Love L.

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   12944 LNCS   143 - 150   2021.01

     More details

    Authorship:Lead author   Language:English   Publishing type:Research paper (international conference proceedings)

    Given a text T of length n, the sparse suffix sorting problem asks for the lexicographic order of suffixes starting at m selectable text positions P. The suffix binary search tree [Irving and Love, JDA’03] is a dynamic data structure that can answer this problem dynamically in the sense that insertions and deletions of positions in P are allowed. While a standard binary search tree on strings needs to store two longest-common prefix (LCP) values per node for providing the same query bounds, each suffix binary search tree node only stores a single LCP value and a bit flag. Its tree topology induces the sorting of the m suffixes by an Euler tour in O(m) time. However, it has not been addressed how to compute the lengths of the longest common prefixes of two suffixes with neighboring ranks with this data structure. We show that we can compute these lengths again by an Euler tour in O(m) time.

    DOI: 10.1007/978-3-030-86692-1_12

    Scopus

    Other Link: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85116834863&origin=inward

  • A Separation of γ and b via Thue–Morse Words Reviewed

    Bannai H., Funakoshi M., I T., Köppl D., Mieno T., Nishimoto T.

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   12944 LNCS   167 - 178   2021.01

     More details

    Authorship:Lead author   Language:English   Publishing type:Research paper (international conference proceedings)

    We prove that for n≥ 2, the size b(tn) of the smallest bidirectional scheme for the nth Thue–Morse word tn is n+ 2. Since Kutsukake et al. [SPIRE 2020] show that the size γ(tn) of the smallest string attractor for tn is 4 for n≥ 4, this shows for the first time that there is a separation between the size of the smallest string attractor γ and the size of the smallest bidirectional scheme b, i.e., there exist string families such that γ= o(b).

    DOI: 10.1007/978-3-030-86692-1_14

    Scopus

    Other Link: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85116783139&origin=inward

  • Re-Pair in Small Space Reviewed International journal

    Dominik Köppl, Tomohiro I, Isamu Furuya, Yoshimasa Takabatake, Kensuke Sakai, Keisuke Goto

    Algorithms   14 ( 1 )   2020.12

     More details

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

    DOI: 10.3390/a14010005

  • Practical Random Access to SLP-Compressed Texts Reviewed

    Travis Gagie, Tomohiro I, Giovanni Manzini, Gonzalo Navarro, Hiroshi Sakamoto, Louisa Seelbach Benkner, Yoshimasa Takabatake

    Lecture Notes in Computer Science   12303 LNCS   221 - 231   2020.10

     More details

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

    DOI: 10.1007/978-3-030-59212-7_16

  • RePair in Compressed Space and Time Reviewed International journal

    Dominik Köppl, Tomohiro I, Isamu Furuya, Yoshimasa Takabatake, Kensuke Sakai, Keisuke Goto

    The Prague Stringology Conference   134 - 147   2020.08

     More details

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

  • Deterministic Sparse Suffix Sorting in the Restore Model Reviewed

    Fischer J., I T., Köppl D.

    ACM Transactions on Algorithms   16 ( 4 )   Article No. 50   2020.07

     More details

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

    DOI: 10.1145/3398681

    Other Link: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85025816771&origin=inward

  • Refining the r-index Reviewed

    Bannai H., Gagie T., I T.

    Theoretical Computer Science   812   96 - 108   2020.04

     More details

    Authorship:Corresponding author   Language:English   Publishing type:Research paper (scientific journal)

    DOI: 10.1016/j.tcs.2019.08.005

    Scopus

    Other Link: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85070385571&origin=inward

  • Dynamic index and LZ factorization in compressed space Reviewed

    Nishimoto T., I T., Inenaga S., Bannai H., Takeda M.

    Discrete Applied Mathematics   274   116 - 129   2020.03

     More details

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

    DOI: 10.1016/j.dam.2019.01.014

    Scopus

    Other Link: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85061439333&origin=inward

  • Faster privacy-preserving computation of edit distance with moves Reviewed

    Yoshimoto Y., Kataoka M., Takabatake Y., I T., Shin K., Sakamoto H.

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   12049 LNCS   308 - 320   2020.01

     More details

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

    DOI: 10.1007/978-3-030-39881-1_26

    Scopus

    Other Link: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85080940455&origin=inward

  • Rpair: Rescaling RePair with Rsync Reviewed

    Gagie T., I T., Manzini G., Navarro G., Sakamoto H., Takabatake Y.

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   11811 LNCS   35 - 44   2019.10

     More details

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

    DOI: 10.1007/978-3-030-32686-9_3

    Scopus

    Other Link: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85075670034&origin=inward

  • k-Abelian Pattern Matching: Revisited, Corrected, and Extended Reviewed International journal

    Golnaz Badkobeh, Hideo Bannai, Maxime Crochemore, Tomohiro I, Shunsuke Inenaga and Shiho Sugimoto

    The Prague Stringology Conference   29 - 40   2019.08

     More details

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

  • RePair in Compressed Space and Time Reviewed

    Sakai K., Ohno T., Goto K., Takabatake Y., I T., Sakamoto H.

    Data Compression Conference Proceedings   2019-March   518 - 527   2019.05

     More details

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

    DOI: 10.1109/DCC.2019.00060

    Scopus

    Other Link: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85066320396&origin=inward

  • Improved upper bounds on all maximal α-gapped repeats and palindromes Reviewed

    I T., Köppl D.

    Theoretical Computer Science   753   1 - 15   2019.01

     More details

    Authorship:Lead author   Language:English   Publishing type:Research paper (scientific journal)

    DOI: 10.1016/j.tcs.2018.06.033

    Scopus

    Other Link: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85049535167&origin=inward

  • A faster implementation of online RLBWT and its application to LZ77 parsing Reviewed

    Ohno T., Sakai K., Takabatake Y., I T., Sakamoto H.

    Journal of Discrete Algorithms   52-53   18 - 28   2018.09

     More details

    Authorship:Corresponding author   Language:English   Publishing type:Research paper (scientific journal)

    DOI: 10.1016/j.jda.2018.11.002

    Scopus

    Other Link: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85056312105&origin=inward

  • Lempel–Ziv Factorization Powered by Space Efficient Suffix Trees Reviewed

    Fischer J., I T., Köppl D., Sadakane K.

    Algorithmica   80 ( 7 )   2048 - 2081   2018.07

     More details

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

    DOI: 10.1007/s00453-017-0333-1

    Scopus

    Other Link: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85025816771&origin=inward

  • Online LZ77 parsing and matching statistics with RLBWTs Reviewed

    Bannai H., Gagie T., I T.

    Leibniz International Proceedings in Informatics, LIPIcs   105   71 - 712   2018.05

     More details

    Authorship:Corresponding author   Language:English   Publishing type:Research paper (international conference proceedings)

    DOI: 10.4230/LIPIcs.CPM.2018.7

    Scopus

    CiNii Research

    Other Link: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85048304169&origin=inward

  • Faster online elastic degenerate string matching Reviewed

    Aoyama K., Nakashima Y., I T., Inenaga S., Bannai H., Takeda M.

    Leibniz International Proceedings in Informatics, LIPIcs   105   91 - 910   2018.05

     More details

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

    DOI: 10.4230/LIPIcs.CPM.2018.9

    Scopus

    CiNii Research

    Other Link: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85048268511&origin=inward

  • Lyndon factorization of grammar compressed texts revisited Reviewed

    Furuya I., Nakashima Y., I T., Inenaga S., Bannai H., Takeda M.

    Leibniz International Proceedings in Informatics, LIPIcs   105   241 - 2410   2018.05

     More details

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

    DOI: 10.4230/LIPIcs.CPM.2018.24

    Scopus

    CiNii Research

    Other Link: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85048271134&origin=inward

  • Tighter Bounds and Optimal Algorithms for All Maximal α-gapped Repeats and Palindromes: Finding All Maximal α-gapped Repeats and Palindromes in Optimal Worst Case Time on Integer Alphabets Reviewed

    Gawrychowski P., I T., Inenaga S., Köppl D., Manea F.

    Theory of Computing Systems   62 ( 1 )   162 - 191   2018.01

     More details

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

    DOI: 10.1007/s00224-017-9794-5

    Scopus

    Other Link: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85028529401&origin=inward

  • Approximate Frequent Pattern Discovery in Compressed Space Reviewed

    101 ( 3 )   593 - 601   2018.01

     More details

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

    DOI: 10.1587/transinf.2017FCP0010

    CiNii Article

    Other Link: https://ci.nii.ac.jp/naid/130006414054

  • A faster implementation of online run-length burrows-wheeler transform Reviewed

    Ohno T., Takabatake Y., I T., Sakamoto H.

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   10765 LNCS   409 - 419   2018.01

     More details

    Authorship:Corresponding author   Language:English   Publishing type:Research paper (international conference proceedings)

    DOI: 10.1007/978-3-319-78825-8_33

    Scopus

    Other Link: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85046002496&origin=inward

  • Block palindromes: A new generalization of palindromes Reviewed

    Goto K., I T., Bannai H., Inenaga S.

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   11147 LNCS   183 - 190   2018.01

     More details

    Authorship:Corresponding author   Language:English   Publishing type:Research paper (international conference proceedings)

    DOI: 10.1007/978-3-030-00479-8_15

    Scopus

    Other Link: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85054822428&origin=inward

  • LZ-ABT: A practical algorithm for α-balanced grammar compression Reviewed

    Ohno T., Goto K., Takabatake Y., I T., Sakamoto H.

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   10979 LNCS   323 - 335   2018.01

     More details

    Authorship:Corresponding author   Language:English   Publishing type:Research paper (international conference proceedings)

    DOI: 10.1007/978-3-319-94667-2_27

    Scopus

    Other Link: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85049890021&origin=inward

  • Privacy-Preserving String Edit Distance with Moves Reviewed

    Nakagawa S., Sakamoto T., Takabatake Y., I T., Shin K., Sakamoto H.

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   11223 LNCS   226 - 240   2018.01

     More details

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

    DOI: 10.1007/978-3-030-02224-2_18

    Scopus

    Other Link: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85055117003&origin=inward

  • The Runs Theorem and Beyond Invited Reviewed

    I T.

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   11088 LNCS   18 - 23   2018.01

     More details

    Authorship:Lead author   Language:English   Publishing type:Research paper (international conference proceedings)

    DOI: 10.1007/978-3-319-98654-8_2

    Scopus

    Other Link: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85053865754&origin=inward

  • A space-optimal grammar compression Reviewed

    Takabatake Y., I T., Sakamoto H.

    Leibniz International Proceedings in Informatics, LIPIcs   87   2017.09

     More details

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

    DOI: 10.4230/LIPIcs.ESA.2017.67

    Scopus

    CiNii Research

    Other Link: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85030564164&origin=inward

  • Inferring strings from Lyndon factorization Reviewed

    Nakashima Y., Okabe T., I T., Inenaga S., Bannai H., Takeda M.

    Theoretical Computer Science   689   147 - 156   2017.08

     More details

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

    DOI: 10.1016/j.tcs.2017.05.038

    Scopus

    Other Link: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85020825934&origin=inward

  • Longest common extensions with recompression Reviewed

    I T.

    Leibniz International Proceedings in Informatics, LIPIcs   78   2017.07

     More details

    Authorship:Lead author   Language:English   Publishing type:Research paper (international conference proceedings)

    DOI: 10.4230/LIPIcs.CPM.2017.18

    Scopus

    CiNii Research

    Other Link: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85027268431&origin=inward

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

    I T., Nakashima Y., Inenaga S., Bannai H., Takeda M.

    Theoretical Computer Science   656   215 - 224   2016.12

     More details

    Authorship:Lead author   Language:English   Publishing type:Research paper (scientific journal)

    DOI: 10.1016/j.tcs.2016.03.005

    Scopus

    Other Link: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84961175476&origin=inward

  • Closed factorization Reviewed

    Badkobeh G., Bannai H., Goto K., I T., Iliopoulos C.S., Inenaga S., Puglisi S.J., Sugimoto S.

    Discrete Applied Mathematics   212   23 - 29   2016.10

     More details

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

    DOI: 10.1016/j.dam.2016.04.009

    Scopus

    Other Link: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84967167017&origin=inward

  • Fully dynamic data structure for LCE queries in compressed space Reviewed

    Nishimoto T., I T., Inenaga S., Bannai H., Takeda M.

    Leibniz International Proceedings in Informatics, LIPIcs   58   2016.08

     More details

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

    DOI: 10.4230/LIPIcs.MFCS.2016.72

    Scopus

    CiNii Research

    Other Link: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85012885943&origin=inward

  • Online Grammar Compression for Frequent Pattern Discovery Reviewed

    FUKUNAGA Shouhei, TAKABATAKE Yoshimasa, I Tomohiro, SAKAMOTO Hiroshi

    JSAI Technical Report, SIG-FPAI ( The Japanese Society for Artificial Intelligence )   101 ( 0 )   06   2016.08

     More details

    Language:Japanese   Publishing type:Research paper (scientific journal)

    DOI: 10.11517/jsaifpai.101.0_06

    CiNii Article

    CiNii Research

    Other Link: http://id.ndl.go.jp/bib/027587749

  • Deterministic sub-linear space LCE data structures with efficient construction Reviewed

    Tanimura Y., I T., Bannai H., Inenaga S., Puglisi S., Takeda M.

    Leibniz International Proceedings in Informatics, LIPIcs   54   1.1 - 1.10   2016.06

     More details

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

    DOI: 10.4230/LIPIcs.CPM.2016.1

    Scopus

    CiNii Research

    Other Link: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85011977600&origin=inward

  • Efficiently finding all maximal α-gapped repeats Reviewed

    Gawrychowski P., I T., Inenaga S., Köppl D., Manea F.

    Leibniz International Proceedings in Informatics, LIPIcs   47   2016.02

     More details

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

    DOI: 10.4230/LIPIcs.STACS.2016.39

    Scopus

    CiNii Research

    Other Link: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84961615105&origin=inward

  • Deterministic sparse suffix sorting on rewritable texts Reviewed

    Fischer J., I T., Köppl D.

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   9644   483 - 496   2016.01

     More details

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

    DOI: 10.1007/978-3-662-49529-2_36

    Scopus

    Other Link: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84961711921&origin=inward

  • Dynamic index and LZ factorization in compressed space Reviewed

    Nishimoto T., I T., Inenaga S., Bannai H., Takeda M.

    Proceedings of the Prague Stringology Conference, PSC 2016   158 - 171   2016.01

     More details

    Authorship:Corresponding author   Language:English   Publishing type:Research paper (international conference proceedings)

    In this paper, we propose a new dynamic compressed index of O(w) space for a dynamic text T, where w = O(min(z logN log-M,N)) is the size of the signature encoding of T, z is the size of the Lempel-Ziv77 (LZ77) factorization of T, N is the length of T, and M ≥ 4N is an integer that can be handled in constant time under word RAM model. Our index supports searching for a pattern P in T in O(|P|fA + log w log |P| log-M(logN + log |P| log-M) + occ logN) time and insertion/deletion of a substring of length y in O((y + logN log-M) log w logN log-M) time, where fA = O(min{log logM log log w log log logM , √ log w log log w}). Also, we propose a new spaceefficient LZ77 factorization algorithm for a given text of length N, which runs in O(NfA + z log w log3 N(log- N)2) time with O(w) working space.

    Scopus

    Other Link: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85027267678&origin=inward

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

    Nakashima Y., I T., Inenaga S., Bannai H., Takeda M.

    Information Processing Letters   115 ( 9 )   655 - 659   2015.09

     More details

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

    © 2015 Elsevier B.V. We present the first worst-case linear-time algorithm to compute the Lempel-Ziv 78 factorization of a given string over an integer alphabet. Our algorithm is based on nearest marked ancestor queries on the suffix tree of the given string. We also show that the same technique can be used to construct the position heap of a set of strings in worst-case linear time, when the set of strings is given as a trie.

    DOI: 10.1016/j.ipl.2015.04.002

    Scopus

    Other Link: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84927723236&origin=inward

  • Compressed automata for dictionary matching Reviewed

    I T., Nishimoto T., Inenaga S., Bannai H., Takeda M.

    Theoretical Computer Science   578   30 - 41   2015.05

     More details

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

    © 2015 Elsevier B.V.. We address a variant of the dictionary matching problem where the dictionary is represented by a straight line program (SLP). For a given SLP-compressed dictionary D of size n and height h representing m patterns of total length N, we present an O(n2log N)-size representation of Aho-Corasick automaton which recognizes all occurrences of the patterns in D in amortized O(h+m) running time per character. We also propose an algorithm to construct this compressed Aho-Corasick automaton in O(n3log n log N) time and O(n2log N) space. In a spacial case where D represents only a single pattern, we present an O(n log N)-size representation of the Morris-Pratt automaton which permits us to find all occurrences of the pattern in amortized O(h) running time per character, and we show how to construct this representation in O(n3log n log N) time with O(n2log N) working space.

    DOI: 10.1016/j.tcs.2015.01.019

    Scopus

    Other Link: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84951866541&origin=inward

  • Detecting regularities on grammar-compressed strings Reviewed

    I T., Matsubara W., Shimohira K., Inenaga S., Bannai H., Takeda M., Narisawa K., Shinohara A.

    Information and Computation   240   74 - 89   2015.02

     More details

    Authorship:Lead author   Language:English   Publishing type:Research paper (international conference proceedings)

    DOI: 10.1016/j.ic.2014.09.009

    Scopus

    Other Link: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85027953511&origin=inward

  • A faster algorithm for computing maximal α-gapped repeats in a string Reviewed

    Tanimura Y., Fujishige Y., I T., Inenaga S., Bannai H., Takeda M.

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   9309   124 - 136   2015.01

     More details

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

    © Springer International Publishing Switzerland 2015. A string x = uvu with both u, v being non-empty is called a gapped repeat with period p = |uv|, and is denoted by pair (x, p). If p ≤ α(|x| − p) with α > 1, then (x, p) is called an α-gapped repeat. An occurrence [i, i+|x|−1] of an α-gapped repeat (x, p) in a string w is called a maximal α-gapped repeat of w, if it cannot be extended either to the left or to the right in w with the same period p. Kolpakov et al. (CPM 2014) showed that, given a string of length n over a constant alphabet, all the occurrences of maximal α-gapped repeats in the string can be computed in O(α2n+occ) time, where occ is the number of occurrences. In this paper, we propose a faster O(αn + occ)-time algorithm to solve this problem, improving the result of Kolpakov et al. by a factor of α.

    DOI: 10.1007/978-3-319-23826-5_13

    Scopus

    Other Link: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84944682942&origin=inward

  • A new characterization of maximal repetitions by Lyndon trees Reviewed

    Bannai H., I T., Inenaga S., Nakashima Y., Takeda M., Tsuruta K.

    Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms   2015-January ( January )   562 - 571   2015.01

     More details

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

    Copyright © 2015 by the Society for Industrial and Applied Mathmatics. We give a new characterization of maximal repetitions (or runs) in strings, using a tree defined on recursive standard factorizations of Lyndon words, called the Lyndon tree. The characterization leads to a remarkably simple novel proof of the linearity of the maximum number of runs p(n) in a string of length n. Furthermore, we show an upper bound of p(n) < 1.5n, which improves on the best upper bound 1.6n (Crochemore & Hie 2008) that does not rely on computational verification. The proof also gives rise to a new, conceptually simple linear-time algorithm for computing all the runs in a string. A notable characteristic of our algorithm is that, unlike all existing linear-time algorithms, it does not utilize the Lempel-Ziv factorization of the string.

    Scopus

    Other Link: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84938221386&origin=inward

  • Arithmetics on suffix arrays of Fibonacci words Reviewed

    Köppl D., I T.

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   9304   135 - 146   2015.01

     More details

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

    © Springer International Publishing Switzerland 2015. We study the sequence of Fibonacci words and some of its derivatives with respect to their suffix array, inverse suffix array and Burrows-Wheeler transform based on the respective suffix array.We show that the suffix array is a rotation of its inverse under certain conditions, and that the factors of the LZ77 factorization of any Fibonacci word yield again similar characteristics.

    DOI: 10.1007/978-3-319-23660-5_12

    Scopus

    Other Link: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84945955196&origin=inward

  • Beyond the runs theorem Reviewed

    Fischer J., Holub Š., I T., Lewenstein M.

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   9309   277 - 286   2015.01

     More details

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

    © Springer International Publishing Switzerland 2015. In [3], a short and elegant proof was presented showing that a word of length n contains at most n - 3 runs. Here we show, using the same technique and a computer search, that the number of runs in a binary word of length n is at most 22/23n < 0.957n.

    DOI: 10.1007/978-3-319-23826-5_27

    Scopus

    Other Link: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84944682455&origin=inward

  • Inferring strings from full abelian periods Reviewed

    Nishida M., I T., Inenaga S., Bannai H., Takeda M.

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   9472   768 - 779   2015.01

     More details

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

    © Springer-Verlag Berlin Heidelberg 2015. Strings u, v are said to be Abelian equivalent if u is a permutation of the characters appearing in v. A string w is said to have a full Abelian period p if w = w1 …wk, where all wi’s are of length p each and are all Abelian equivalent. This paper studies reverse-engineering problems on full Abelian periods. Given a positive integer n and a set D of divisors of n, we show how to compute in O(n) time the lexicographically smallest string of length n which has all elements of D as its full Abelian periods and has the minimum number of full Abelian periods not in D. Moreover, we give an algorithm to enumerate all such strings in amortized constant time per output after O(n)-time preprocessing. Also, we show how to enumerate the strings which have all elements of D as its full Abelian periods in amortized constant time per output after O(n)-time preprocessing.

    DOI: 10.1007/978-3-662-48971-0_64

    Scopus

    Other Link: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84951950947&origin=inward

  • Lempel Ziv computation in small space (LZ-CISS) Reviewed

    Fischer J., I T., Köppl D.

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   9133   172 - 184   2015.01

     More details

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

    © Springer International Publishing Switzerland 2015. For both the Lempel Ziv 77- and 78-factorization we propose factorization algorithms using (1 + ε)n lg n + O(n) bits (for any positive constant ε ≤ 1) working space (including the space for the output) for any text of size n over an integer alphabet in O(n/ε2) time.

    DOI: 10.1007/978-3-319-19929-0_15

    Scopus

    Other Link: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84948952875&origin=inward

  • Semi-dynamic compact index for short patterns and succinct van Emde Boas tree Reviewed

    Matsuoka Y., I T., Inenaga S., Bannai H., Takeda M.

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   9133   355 - 366   2015.01

     More details

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

    © Springer International Publishing Switzerland 2015. We present a compact semi-dynamic text index which allows us to find short patterns efficiently. For parameters k ≤ q ≤ logσ n − logσ logσ n and alphabet size σ = O(polylog(n)), all occ occurrences of a pattern of length at most q−k+1 can be obtained in O(k×occ +logσ n) time, where n is the length of the text. Adding characters to the end of the text is supported in amortized constant time. Our index requires (n/k) log(n/k) + n log σ + o(n) bits of space, which is compact (i.e., O(n log σ)) when k = Θ(logσ n). As a byproduct, we present a succinct van Emde Boas tree which supports insertion, deletion, predecessor, and successor on a dynamic set of integers over the universe [0,m − 1] in O(log logm) time and requires only m + o(m) bits of space.

    DOI: 10.1007/978-3-319-19929-0_30

    Scopus

    Other Link: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84948993636&origin=inward

  • Faster sparse suffix sorting Reviewed

    I T., Kärkkäinen J., Kempa D.

    Leibniz International Proceedings in Informatics, LIPIcs   25   386 - 396   2014.03

     More details

    Authorship:Lead author   Language:English   Publishing type:Research paper (international conference proceedings)

    © Tomohiro I, Juha Kärkkäinen, and Dominik Kempa. The sparse suffix sorting problem is to sort b = o(n) arbitrary suffixes of a string of length n using o(n) words of space in addition to the string. We present an O(n) time Monte Carlo algorithm using O(b log b) space and an O(n log b) time Las Vegas algorithm using O(b) space. This is a significant improvement over the best prior solutions by Bille et al. (ICALP 2013): a Monte Carlo algorithm running in O(n log b) time and O(b1+ε) space or O(n log2b) time and O(b) space, and a Las Vegas algorithm running in O(n log2b+b2log b) time and O(b) space. All the above results are obtained with high probability not just in expectation.

    DOI: 10.4230/LIPIcs.STACS.2014.386

    Scopus

    Other Link: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84907811406&origin=inward

  • Faster compact on-line Lempel-ziv factorization Reviewed

    Yamamoto J., I T., Bannai H., Inenaga S., Takeda M.

    Leibniz International Proceedings in Informatics, LIPIcs   25   675 - 686   2014.03

     More details

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

    © Jun'ichi Yamamoto, Tomohiro I, Hideo Bannai, Shunsuke Inenaga, and Masayuki Takeda. We present a new on-line algorithm for computing the Lempel-Ziv factorization of a string that runs in O(N logN) time and uses only O(N log σ) bits of working space, where N is the length of the string and σ is the size of the alphabet. This is a notable improvement compared to the performance of previous on-line algorithms using the same order of working space but running in either O(N log3N) time (Okanohara & Sadakane 2009) or O(N log2N) time (Starikovskaya 2012). The key to our new algorithm is in the utilization of an elegant but less popular index structure called Directed Acyclic Word Graphs, or DAWGs (Blumer et al. 1985). We also present an opportunistic variant of our algorithm, which, given the run length encoding of size m of a string of length N, computes the Lempel-Ziv factorization of the string on-line, in O (m · min{n (log logm)(log logN)/log log logN , √ logm/log logm o})time and O(mlogN) bits of space.

    DOI: 10.4230/LIPIcs.STACS.2014.675

    Scopus

    Other Link: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84907858098&origin=inward

  • Inferring strings from suffix trees and links on a binary alphabet Reviewed

    I T., Inenaga S., Bannai H., Takeda M.

    Discrete Applied Mathematics   163 ( PART 3 )   316 - 325   2014.01

     More details

    Authorship:Lead author   Language:English   Publishing type:Research paper (scientific journal)

    A suffix tree, which provides us with a linear space full-text index of a given string, is a fundamental data structure for string processing and information retrieval. In this paper we consider the reverse engineering problem on suffix trees: given an unlabeled ordered rooted tree T accompanied with a node-to-node transition function f, infer a string whose suffix tree and its suffix links for inner nodes are isomorphic to T and f, respectively. Also, we consider the enumeration problem in which we enumerate all strings corresponding to an input tree and links. By introducing new characterizations of suffix trees, we show that the reverse engineering problem and the enumeration problem on suffix trees on a binary alphabet can be solved in optimal time. © 2013 Elsevier B.V. All rights reserved.

    DOI: 10.1016/j.dam.2013.02.033

    Scopus

    Other Link: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84889665144&origin=inward

  • Closed factorization Reviewed

    Badkobeh G., Bannai H., Goto K., I T., Iliopoulos C., Inenaga S., Puglisi S., Sugimoto S.

    Proceedings of the Prague Stringology Conference 2014, PSC 2014   162 - 168   2014.01

     More details

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

    © Czech Technical University in Prague, Czech Republic. A closed string is a string with a proper substring that occurs in the string as a prefix and a suffix, but not elsewhere. Closed strings were introduced by Fici (Proc. WORDS, 2011) as objects of combinatorial interest in the study of Trapezoidal and Sturmian words. In this paper we consider algorithms for computing closed factors (substrings) in strings, and in particular for greedily factorizing a string into a sequence of longest closed factors. We describe an algorithm for this problem that uses linear time and space. We then consider the related problem of computing, for every position in the string, the longest closed factor starting at that position. We describe a simple algorithm for the problem that runs in O(n log n/ log log n) time.

    Scopus

    Other Link: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84928791807&origin=inward

  • Computing palindromic factorizations and palindromic covers on-line Reviewed

    I T., Sugimoto S., Inenaga S., Bannai H., Takeda M.

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   8486   150 - 161   2014.01

     More details

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

    A palindromic factorization of a string w is a factorization of w consisting only of palindromic substrings of w. In this paper, we present an on-line O(n logn)-time O(n)-space algorithm to compute smallest palindromic factorizations of all prefixes of w, where n is the length of a given string w. We then show how to extend this algorithm to compute smallest maximal palindromic factorizations of all prefixes of w, consisting only of maximal palindromes (non-extensible palindromic substring) of each prefix, in O(n logn) time and O(n) space, in an on-line manner. We also present an on-line O(n)-time O(n)-space algorithm to compute a smallest palindromic cover of w. © 2014 Springer International Publishing Switzerland.

    DOI: 10.1007/978-3-319-07566-2_16

    Scopus

    Other Link: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84958527699&origin=inward

  • Inferring strings from Lyndon factorization Reviewed

    Nakashima Y., Okabe T., I T., Inenaga S., Bannai H., Takeda M.

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   8635 LNCS ( PART 2 )   565 - 576   2014.01

     More details

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

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

    Scopus

    Other Link: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84906230308&origin=inward

▼display all

Honors and Awards

  • IWOCA best paper award

    Program Committee of the 33rd International Workshop on Combinatorial Algorithms   Computing Longest (Common) Lyndon Subsequences   2022.06

    Hideo Bannai, Tomohiro I, Tomasz Kociumaka, Dominik Köppl, Simon J. Puglisi

     More details

    Country:Germany

    We present an algorithm computing the longest periodic subsequence of a string of length n in O(n^7) time with O(n^4) words of space. We obtain improvements when restricting the exponents or extending the search allowing the reported subsequence to be subperiodic down to O(n^3) time and O(n^2) words of space.

Grants-in-Aid for Scientific Research

  • 高効率で多様な文字列処理を実現する圧縮変換の理論

    Grant number:16K16009  2016.04 - 2019.03   若手研究(B)

Activities of Academic societies and Committees

  • 電子情報通信学会   『Special Section on Foundations of Computer Science 』 小特集編集委員会 編集委員  

    2022.03 - 2023.03

  • 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022)   33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022) プログラム委員  

    2022.01 - 2022.07

  • 28th International Symposium on String Processing and Information Retrieval (SPIRE 2021)   28th International Symposium on String Processing and Information Retrieval (SPIRE 2021) プログラム委員  

    2021.05 - 2021.11

  • 電子情報通信学会   『Special Section on Foundations of Computer Science』 小特集編集委員会 編集委員  

    2021.01 - 2022.03

  • 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021)   32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021) プログラム委員  

    2021.01 - 2021.08

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

    2018.04 - 2022.03

▼display all