فهرست نشریات علمی دسترسی آزاد ایران

In this paper, two different ways of introducing alternation for lattice-valued (referred to as {L}valued)  regular tree grammars and {L}valued top-down tree automata are compared. One is the way which defines the alternating regular tree grammar, i.e., alternation is governed by the non-terminals of the grammar and the other is the way which combines state with alternation. The first way is taken over to  prove a  main theorem:   the  class  of   languages generated by an {L}valued alternating regular tree grammar {LAG}) is  equal  to  the  class  of  languages  accepted  by an {L}valued alternating top-down tree automaton {LAA}). The second  way is taken over to define   a new type of   automaton by combining the {L}valued  alternating top-down tree automaton with stack,   called {L}-valued   alternating stack tree automaton {LASA}  and  the generative power of it is compared to some well-known language classes, especially to  {LAA} and to {LAG}Also, we have derived a characterization of the state alternating regular tree grammar {LSAG}) in terms of  {LASA}.