کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6874852 1441444 2018 16 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Optimised determinisation and completion of finite tree automata
ترجمه فارسی عنوان
تعیین و تکمیل خودکار اتوماتیک درختی محدود
ترجمه چکیده
تعیین و تکمیل خودکار ماشین آلات درخت درختی عملیات مهم با برنامه های کاربردی در تجزیه و تحلیل برنامه و تأیید است. با این حال، پیچیدگی روش های کلاسیک برای تعیین و تکمیل بالا است. آنها روش های عملی برای دستکاری در ماشین های درختی فراتر از آنهایی که بسیار کوچک هستند نیستند. در این مقاله یک الگوریتم برای تعیین و تکمیل دستگاه اتوماتیک درختی محدود ایجاد می کنیم که پیچیدگی بدترین حالت آن بدون تغییر باقی می ماند اما در عمل عمل بسیار بهتر از الگوریتم های موجود است. جنبه بحرانی الگوریتم این است که انتقال از ماشین تعیین شده (و احتمالا تکمیل شده) در یک فرم بالقوه بسیار جمع و جور به نام فرم محصول تولید می شود که می تواند به طور چشمگیری میزان نمایش را کاهش دهد. علاوه بر این، نمایندگی اغلب می تواند به طور مستقیم در هنگام دستکاری ماشین تعیین شده مورد استفاده قرار گیرد. مقاله حاوی ارزیابی تجربی از الگوریتم در مجموعه ای بزرگ از نمونه های اتوماتیک درخت است.
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش مقاله
تعیین و تکمیل خودکار اتوماتیک درختی محدود
چکیده انگلیسی
Determinisation and completion of finite tree automata are important operations with applications in program analysis and verification. However, the complexity of the classical procedures for determinisation and completion is high. They are not practical procedures for manipulating tree automata beyond very small ones. In this paper we develop an algorithm for determinisation and completion of finite tree automata, whose worst-case complexity remains unchanged, but which performs far better than existing algorithms in practice. The critical aspect of the algorithm is that the transitions of the determinised (and possibly completed) automaton are generated in a potentially very compact form called product form, which can reduce the size of the representation dramatically. Furthermore, the representation can often be used directly when manipulating the determinised automaton. The paper contains an experimental evaluation of the algorithm on a large set of tree automata examples.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Logical and Algebraic Methods in Programming - Volume 95, February 2018, Pages 1-16
نویسندگان
, , ,