Alternating Regular Tree Grammars in the Framework of Lattice-Valued Logic
عنوان مقاله: Alternating Regular Tree Grammars in the Framework of Lattice-Valued Logic
شناسه ملی مقاله: JR_IJFS-13-2_006
منتشر شده در در سال 1395
شناسه ملی مقاله: JR_IJFS-13-2_006
منتشر شده در در سال 1395
مشخصات نویسندگان مقاله:
Maryam Ghorani - Faculty of Mathematical Sciences, Shahrood University of Technology, Shahrood, Iran
Mohammad Mehdi Zahedi - Department of Mathematics, Graduate University of Advanced Technology, Kerman, Iran
خلاصه مقاله:
Maryam Ghorani - Faculty of Mathematical Sciences, Shahrood University of Technology, Shahrood, Iran
Mohammad Mehdi Zahedi - Department of Mathematics, Graduate University of Advanced Technology, Kerman, Iran
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}.
کلمات کلیدی: Lattice-valued logic, Alternating top-down tree automaton, State alternating regular tree grammar, Alternating stack tree automaton
صفحه اختصاصی مقاله و دریافت فایل کامل: https://civilica.com/doc/1466597/