Finite Automata for the Sub- and Superword Closure of CFLs: Descriptional and Computational Complexity
| Autor: | Georg Bachmeier, Maximilian Schlund, Michael Luttenberger |
|---|---|
| Rok vydání: | 2015 |
| Předmět: |
Discrete mathematics
Combinatorics Deterministic finite automaton Finite-state machine Computational complexity theory Closure (computer programming) Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing) Nondeterministic finite automaton Upper and lower bounds Computer Science::Formal Languages and Automata Theory Mathematics |
| Zdroj: | Language and Automata Theory and Applications ISBN: 9783319155784 LATA |
| DOI: | 10.1007/978-3-319-15579-1_37 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|