3 papers
cs.FL2026
Unary Versus Binary Two-Way Automata
Viliam Geffert, Vincent Hlaváč, Rastislav Královič
If L is a unary language, then its binary coded version bin(L) is a binary language containing all binary strings representing any 0^x in L. It is known that if a unary language L…
cs.IT2026
Point-to-set Principle and Constructive Dimension Faithfulness
Satyadev Nandakumar, Subin Pulari, Akhil S
Hausdorff -dimension is a notion of Hausdorff dimension developed using a restricted class of coverings of a set. We introduce an effective version of Hausdorff -dimension,…
cs.DS2024
Tree Coloring: Random Order and Predictions
Fabian Frei, Matthias Gehnen, Dennis Komm +4
Coloring is a notoriously hard problem, and even more so in the online setting, where each arriving vertex has to be colored immediately and irrevocably. Already on trees, which ar…