کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
436544 690013 2013 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Groups synchronizing a transformation of non-uniform kernel
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Groups synchronizing a transformation of non-uniform kernel
چکیده انگلیسی

Suppose that a deterministic finite automata A=(Q,Σ) is such that all but one letters from the alphabet Σ act as permutations of the state set Q and the exceptional letter acts as a transformation with non-uniform kernel. Which properties of the permutation group G generated by the letters acting as permutations ensure that A becomes a synchronizing automaton under every possible choice of the exceptional letter (provided the exceptional letter acts as a transformation of non-uniform kernel)? Such permutation groups are called almost synchronizing. It is easy to see that an almost synchronizing group must be primitive; our conjecture is that every primitive group is almost synchronizing.Clearly every synchronizing group is almost synchronizing. In this paper we provide two different methods to find non-synchronizing, but almost synchronizing groups. The infinite families of examples provided by the two different methods have few overlaps.The paper closes with a number of open problems on group theory and combinatorics.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 498, 5 August 2013, Pages 1-9