Finite Automata for the Sub- and Superword Closure of CFLs: Descriptional and Computational Complexity

Georg Bachmeier, Michael Luttenberger, Maximilian Schlund

We answer two open questions by (Gruber, Holzer, Kutrib, 2009) on the state-complexity of representing sub- or superword closures of context-free grammars (CFGs): (1) We prove a (t…