11 citations · 32 across the 26 of their papers we have counts for
29 papers
Learning Deterministic Finite-State Machines from the Prefixes of a Single String is NP-Complete
Radu Cosmin Dumitru, Ryo Yoshinaka, Ayumi Shinohara
It is well known that computing a minimum deterministic finite automaton consistent with a given set of positive and negative examples is NP-hard. Previous work has identified cond…
Solvable Tuple Patterns and Their Applications to Program Verification
Naoki Kobayashi, Ryosuke Sato, Ayumi Shinohara +1
Despite the recent progress of automated program verification techniques, fully automated verification of programs manipulating recursive data structures remains a challenge. We in…
Misère Greedy Nim and Misère Bounded Greedy Nim
Nanako Omiya, Ryo Yoshinaka, Ayumi Shinohara
In this paper, we analyze the misère versions of two impartial combinatorial games: k-Bounded Greedy Nim and Greedy Nim. We present a complete solution to both games by showing nec…
BusOut is NP-complete
Takehiro Ishibashi, Ryo Yoshinaka, Ayumi Shinohara
This study examines the computational complexity of the decision problem modeled on the smartphone game Bus Out. The objective of the game is to load all the passengers in a queue…
StrNim: a variant of Nim played on strings
Shota Mizuno, Ryo Yoshinaka, Ayumi Shinohara
We propose a variant of Nim, named StrNim. Whereas a position in Nim is a tuple of non-negative integers, that in StrNim is a string, a sequence of characters. In every turn, each…
Subsequence Matching and LCS with Segment Number Constraints
Yuki Yonemoto, Takuya Mieno, Shunsuke Inenaga +2
The longest common subsequence (LCS) is a fundamental problem in string processing which has numerous algorithmic studies, extensions, and applications. A sequence $u_1, \ldots, u_…
Breaking a Barrier in Constructing Compact Indexes for Parameterized Pattern Matching
Kento Iseri, Tomohiro I, Diptarama Hendrian +3
A parameterized string (p-string) is a string over an alphabet , where and are disjoint alphabets for static symbols (s-symbols) and for paramet…
Efficient Parameterized Pattern Matching in Sublinear Space
Haruki Ideguchi, Diptarama Hendrian, Ryo Yoshinaka +1
The parameterized matching problem is a variant of string matching, which is to search for all parameterized occurrences of a pattern in a text . In considering matching alg…
Efficient Non-isomorphic Graph Enumeration Algorithms for Subclasses of Perfect Graphs
Jun Kawahara, Toshiki Saitoh, Hirokazu Takeda +2
Intersection graphs are well-studied in the area of graph algorithms. Some intersection graph classes are known to have algorithms enumerating all unlabeled graphs by reverse searc…
Inferring Strings from Position Heaps in Linear Time
Koshiro Kumagai, Diptarama Hendrian, Ryo Yoshinaka +1
Position heaps are index structures of text strings used for the string matching problem. They are rooted trees whose edges and nodes are labeled and numbered, respectively. This p…
Computing the Parameterized Burrows--Wheeler Transform Online
Daiki Hashimoto, Diptarama Hendrian, Dominik Köppl +2
Parameterized strings are a generalization of strings in that their characters are drawn from two different alphabets, where one is considered to be the alphabet of static characte…
Sorting Balls and Water: Equivalence and Computational Complexity
Takehiro Ito, Jun Kawahara, Shin-ichi Minato +7
Various forms of sorting problems have been studied over the years. Recently, two kinds of sorting puzzle apps are popularized. In these puzzles, we are given a set of bins filled…
Parallel algorithm for pattern matching problems under substring consistent equivalence relations
Davaajav Jargalsaikhan, Diptarama Hendrian, Ryo Yoshinaka +1
Given a text and a pattern over an alphabet, the pattern matching problem searches for all occurrences of the pattern in the text. An equivalence relation is called a sub…
Fixed-Treewidth-Efficient Algorithms for Edge-Deletion to Intersection Graph Classes
Toshiki Saitoh, Ryo Yoshinaka, Hans L. Bodlaender
For a graph class , the -Edge-Deletion problem asks for a given graph to delete the minimum number of edges from in order to obtain a graph in $\m…
Grammar compression with probabilistic context-free grammar
Hiroaki Naganuma, Diptarama Hendrian, Ryo Yoshinaka +2
We propose a new approach for universal lossless text compression, based on grammar compression. In the literature, a target string has been compressed as a context-free gramma…
Fast and linear-time string matching algorithms based on the distances of -gram occurrences
Satoshi Kobayashi, Diptarama Hendrian, Ryo Yoshinaka +1
Given a text of length and a pattern of length , the string matching problem is a task to find all occurrences of in . In this study, we propose an algorithm…
Parameterized DAWGs: efficient constructions and bidirectional pattern searches
Katsuhito Nakashima, Noriki Fujisato, Diptarama Hendrian +6
Two strings and over of equal length are said to \emph{parameterized match} (\emph{p-match}) if there is a renaming bijection that…
Computing Covers under Substring Consistent Equivalence Relations
Natsumi Kikuchi, Diptarama Hendrian, Ryo Yoshinaka +1
Covers are a kind of quasiperiodicity in strings. A string is a cover of another string if any position of is inside some occurrence of in . The shortest and lon…
Query Learning Algorithm for Residual Symbolic Finite Automata
Kaizaburo Chubachi, Diptarama Hendrian, Ryo Yoshinaka +1
We propose a query learning algorithm for residual symbolic finite automata (RSFAs). Symbolic finite automata (SFAs) are finite automata whose transitions are labeled by predicates…
An Extension of Linear-size Suffix Tries for Parameterized Strings
Katsuhito Nakashima, Diptarama Hendrian, Ryo Yoshinaka +1
In this paper, we propose a new indexing structure for parameterized strings which we call PLSTs, by generalizing linear-size suffix tries for ordinary strings. Two parameterized s…
Enumerating Cryptarithms Using Deterministic Finite Automata
Yuki Nozaki, Diptarama Hendrian, Ryo Yoshinaka +2
A cryptarithm is a mathematical puzzle where given an arithmetic equation written with letters rather than numerals, a player must discover an assignment of numerals on letters tha…
Linear-Time Online Algorithm Inferring the Shortest Path from a Walk
Shintaro Narisada, Diptarama Hendrian, Ryo Yoshinaka +1
We consider the problem of inferring an edge-labeled graph from the sequence of edge labels seen in a walk of that graph. It has been known that this problem is solvable in $O(n \l…
Enumerating All Subgraphs without Forbidden Induced Subgraphs via Multivalued Decision Diagrams
Jun Kawahara, Toshiki Saitoh, Hirofumi Suzuki +1
We propose a general method performed over multivalued decision diagrams that enumerates all subgraphs of an input graph that are characterized by input forbidden induced subgraphs…
Efficient Dynamic Dictionary Matching with DAWGs and AC-automata
Diptarama Hendrian, Shunsuke Inenaga, Ryo Yoshinaka +1
The dictionary matching is a task to find all occurrences of patterns in a set (called a dictionary) on a text . The Aho-Corasick-automaton (AC-automaton) is a data structur…