2 papers
math.GR2023
Quasilinear Emulation of Turing Machines by S-machines
Bogdan Chornomaz, Francis Wagner
We prove that for any , a non-deterministic Turing machine with time complexity can be emulated by an -machine with time and space complexiti…
math.CO2018
A Sauer-Shelah-Perles Lemma for Lattices
Stijn Cambie, Bogdan Chornomaz, Zeev Dvir +2
We study lattice-theoretical extensions of the celebrated Sauer-Shelah-Perles Lemma. We conjecture that a general Sauer-Shelah-Perlem Lemma holds for a lattice if and only if $…