3 papers
math.LO2026
Chains and Antichains inside Many-One Degrees and Variants
Linus Richter, Frank Stephan, Xiaoyan Zhang
The relations between many-one degrees and one-one degrees have been studied since the beginning of recursion theory; early results from the 1960s include that many-one degrees alw…
cs.FL2025
Quasi-Isometric Reductions Between Infinite Strings
Karen Frilya Celine, Ziyuan Gao, Sanjay Jain +3
This paper studies the recursion-theoretic aspects of large-scale geometries of infinite strings, a subject initiated by Khoussainov and Takisaka (2017). We investigate several not…
cs.FL2024
Languages given by Finite Automata over the Unary Alphabet
Wojciech CzerwiÅski, Maciej DÄbski, Tomasz Gogasz +5
This paper studies the complexity of operations on finite automata and the complexity of their decision problems when the alphabet is unary. Let denote the maximum of the numbe…