Wyniki wyszukiwania - BazTech

Ograniczanie wyników

1 Fundamenta Informaticae

1 2021

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: Černý conjecture

Sortuj według:

Ogranicz wyniki do:

A Linear Bound on the k-rendezvous Time for Primitive Sets of NZ Matrices

Catalano Costanza, Azfar Umer, Charlier Ludovic, Jungers Raphaël M.

Fundamenta Informaticae

2021

Vol. 180, nr 4

289--314

A set of nonnegative matrices is called primitive if there exists a product of these matrices that is entrywise positive. Motivated by recent results relating synchronizing automata and primitive sets, we study the length of the shortest product of a primitive set having a column or a row with k positive entries, called its k-rendezvous time (k-RT), in the case of sets of matrices having no zero rows and no zero columns. We prove that the k-RT is at most linear w.r.t. the matrix size n for small k, while the problem is still open for synchronizing automata. We provide two upper bounds on the k-RT: the second is an improvement of the first one, although the latter can be written in closed form. We then report numerical results comparing our upper bounds on the k-RT with heuristic approximation methods.