Nested word

In computer science, more specifically in automata and formal language theory, nested words are a concept proposed by Alur and Madhusudan as a joint generalization of words, as traditionally used for modelling linearly ordered structures, and of ordered unranked trees, as traditionally used for modelling hierarchical structures. Finite-state acceptors for nested words,
so-called nested word automata, then give a more expressive generalization of finite automata on words. The linear encodings of languages accepted by finite nested word automata gives the class of visibly pushdown languages. The latter language class lies properly between the regular languages and the deterministic context-free languages. Since their introduction in 2004, these concepts have triggered much research in that area.
Formal definition.
To define "nested words", first define "matching relations". For a nonnegative integer formula_1, the notation formula_2 denotes the set formula_3, with the special case formula_4.
A "matching relation" ↝ of length formula_5 is a subset of formula_6 such that:
A position "i" is referred to as 
A "nested word" of length formula_1 over an alphabet Σ is a pair ("w",↝), where "w" is a word, or string, of length formula_1 over Σ and ↝ is a matching relation of length formula_1.
Encoding nested words into ordinary words.
Nested words over the alphabet formula_10 can be encoded into "ordinary" words over the "tagged alphabet" formula_11, in which each symbol "a" from Σ has three tagged counterparts: the
symbol ⟨a for encoding a call position in a nested word labelled with "a", the symbol a⟩ for encoding a return position labelled with "a", and finally the symbol a itself for representing an internal position labelled with "a". More precisely, let "φ" be the function mapping nested words over Σ to words over formula_12 such that each nested word (formula_13,↝) is mapped to the word formula_14, where the letter formula_15 equals ⟨a, a, and a⟩, if formula_16 and "i" is a (possibly pending) call position, an internal position, and a (possibly pending) return position, respectively.
Example.
For illustration, let "n" = ("w",↝) be the nested word over a ternary alphabet with "w"="abaabccca" and matching relation }. Then its encoding as word reads as "φ"("n") = "a"⟩⟨"b"⟨"aa"⟩⟨"bcc"⟩⟨"ca".
Automata.
Nested word automaton.
A "nested word automaton" has a finite number of states, and operates in almost the same way as a deterministic finite automaton on classical strings: a classical finite automaton reads the input word formula_17 from left to right, and the state of the automaton after reading the "j"th letter formula_18 depends on the state in which the automaton was before reading formula_18.
In a nested word automaton, the position formula_20 in the nested word (w,↝) might be a return position; if so, the state after reading formula_18 will not only depend on the "linear state" in which the automaton was before reading formula_18, but also on a "hierarchical state" propagated by the automaton at the time it was in the corresponding call position. In analogy to regular languages of words, a set "L" of nested words is called "regular" if it is accepted by some (finite-state) nested word automaton.
Visibly pushdown automaton.
Nested word automata are an automaton model accepting nested words. There is an equivalent automaton model operating on (ordinary) words. Namely, the notion of a deterministic visibly pushdown automaton is a restriction of the notion of a deterministic pushdown automaton.
Following Alur and Madhusudan, a deterministic visibly pushdown automaton is formally defined as a 6-tuple formula_23
where
The notion of "computation" of a visibly pushdown automaton is a restriction of the one used for pushdown automata. Visibly pushdown automata only add a symbol to the stack when reading a call symbol formula_40, they only remove the top element from the stack when reading a return symbol formula_41 and they do not alter the stack when reading an internal event formula_42. A computation ending in an accepting state is an "accepting computation".
As a result, a visibly pushdown automaton cannot push to and pop from the stack with the same input symbol. Thus the language formula_43 cannot be accepted by a visibly pushdown automaton for any partition of formula_44, however there are pushdown automata accepting this language.
If a language formula_45 over a tagged alphabet formula_12 is accepted by a deterministic visibly pushdown automaton, then formula_45 is called a "visibly pushdown language".
Nondeterministic visibly pushdown automata.
Nondeterministic visibly pushdown automata are as expressive as deterministic ones. Hence one can transform a nondeterministic visibly pushdown automaton into a deterministic one, but if the nondeterministic automaton had formula_48 states, the deterministic one may have up to formula_49 states.
Decision problems.
Let formula_50 be the size of the description of an automaton formula_51, then it is possible to check if a word "n" is accepted by the automaton in time formula_52. In particular, the emptiness problem is solvable in time formula_53.
If formula_51 is fixed, it is decidable in time formula_55 and space formula_56 where formula_57 is the depth of "n" in a streaming seeing. It is also decidable with space formula_58 and time formula_59, and by a uniform boolean circuit of depth formula_60.
For two nondeterministic automata "A" and "B", deciding whether the set of words accepted by "A" is a subset of the word accepted by "B" is EXPTIME-complete. It is also EXPTIME-complete to figure out if there is a word that is not accepted.
Languages.
As the definition of visibly pushdown automata shows, deterministic visibly pushdown automata can be seen as a special case of deterministic pushdown automata; thus the set VPL of visibly pushdown languages over formula_61 forms a subset of the set DCFL of deterministic context-free languages over the set of symbols in formula_61. In particular, the function that removes the matching relation from nested words transforms regular languages over nested words into context-free languages.
Closure properties.
The set of visibly pushdown languages is closed under the following operations:
For the intersection operation, one can construct a VPA "M" simulating two given VPAs formula_63 and formula_64 by a simple product construction : For formula_65, assume formula_66 is given as formula_67. Then for the automaton "M", the set of states is formula_68, the initial state is formula_69, the set of final states is formula_70, the stack alphabet is given by formula_71, and the initial stack symbol is formula_72.
If formula_73 is in state formula_74 on reading a "call symbol" formula_75, then
formula_73 pushes the stack symbol formula_77
and goes to state formula_78, where formula_79 is the stack symbol pushed by formula_66
when transitioning from state formula_81 to formula_82 on reading input formula_75.
If formula_73 is in state formula_74 on reading an "internal symbol" formula_86, then formula_73
goes to state formula_78, whenever formula_66
transitions from state formula_81 to formula_82 on reading "a".
If formula_73 is in state formula_74 on reading a "return symbol" formula_94, then formula_73
pops the symbol formula_77 from the stack and
goes to state formula_78, where formula_79 is the stack symbol popped by formula_66
when transitioning from state formula_81 to formula_82 on reading formula_94.
Correctness of the above construction crucially relies on the fact that the push and pop actions of the simulated
machines formula_63 and formula_64 are synchronized along the input symbols read. In fact, a similar simulation is no longer possible for deterministic pushdown automata, as the larger class of deterministic context-free languages is no longer closed under intersection.
In contrast to the construction for concatenation shown above, the complementation construction for visibly pushdown automata parallels the standard construction for deterministic pushdown automata.
Moreover, like the class of context free languages the class of visibly pushdown languages is closed under prefix closure and reversal, hence also suffix closure.
Relation to other language classes.
 point out that the visibly pushdown languages are more general than the parenthesis languages suggested in . As shown by , the visibly pushdown languages in turn are strictly contained in the class of languages described by operator-precedence grammars, which were introduced by and enjoy the same closure properties and characteristics (see for ω languages and logic and automata-based characterizations). In comparison to conjunctive grammars, a generalization of context-free grammars, shows that the linear conjunctive languages form a superclass of the visibly pushdown languages. The table at the end of this article puts the family of visibly pushdown languages in relation to other language families in the Chomsky hierarchy.
Rajeev Alur and Parthasarathy Madhusudan related a subclass of regular binary tree languages to visibly pushdown languages.
Other models of description.
Visibly pushdown grammars.
Visibly pushdown languages are exactly the languages that can be described by "visibly pushdown grammars".
Visibly pushdown grammars can be defined as a restriction of context-free grammars. A visibly pushdown grammar "G" is defined by the 4-tuple:
formula_105 where
Here, the asterisk represents the Kleene star operation and formula_131 is the empty word.
Uniform Boolean circuits.
The problem whether a word of length formula_1 is accepted by a given nested word automaton can be solved by uniform boolean circuits of depth formula_133.
Logical description.
Regular languages over nested words are exactly the set of languages described by monadic second-order logic with two unary predicates "call" and "return", linear successor and the matching relation ↝.