Alternating Regular Tree Grammars in the Framework of Lattice-Valued Logic

در اين مقاله، دو روش متفاوت به‌كارگيري تناوب براي گرامرهاي درختي منظم مشبكه-مقدار (L-مقدار) و اتوماتاي درختي از بالا به پايين L-مقدار مقايسه مي‌شوند. يك روش گرامر درختي منظم متناوب را تعريف مي‌كند، يعني تناوب با غيرنهايي‌هاي گرامر همراه مي‌شود و روش ديگر حالت را با تناوب تركيب مي‌كند. روش اول براي اثبات يك قضيه اساسي به‌كار گرفته مي‌شود: رده زبان‌هاي توليد شده توسط يك گرامر درختي منظم متناوب L-مقدار (LAG) مساوي رده زبان‌هاي پذيرفته شده توسط يك اتوماتون درختي از بالا به پايين متناوب L-مقدار (LAA) است. روش دوم به‌كار گرفته مي‌شود تا با تركيب اتوماتون درختي از بالا به پايين متناوب L-مقدار با پشته، يك نوع اتوماتون جديد معرفي كند كه به آن اتوماتون درختي پشته‌اي متناوب L-مقدار (LASA) گفته مي‌شود و قدرت توليدي آن با برخي رده‌‍‌هاي معروف زبان، به خصوص LAA و LAG مقايسه مي‌شود. همچنين، مشخصه‌اي از گرامر درختي منظم متناوب حالتي (LSAG) بر حسب LASA بدست مي‌آيد.

In this paper, two different ways of introducing alternation for lattice-valued (referred to as $\mathscr{L}$-valued) regular tree grammars and $\mathscr{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 $\mathscr{L}$-valued alternating regular tree grammar $(\mathcal{LAG})$ is equal to the class of languages accepted by an $\mathscr{L}$-valued alternating top-down tree automaton $(\mathcal{LAA}).$ The second way is taken over to define a new type of automaton by combining the $\mathscr{L}$-valued alternating top-down tree automaton with stack, called $\mathscr{L}$-valued alternating stack tree automaton $(\mathcal{LASA})$ and the generative power of it is compared to some well-known language classes, especially to $\mathcal{LAA}$ and to $\mathcal{LAG}.$ Also, we have derived a characterization of the state alternating regular tree grammar $(\mathcal{LSAG})$ in terms of $\mathcal{LASA}.$