Differences

This shows you the differences between two versions of the page.

--- visibly_pushdown_languages [2007/05/31 11:08]
vkuncak
+++ visibly_pushdown_languages [2007/05/31 12:01]
vkuncak
@@ Line 13: / Line 13: @@
 ===== 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
@@ Line 32: / Line 34: @@
 ===== Closure properties =====
 ===== Determinization of visibly pushdown automaton =====
+Note
+  * cannot store set of stacks (not a stack)
+  * if attempt to store stack of sets of symbols, lose connection between states and stacks
+Solution: not just a set of states, but a summary of relation from initial to final states of 'procedure'.  Then update directly the effect of a procedure call on each state.
+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 =====