Faculty Profiles - I Tomohiro

Papers - I Tomohiro

Division display41 - 60 of about 65／ All the affair displays >>

Longest common extensions with recompression Reviewed

I T.

Leibniz International Proceedings in Informatics, LIPIcs 78 2017.07

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Faster sparse suffix sorting Reviewed

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

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

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

　 PREV - NEXT 　

<I Tomohiro>

Papers - I Tomohiro