6 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 ne…
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_…