کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
8900477 | 1631597 | 2018 | 16 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Strongly connected synchronizing automata and the language of minimal reset words
ترجمه فارسی عنوان
اتوماتای همزمان همگام سازی شده و زبان حداقل کلمات بازنشانی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات کاربردی
چکیده انگلیسی
We approach the problem of finding strongly connected synchronizing automata with a given ideal I that serves as the set of reset words, by studying the set of minimal words M of the ideal I (no proper factor is a reset word). We first show the existence of an infinite strongly connected synchronizing automaton A having I as the set of reset words and such that every other strongly connected synchronizing automaton having I as the set of reset words is an homomorphic image of A. Finally, we show that for any non-unary regular ideal I there is a strongly connected synchronizing automaton having I as the set of reset words with at most (kmk)2kmkn states, where k is the dimension of the alphabet, m is twice the length of a shortest word in I, and n is the number of states of the smallest automaton recognizing M. This synchronizing automaton is computable and we exhibit an algorithm to compute it in time O((k2mk)2kmkn).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Advances in Applied Mathematics - Volume 99, August 2018, Pages 158-173
Journal: Advances in Applied Mathematics - Volume 99, August 2018, Pages 158-173
نویسندگان
Emanuele Rodaro,