1 paper · 1 filter
Maryia Kapytka
We study the complexity of inverse cellular automata on configurations of bounded size. Deciding injectivity in this setting is co-NP-complete by a theorem of Durand. We give a sim…