“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.^[1]

Formal definition

To define nested words, first define matching relations. For a nonnegative integer

, the notation

denotes the set

, with the special case

A nested word of length

over an alphabet Σ is a pair (w,↝), where w is a word, or string, of length

over Σ and ↝ is a matching relation of length

Encoding nested words into ordinary words

Nested words over the alphabet

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 φ be the function mapping nested words over Σ to words over

such that each nested word (

,↝) is mapped to the word

, where the letter

equals ⟨a, a, and a⟩, if

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 {{math|1=↝ = {(−∞,1),(2,∞),(3,4),(5,7),(8,∞)}}}. 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

from left to right, and the state of the automaton after reading the jth letter

depends on the state in which the automaton was before reading

In a nested word automaton, the position

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. 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,^[2] 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

, they only remove the top element from the stack when reading a return symbol

and they do not alter the stack when reading an internal event

. 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

cannot be accepted by a visibly pushdown automaton for any partition of

, however there are pushdown automata accepting this language.

If a language

over a tagged alphabet

is accepted by a deterministic visibly pushdown automaton, then

is called a visibly pushdown language.

Nondeterministic visibly pushdown automata

Decision problems

Let

be the size of the description of an automaton

, then it is possible to check if a word n is accepted by the automaton in time

. In particular, the emptiness problem is solvable in time

is fixed, it is decidable in time

and space

where

is the depth of n in a streaming seeing. It is also decidable with space

and time

, and by a uniform boolean circuit of depth

.^[2]

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.^[2]

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

forms a subset of the set DCFL of deterministic context-free languages over the set of symbols in

. 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:^[3]

For the intersection operation, one can construct a VPA M simulating two given VPAs

and

by a simple product construction {{harv|Alur|Madhusudan|2004}}: For

, assume

is given as

. Then for the automaton M, the set of states is

, the initial state is

, the set of final states is

, the stack alphabet is given by

, and the initial stack symbol is

Correctness of the above construction crucially relies on the fact that the push and pop actions of the simulated

machines

and

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^[4] 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

Rajeev Alur and Parthasarathy Madhusudan^[5]^[6] 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.^[2]

Visibly pushdown grammars can be defined as a restriction of context-free grammars. A visibly pushdown grammar G is defined by the 4-tuple:

Uniform Boolean circuits

The problem whether a word of length

is accepted by a given nested word automaton can be solved by uniform boolean circuits of depth