Talk:Nested word

Runs

Hermel removed an entire paragraph, that I copy below, writting "removed incomprehensible sentence". But if the paragraph was here, there was a reason. I think one should explain how a machine run. Even if it is trivial for anyone used to automaton theory, given the type of the three delta function, it certainly could help someone who is not used to the field.

I can understand that it is hard to read, english is not my mother tong, but at least, someone should try to rewrite it !

A run of the automaton begin in state $q_{0}$ with an empty stack. At each step, the automaton reads a letter and:

• If the letter is a call $\langle a$, then let $\delta _{c}(q,a)=(q',g)$, the automaton goes to state $q'$ and push $g$ in the stack.
• If the letter is an internal letter $a$ then let $\delta _{i}(q,a)=q'$, the automaton goes to state $q'$
• If the letter is a return letter $a\rangle$ and the top of the stack is $g$ then let $\delta _{c}(q,a,g)=q'$, the automaton goes to state $q'$ and pop $g$ from the top of the stack. If the stack is empty we take $g$ to be $Z$.

where $q$ is the state before the step. The run stop when every letters are read, and the runs is accepting the state at the end of the run is in $F$.

Arthur MILCHIOR (talk) 22:36, 31 March 2011 (UTC)

I agree to that the accepting computation should be explained more precisely. In particular, the notion of computation is not "precisely" that of PDAs. PDAs ignore the partition of the alphabet. However, I don't think we should just copy or rephrase the definition. Anyone interested in the details can read the paper. Anyway, you should revise your added references (besides the fact that you can reuse them using <ref name="..." />). Neither the STOC 04 paper defines a grammar (you may find it in the JACM09 publication) nor it claims the upper bound for determinization to be optimal, nor it shows polynomial runtime for the decision problem in the deterministic case.

Unfortunately, I don't like the definition. It is not following the STOC 2004 notation (as claimed). There, you don't read about tagged alphabets and the partitions of the alphabet need not be equal-sized. Unless that gets cleaned up it's unmotivating to contribute. --Zahnradzacken (talk) 20:00, 1 April 2011 (UTC)

I modified the definition of automata and added a few words on the definition of computation. I don't think that additional definitions would render the text more comprehensible for readers not involved with automata. Still, a few more words might improve the section. --Zahnradzacken (talk) 15:42, 8 April 2011 (UTC)

Sorry for the rigorous removal. But I did not want to go into pains to correct that definition, whose tone was imho too formal anyway. Thus thought that removing the passage would improve the overall readability of the article. I slightly edited the previous edit by Zahnradzacken, and I hope that everyone is happy now. Hermel (talk) 21:11, 13 April 2011 (UTC)

Establish location in Chomsky hierarchy

The lead says: "...visibly pushdown languages. The latter language class lies properly between the regular languages and the deterministic context-free languages." Looking for a source for this statement, I just found prop.5.1 (p.26) in Alur+Madhusudan 2009, proving containment in CFLs. Could somebody please find a reference for the containment of regular languages (may be trivial due to less-restrictive requirements to automata - I dind't check that), and two example languages demonstrating that both containments are proper? - Jochen Burghardt (talk) 12:10, 25 February 2015 (UTC)

Closure properties

@Saolof: I looked over your recent edits, and the closure properties section in general. Something important needs to be clarified here: how do the closure operations deal with the input alphabet partitioning (i.e. $\Sigma _{c},\Sigma _{r},\Sigma _{int}$? I propose that this be explicitly discussed in the article, perhaps before the operations list.

For example, my understanding is that for the set operations, the input alphabet partitioning is fixed (and visibly pushdown languages are not closed if it is not fixed). But I briefly thought about reversal and string homomorphism, and I don't know how it works with those:

• Does reversal switch call and return symbols?
• Are string homomorphisms required to preserve the input alphabet partitioning?

Caleb Stanford (talk) 23:27, 29 December 2021 (UTC)