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.
Contents
- Formal definition
- Encoding nested words into ordinary words
- Example
- Nested word automaton
- Visibly pushdown automaton
- Nondeterministic visibly pushdown automata
- Decision problems
- Languages
- Closure properties
- Relation to other language classes
- Visibly pushdown grammars
- Uniform Boolean circuits
- Logical description
- References
Formal definition
To define nested words, we first need to define matching relation. As usual, for a nonnegative integer
A matching relation ↝ of length
- all nesting edges are forward, that is, if i ↝ j then i<j;
- nesting edges never have a finite position in common, that is, for -∞ < i < ∞, there is at most one position h such that h ↝ i, and there is at most one position j such that i ↝ j; and
- nesting edges never cross, that is, we can't find i<i’≤j<j’ such that both i ↝ j and i’ ↝ j’.
A position i is referred to as
A nested word of length
Encoding nested words into ordinary words
Nested words over the alphabet
Example
For illustration, let n=(w,↝) be the nested word over an ternary alphabet with w=abaabccca and matching relation ↝ = {(-∞,1),(2,∞),(3,4),(5,7),(8,∞)}. Then its encoding as word reads as φ(n) = a⟩⟨b⟨aa⟩⟨bcc⟩⟨ca.
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
In a nested word automaton, the position
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
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
As a result, a visibly pushdown automaton cannot push to and pop from the stack with the same input symbol. Thus the language
If a 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
Decision problems
Let
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
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
If
If
If
Correctness of the above construction crucially relies on the fact that the push and pop actions of the simulated machines
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
Alur & Madhusudan (2004) point out that the visibly pushdown languages are more general than the parenthesis languages suggested in McNaughton (1967). As shown by Crespi Reghizzi & Mandrioli (2012), the VPL 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) 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.
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:
Here, the asterisk represents the Kleene star operation and
Uniform Boolean circuits
The problem whether a word of length
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 ↝.