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.
The linear encodings of languages accepted by finite nested word automata gives the class of visibly pushdown languages.
Since their introduction in 2004, these concepts have triggered much research in that area.
over an alphabet Σ is a pair (w,↝), where w is a word, or string, of length
can be encoded into "ordinary" words over the tagged alphabet
For illustration, let n = (w,↝) be the nested word over a ternary alphabet with w=abaabccca and matching relation ↝ = {(−∞,1),(2,∞),(3,4),(5,7),(8,∞)}.
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
from left to right, and the state of the automaton after reading the jth letter
in the nested word (w,↝) might be a return position; if so, the state after reading
will not only depend on the linear state in which the automaton was before reading
, but also on a hierarchical state propagated by the automaton at the time it was in the corresponding call position.
There is an equivalent automaton model operating on (ordinary) words.
Following Alur and Madhusudan,[2] a deterministic visibly pushdown automaton is formally defined as a 6-tuple
, they only remove the top element from the stack when reading a return symbol
As a result, a visibly pushdown automaton cannot push to and pop from the stack with the same input symbol.
cannot be accepted by a visibly pushdown automaton for any partition of
is accepted by a deterministic visibly pushdown automaton, then
Nondeterministic visibly pushdown automata are as expressive as deterministic ones.
, then it is possible to check if a word n is accepted by the automaton in time
In particular, the function that removes the matching relation from nested words transforms regular languages over nested words into context-free languages.
Correctness of the above construction crucially relies on the fact that the push and pop actions of the simulated machines
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.
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.
As shown by Crespi Reghizzi & Mandrioli (2012), the visibly pushdown languages in turn are strictly contained in the class of languages described by operator-precedence grammars, which were introduced by Floyd (1963) and enjoy the same closure properties and characteristics (see Lonati et al. (2015) for ω languages and logic and automata-based characterizations).
In comparison to conjunctive grammars, a generalization of context-free grammars, Okhotin (2011) harvtxt error: no target: CITEREFOkhotin2011 (help) 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[5][6] related a subclass of regular binary tree languages to visibly pushdown languages.
where Here, the asterisk represents the Kleene star operation and
is accepted by a given nested word automaton can be solved by uniform Boolean circuits of depth
[2] 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 ↝.