2014/10/10 by Georg Bachmeier, Bachmeier, Georg, Michael Luttenberger +3
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #DNA and Biological Computing #F.4.3 #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Natural Language Processing Techniques #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1410.2737
openalex publication_date 2014/10/10 · openalex created_date 2025/10/24 · openalex updated_date 2026/07/28
We answer two open questions by (Gruber, Holzer, Kutrib, 2009) on the\nstate-complexity of representing sub- or superword closures of context-free\ngrammars (CFGs): (1) We prove a (tight) upper bound of 2\O(n) on\nthe size of nondeterministic finite automata (NFAs) representing the subword\nclosure of a CFG of size n. (2) We present a family of CFGs for which the\nminimal deterministic finite automata representing their subword closure\nmatches the upper-bound of 2^2\O(n) following from (1).\nFurthermore, we prove that the inequivalence problem for NFAs representing sub-\nor superword-closed languages is only NP-complete as opposed to PSPACE-complete\nfor general NFAs. Finally, we extend our results into an approximation method\nto attack inequivalence problems for CFGs.\n