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 a words, as traditionally used for modeling linearly ordered structures, and of ordered unranked trees, as traditionally used for modeling 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 a lot of research in that area.[1]
Formal Definition
Nested words are defined with the aid of a matching relation, to be defined first: A matching relation ↝ of length is a subset of such
that:
(i) only forward nesting edges, that is, if i ↝ j then i<j;
(ii) nesting edges never have a position in common, that is, for , there is at most one position h such that h ↝ i, and there is at most one position j such that i ↝ j; and
(iii) nesting edges never cross, that is, there are no four positions h<i<j<k such that both h ↝ j and i ↝ k.
A nested word over an alphabet (computer science) Σ is a pair (w,↝), where w is a word over Σ (in the usual sense) and ↝ is a matching relation, whose length is equal to the length of the word.
Notes
- ^ Google Scholar search results for "nested words" OR "visibly pushdown"
References
- Rajeev Alur, P. Madhusudan: Visibly pushdown languages. STOC 2004:202-211
- Rajeev Alur, Marcelo Arenas, Pablo Barceló, Kousha Etessami, Neil Immerman, Leonid Libkin: First-Order and Temporal Logics for Nested Words. Logical Methods in Computer Science 4(4): (2008)
- Rajeev Alur, P. Madhusudan: Adding nesting structure to words. Journal of the ACM 56(3) (2009)