کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
428751 686904 2008 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A note on partially ordered tree automata
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
A note on partially ordered tree automata
چکیده انگلیسی

A recent paper by Bouajjani, Muscholl and Touili shows that the class of languages accepted by partially ordered word automata (or equivalently accepted by Σ2-formulae) is closed under semi-commutation and it suggested the following open question: can we extend this result to tree languages? This problem can be addressed by proving (1) that the class of tree regular languages accepted by Σ2 formulae is strictly included in the class of languages accepted by partially ordered automata, and (2) that Bouajjani and the others results cannot be extended to tree.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 108, Issue 4, 31 October 2008, Pages 242-246