2 papers
math.LO2026
Lower Bounds on Inverse Cellular Automata via Proof Complexity
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…
math.CO2024
Multisorted Boolean Clones Determined by Binary Relations up to Minion Homomorphisms
Libor Barto, Maryia Kapytka
We describe the ordering of a class of clones by minion homomorphisms, also known as minor preserving maps or height 1 clone homomorphisms. The class consists of all clones on fini…