Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision | Next revision Both sides next revision | ||
|
visibly_pushdown_languages [2007/05/31 11:47] vkuncak |
visibly_pushdown_languages [2007/05/31 12:01] vkuncak |
||
|---|---|---|---|
| Line 13: | Line 13: | ||
| ===== Visibly pushdown automaton ===== | ===== Visibly pushdown automaton ===== | ||
| + | |||
| + | The key restriction compared to nondeterministic pushdown automata is that whether a visibly pushdown automaton will push or pop is determined only by the input symbol. (The automaton can change the state in a non-deterministic way, and can non-deterministically decide what to push.) | ||
| A (nondeterministic) visibly pushdown automaton (on finite words) over the pushdown alphabet $(\Sigma_c,\Sigma_r,\Sigma_l)$ is a tuple $M = (Q,Q_{in},\Gamma,\delta,Q_F)$ where | A (nondeterministic) visibly pushdown automaton (on finite words) over the pushdown alphabet $(\Sigma_c,\Sigma_r,\Sigma_l)$ is a tuple $M = (Q,Q_{in},\Gamma,\delta,Q_F)$ where | ||
| Line 43: | Line 45: | ||
| Note: you never store original symbols on the stack. | Note: you never store original symbols on the stack. | ||
| + | |||
| + | ===== MSOL over strings with matching relation ===== | ||
| + | |||
| + | Thanks to closure properties. | ||
| + | |||
| + | ===== Strack trees ===== | ||
| + | |||
| + | We can associate //injectively// trees with words over pushdown alphabet, then visibly pushdown languages correspond to regular trees. | ||
| + | |||
| + | Can we obtain closure and other properties from properties of tree automata? | ||
| + | |||
| + | ===== Visibly pushdown grammars ===== | ||
| ===== References ===== | ===== References ===== | ||