TY - GEN
T1 - Finite automata for the sub- and superword closure of CFLs
T2 - 9th International Conference on Language and Automata Theory and Applications, LATA 2015
AU - Bachmeier, Georg
AU - Luttenberger, Michael
AU - Schlund, Maximilian
N1 - Publisher Copyright:
© Springer International Publishing Switzerland 2015.
PY - 2015
Y1 - 2015
N2 - 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 2O(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 22O(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.
AB - 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 2O(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 22O(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.
KW - Descriptional complexity
KW - Language approximation
KW - Nfa equivalence
KW - Subword closure
UR - http://www.scopus.com/inward/record.url?scp=84928779104&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-15579-1_37
DO - 10.1007/978-3-319-15579-1_37
M3 - Conference contribution
AN - SCOPUS:84928779104
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 473
EP - 485
BT - Language and Automata Theory and Applications - 9th International Conference, LATA 2015, Proceedings
A2 - Dediu, Adrian-Horia
A2 - Martín-Vide, Carlos
A2 - Formenti, Enrico
A2 - Truthe, Bianca
PB - Springer Verlag
Y2 - 2 March 2015 through 6 March 2015
ER -