8 papers
Non-Terminal Complexity of Simple Semi-Conditional Grammars
Henning Fernau, Sanjay Jain, Linus Richter +2
We study the complexity of simple semi-conditional grammars (SSCGs) in terms of the number of their terminals and non-terminals. We show that SSCGs with three non-terminals can gen…
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…
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…
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…
Word automatic groups of nilpotency class 2
Andre Nies, Frank Stephan
We consider word automaticity for groups that are nilpotent of class and have exponent a prime . We show that the infinitely generated free group in this variety is not word…
String Compression in FA-Presentable Structures
Dmitry Berdinsky, Sanjay Jain, Bakhadyr Khoussainov +1
We construct a FA-presentation of the structure for which a numerical characteristic defined as the maximum number $ψ…
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…