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
Languages of Words of Low Automatic Complexity Are Hard to Compute
Joey Chen, Bjørn Kjos-Hanssen, Ivan Koswara +2
The automatic complexity of a finite word (string) is an analogue for finite automata of Sipser's distinguishing complexity (1983) and was introduced by Shallit and Wang (2001). Fo…
math.LO2025
All Borel Group Extensions of Finite-Dimensional Real Space Are Trivial
Linus Richter
For , we study the structure of definable abelian group extensions of the additive group by countable abelian (Borel) groups . Given an extension $H…