4 papers · 1 filter
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…
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…
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…