Showing cs.FLShow all
2 papers · 1 filter
cs.FL2026
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…
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…