Limitations of lower bound methods for deterministic nested word automata (Q553328): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(5 intermediate revisions by 5 users not shown) | |||
Property / review text | |||
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? | |||
Property / review text: 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? / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 68Q45 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 68Q17 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 5932333 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
nested words | |||
Property / zbMATH Keywords: nested words / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
finite automata | |||
Property / zbMATH Keywords: finite automata / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
state complexity | |||
Property / zbMATH Keywords: state complexity / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
fooling set methods | |||
Property / zbMATH Keywords: fooling set methods / rank | |||
Normal rank | |||
Property / describes a project that uses | |||
Property / describes a project that uses: VPAlib / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/j.ic.2010.11.021 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2066278264 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Automata, Languages and Programming / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Adding Nesting Structure to Words / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Adding nesting structure to words / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Regular Languages of Nested Words: Fixed Points, Automata, and Synchronization / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Intersection and union of regular languages and state complexity / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Minimizing Variants of Visibly Pushdown Automata / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Efficient inclusion checking for deterministic tree automata and XML schemas / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Lower bounds for the transition complexity of NFAs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Streaming tree automata / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Finding Lower Bounds for Nondeterministic State Complexity Is Hard / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Inapproximability of Nondeterministic State and Transition Complexity Assuming P ≠ NP / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Nondeterministic state complexity of nested word automata / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Descriptional and Computational Complexity of Finite Automata / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4337605 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the limits of the communication complexity technique for proving lower bounds on the size of minimal NFA's / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4453205 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: State complexity of some operations on binary regular languages / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the State Minimization of Nondeterministic Finite Automata / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Minimization, Learning, and Conformance Testing of Boolean Programs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: State complexity of basic language operations combined with reversal / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Operational state complexity of nested word automata / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Transformations Between Different Models of Unranked Bottom-Up Tree Automata / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4714446 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: State Complexity of Nested Word Automata / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A Second Course in Formal Languages and Automata Theory / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 08:51, 4 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Limitations of lower bound methods for deterministic nested word automata |
scientific article |
Statements
Limitations of lower bound methods for deterministic nested word automata (English)
0 references
27 July 2011
0 references
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?
0 references
nested words
0 references
finite automata
0 references
state complexity
0 references
fooling set methods
0 references
0 references
0 references