5 papers
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…
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…
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…
An Improved Algorithm for Sparse Instances of SAT
Sanjay Jain, Tzeh Yuan Neoh, Frank Stephan
We show that the CNF satisfiability problem (SAT) can be solved in time , where is either the maximum number of occurrences of any variable or the average…
Classifying different criteria for learning algebraic structures
Nikolay Bazhenov, Vittorio Cipriani, Sanjay Jain +2
In the last years there has been a growing interest in the study of learning problems associated with algebraic structures. The framework we use models the scenario in which a lear…