Limitations of lower bound methods for deterministic nested word automata (Q553328): Difference between revisions

Let \(\Sigma\) be a finite nonempty alphabet of internal symbols. The tagged alphabet is defined as \(\widehat{\Sigma} = \Sigma \cup \Sigma^{<} \cup \Sigma^{>}\), where \(\Sigma^{<} =\{a^{<}\mid a\in\Sigma\}\) is the set of call symbols and \(\Sigma^{>} = \{a^{>}\mid a\in\Sigma\}\) is the set of return symbols. A tagged word over \(\Sigma\) is a sequence of symbols of \(\widehat{\Sigma}\). In a tagged word \(w\), a call symbol \(a\) (hierarchically) matches a return symbol \(b\) on the right of \(a\) if in the sequence from \(a\) to \(b\) every call symbol (respectively, return symbol) has a matching return symbol (respectively, call symbol). A nested word is a tagged word that is associated with the linear ordering of symbols and the hierarchical matching relation between occurrences of call and return symbols. The set \(\operatorname{NW}(\Sigma)\) is the set of all nested words. A nested word language is any subset of \(\operatorname{NW}(\Sigma)\). Definition. A nondeterministic nested word automaton (NNWA) is a tuple \[ A=(\Sigma, Q, Q_0, Q_f, P, P_0, P_f, \delta_c, \delta_i, \delta_r), \] where \(\Sigma\) is the set of final linear states, \(P\) is a finite set of hierarchical states, \(Q\cap P\) is empty, \(P_0\subseteq P\) is the set of initial hierarchical states, \(P_f\subseteq P\) is the set of final hierarchical states, \(\delta_c: Q \otimes\Sigma^{<}\rightarrow 2^{Q \otimes P }\) is the call transition function, \(\delta_i :Q\otimes\Sigma\rightarrow 2^Q\) is the internal transition function, \(\delta_r : Q\otimes P\otimes \Sigma^{>}\rightarrow 2^Q\) is the return transition function. A nested word automaton is called deterministic (DNWA) if \(Q_0\) and \(P_0\) are singleton sets and \(\delta_c\), \(\delta_i\), \(\delta_r\) are partial functions. A nested word language is regular if it is recognized by an NNWA. The lower bounds for the state complexity of nested word languages rely on the fooling set type techniques. Theorem 1. For an arbitrarily large natural number \(n\) there exist regular nested word languages \(M_n\) such that state complexities \(\operatorname{sc}(M_n)\) and \(\operatorname{sc}(M_n^{*})\) belong respectively to \(O(n)\) and to \((2^{\Omega(n, \log n)})\). Theorem 2. There exist regular nested word languages \(L_n\), \(n\geq 1\), such that \(\operatorname{sc}(L_n)\geq n^{1/2}\), but the best lower bound obtained for \(\operatorname{sc}(L_n)\) using separator sets is 4. Open problem. What is the precise deterministic state complexity of concatenation, Kleene star and reversal, and the precise nondeterministic state complexity of complementation of regular nested word languages?