کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
695231 | 1460654 | 2015 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On primitivity of sets of matrices
ترجمه فارسی عنوان
بر روی ظرافت مجموعه ای از ماتریس ها
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
ماتریس غیر انتزاعی، نظریه پیچیدگی، مسیرهای دولتی، شبکه های مجازی الگوریتم های کنترل،
موضوعات مرتبط
مهندسی و علوم پایه
سایر رشته های مهندسی
کنترل و سیستم های مهندسی
چکیده انگلیسی
We show that while primitivity is algorithmically decidable, unless P=NP it is not possible to decide primitivity of a matrix set in polynomial time. Moreover, we show that the length of the shortest positive sequence can be superpolynomial in the dimension of the matrices. On the other hand, defining P to be the set of matrices with no zero rows or columns, we give a combinatorial proof of the Protasov-Voynov characterization (2012) of primitivity for matrices in P which can be tested in polynomial time. This latter observation is related to the well-known 1964 conjecture of Äerný on synchronizing automata; in fact, any bound on the minimal length of a synchronizing word for synchronizing automata immediately translates into a bound on the length of the shortest positive product of a primitive set of matrices in P. In particular, any primitive set of nÃn matrices in P has a positive product of length O(n3).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Automatica - Volume 61, November 2015, Pages 80-88
Journal: Automatica - Volume 61, November 2015, Pages 80-88
نویسندگان
Vincent D. Blondel, Raphaël M. Jungers, Alex Olshevsky,