# Nested word automatons

At the moment I'm trying to understand nested word automatons but I don't get the point quiet right. Let's say I have the alphabet $$\Sigma = \{c,r\}$$ and I want ot recoginize the languge $$\mathcal{L} = \{ \langle c^n r\rangle^n \}$$. On slide 14 of this presentation I found the following automaton which should recognize $$\mathcal{L}$$.

After reading the last $$\langle c$$ the automaton is is state $$(q_1,p_1)$$ and, since $$\delta_r: Q \times P \times \Sigma \rightarrow Q$$, after reading the first $$r\rangle$$ it switches to $$(q_2)$$. So how does the automaton keep track of reading the same ammount of $$\langle c$$ and $$r\rangle$$? Do we have to keep the hierarchical state in mind for each call symbol? If so wouldn't we need a stack again for that?

• Thank you so much for creating the TAGs! Commented Mar 11, 2019 at 11:15

A nested word $$n$$ over $$\Sigma$$ is a pair $$(a_1\cdots a_l; \leadsto)$$, where $$a_i\in\Sigma$$ and $$\leadsto$$ is a matching relation of length $$l$$. Note that if there is no pending call nor pending returns (in which case $$\leadsto$$ is said to be well-matched), then the number of the calls and the number of returns are equal by the definition of a matching relation. This is the case when you use $$\{ \langle c, r\rangle\}$$ as the alphabet of $$L$$ to represent the nested words.
What the nested word automaton in the question does mostly is, indeed, to check that all $$\langle c$$'s happens before $$r\rangle$$'s.
• I did read that. Maybe let's do an example. Let's consider the word $w = \langle c\langle c\langle cr\rangle r\rangle r\rangle$. The run, as explained in that paper, would look like this for the first 3 symbols: $q_0q_1q_1q_1$ and $p_0p_0p_1p_1$. But what is next now? $\delta_r$ only gives us a $q$ so how does the $p$ series continue? Commented Mar 11, 2019 at 11:14
• From the example of the paper: For example, in state $q_1$, while processing a call, the hierarchical state on the nestingedge is $p_1$, and the new linear state is $q_0$/$q_1$ depending on whether the call is labeled $1$/$0$. I do not understand this... How can I read $\langle 1$ in $q_1$? Commented Mar 12, 2019 at 9:32