کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
382253 660750 2015 16 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Forward and backward synchronizing algorithms
ترجمه فارسی عنوان
الگوریتم های همگام سازی به جلو و عقب
کلمات کلیدی
هماهنگ سازی اتوماتیک، الگوریتم همگام سازی، لغو کلمه طول مجدد، ترتیب مجدد مدار پیوسته
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر هوش مصنوعی
چکیده انگلیسی


• We describe a general framework for constructing synchronizing algorithms.
• We design currently the best heuristic polynomial synchronizing algorithm.
• Detailed analysis shows impact of various parameters on the results.
• Experiments are conducted on much larger automata than in other studies up to date.

Automata synchronization has many important applications, mostly in conformance testing of electrical circuits, self-correcting codes and protocol testing. Finding a shortest synchronizing word cannot be done in polynomial time, assuming P ≠ NP. In some situations, especially for very large automata, finding such a word is almost impossible. Therefore, we accept any synchronizing word that is reasonably short and can be calculated in short time. The existing algorithms are either polynomial (quick, but not optimal) or exponential (exact, but useless in case of large automata). In this paper we present a flexible algorithmic framework for synchronization. It allows the user to parameterize the algorithm to obtain a desired balance in terms of a trade-off between memory usage, runtime and optimality. We also discuss many practical issues that affect efficiency of an implementation.In particular, we design a new polynomial backward algorithm, which works significantly better than previously used heuristic algorithms. Finally, we present detailed results of experiments involving automata up to 2000 states, which compare our algorithms in various settings and the other known algorithms, and check the impact of different parameters on the results.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Expert Systems with Applications - Volume 42, Issue 24, 30 December 2015, Pages 9512–9527
نویسندگان
, ,