patternMinor
Nested word automatons
Viewed 0 times
nestedautomatonsword
Problem
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?
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#105396, answer score: 2
Revisions (0)
No revisions yet.