4 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…