Reference:

Georg Bachmeier, Michael Luttenberger, and Maximilian Schlund. Finite Automata for the Sub- and Superword Closure of CFLs: Descriptional and Computational Complexity. In LATA, Lecture Notes in Computer Science, pages ??–??, March To appear.

Abstract:

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 (tight) upper bound of on the size of nondeterministic finite automata (NFAs) representing the subword closure of a CFG of size . (2) We present a family of CFGs for which the minimal deterministic finite automata representing their subword closure matches the upper-bound of following from (1). Furthermore, we prove that the inequivalence problem for NFAs representing sub- or superword-closed languages is only NP-complete as opposed to PSPACE-complete for general NFAs. Finally, we extend our results into an approximation method to attack inequivalence problems for CFGs.

Suggested BibTeX entry:

@inproceedings{BLS2015,
    author = {Georg Bachmeier and Michael Luttenberger and Maximilian Schlund},
    booktitle = {LATA},
    month = {March},
    pages = {??--??},
    series = {Lecture Notes in Computer Science},
    title = {{Finite Automata for the Sub- and Superword Closure of CFLs: Descriptional and Computational Complexity}},
    year = {To appear}
}