↑ arvau

Wikipedia / 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.

A matching relation such that:

  1. all nesting edges are forward, that is, if then ;

  2. nesting edges never have a finite position in common, that is, for , there is at most one position h such that , and there is at most one position j such that i ↝ j; and

  3. nesting edges never cross, that is, there are no such that both and .

A position i is referred to as

  • a call position, if i ↝ j for some j,

  • a pending call if i ↝ ∞,

  • a return position, if h ↝ i for some h,

  • a pending return if −∞ ↝ i, and

  • an internal position in all remaining cases.

A nested word over an alphabet Σ is a pair (w,↝), where w is a word, or string.

Encoding nested words into ordinary words

can be encoded into "ordinary" words over the tagged alphabet, 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 φ equals ⟨a, a, and a⟩ and i is a (possibly pending) call position, an internal position, and a (possibly pending) return position, respectively.

Example

For illustration, let be the nested word over a ternary alphabet with and matching relation }. Then its encoding as word reads as .

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 from left to right, and the state of the automaton after reading the j.

will not only depend on the linear state, 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, where

  • is a finite set of states,

  • is the input alphabet denotes the set of call symbols contains the return symbols contains the internal symbols,

  • is a finite set which is called the stack alphabet denoting the empty stack,

is the transition function, which is partitioned into three parts corresponding to call transitions, return transitions, and internal transitions, namely

  • , the call transition function

  • , the return transition function

  • , the internal transition function,

  • is the initial state, and

  • is the set of accepting states.

The notion of computation of a visibly pushdown automaton is a restriction of the one used for pushdown automata. A computation ending in an accepting state is an accepting computation.

, however there are pushdown automata accepting this language.

If a language is called a visibly pushdown language.

Nondeterministic visibly pushdown automata

Nondeterministic states.

Decision problems

, then it is possible to check if a word n is the depth of n.

For two nondeterministic automata A and B, deciding whether the set of words accepted by A is a subset of the words 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 forms a subset of the set DCFL of deterministic context-free languages. 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:

set operations:

For the intersection operation, one can construct a VPA M by a simple product construction . Then for the automaton M.

on reading a call symbol.

on reading an internal symbol on reading a.

on reading a return symbol.

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:

where

  • is called a non-terminal character or a variable are the one without pending calls or pending returns.

  • is a finite set of terminal.

are called the (rewrite) rules or production

  • is the start variable (or start symbol), used to represent the whole sentence (or program).

Here, the asterisk represents the Kleene star is the empty word.

Uniform Boolean circuits

is accepted by a given nested word automaton can be solved by uniform Boolean circuits.

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 ↝.

See also

Notes

References