{"id":"arxiv/2609.14181","url":"https://arxiv.org/abs/2609.14181","tags":["cs.FL","math.LO"],"score":0,"title":"Non-Terminal Complexity of Simple Semi-Conditional Grammars","domain":"cs.FL","source":"arxiv","authors":["Henning Fernau","Sanjay Jain","Linus Richter","Frank Stephan","Dan Turetsky"],"reviews":0,"subject":"cs.FL","summary":"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 generate all RE languages; two non-terminals suffice for linear languages; and one suffices for unary regular languages. We also determine both upper bounds and fundamental limitations of SSCGs: while certain one-non-terminal SSCGs can generate non-context-free languages, every language generated by a one-non-terminal SSCG is in non-deterministic linear space. We also prove that there exists a regular language of…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-12","reactions":{}}