Advertisement
Published in:
2015 | OriginalPaper | Chapter
Finite Automata for the Sub- and Superword Closure of CFLs: Descriptional and Computational Complexity
Authors : Georg Bachmeier, Michael Luttenberger, Maximilian Schlund
Published in: Language and Automata Theory and Applications
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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
$$2^{\mathcal {O}(n)}$$
on the size of nondeterministic finite automata (NFAs) representing the subword closure of a CFG of size
$$n$$
. (2) We present a family of CFGs for which the minimal deterministic finite automata representing their subword closure matches the upper-bound of
$$2^{2^{\mathcal {O}(n)}}$$
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.