4 citations · 7 across the 6 of their papers we have counts for
6 papers
Two-State Max-Plus Comparison Is Decidable
Keigo Oka
Daviaud, Guillon, and Merlet proved that comparison of max-plus automata is undecidable under a fixed state bound of 553 and explicitly left the range from 2 to 552 states open. We…
Breaking the Barrier for Counting Linear Extensions with a Short Elementary Algorithm
Keigo Oka
A linear extension of a finite partially ordered set is a total ordering that respects the partial order. We give a deterministic exact algorithm that counts the linear extensions…
Turing Completeness of GNU find: From mkdir-assisted Loops to Standalone Computation
Keigo Oka
The Unix command \texttt{find} is among the first commands taught to beginners, yet remains indispensable for experienced engineers. In this paper, we demonstrate that \texttt{find…
Covering a Polyomino-Shaped Stain with Non-Overlapping Identical Stickers
Keigo Oka, Naoki Inaba, Akira Iino
You find a stain on the wall and decide to cover it with non-overlapping stickers of a single identical shape (rotation and reflection are allowed). Is it possible to find a sticke…
Fast Dynamic Graph Algorithms for Parameterized Problems
Yoichi Iwata, Keigo Oka
Fully dynamic graph is a data structure that (1) supports edge insertions and deletions and (2) answers problem specific queries. The time complexity of (1) and (2) are referred to…
Linear-Time FPT Algorithms via Network Flow
Yoichi Iwata, Keigo Oka, Yuichi Yoshida
In the area of parameterized complexity, to cope with NP-Hard problems, we introduce a parameter k besides the input size n, and we aim to design algorithms (called FPT algorithms)…