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}$.

enter image description here

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?

  • $\begingroup$ Thank you so much for creating the TAGs! $\endgroup$ – Cilenco Mar 11 '19 at 11:15

Please note that the input to a nested word automaton is nested words instead of the usual words.

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.

You are encouraged to read the seminal paper Adding Nesting Structure to Words by Rajeev Alur and P. Madhusudan. You might be delighted to find it is pretty easy to read, especially the relevant section 3.1.

| cite | improve this answer | |
  • $\begingroup$ 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? $\endgroup$ – Cilenco Mar 11 '19 at 11:14
  • $\begingroup$ 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$? $\endgroup$ – Cilenco Mar 12 '19 at 9:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.