A Linear Bound on the K-Rendezvous Time for Primitive Sets of NZ Matrices

Azfar, Umer;Catalano, Costanza;Charlier, Ludovic;Jungers, Raphaël
(2019) International Conference on Developments in Language Theory — Location: Warsaw, Poland (5.August.2019)

Files

Azfar2019_Chapter_ALinearBoundOnTheK-RendezvousT.pdf
  • Open Access
  • Adobe PDF
  • 556.42 KB
Download

Details

Authors
  • Azfar, UmerUCLouvain
    Author
  • Catalano, CostanzaGran Sasso Science Institute, L’Aquila, Italy
    Author
  • Charlier, LudovicUCLouvain
    Author
  • Jungers, RaphaëlUCLouvain
    Author
Abstract
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 (the k-RT). We prove that this value is at most linear w.r.t. the matrix size n for small k, while the problem is still open for synchronizing automata. We then report numerical results comparing our upper bound on the k-RT with heuristic approximation methods.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Azfar, U., Catalano, C., Charlier, L., & Jungers, R. (2019). A Linear Bound on the K-Rendezvous Time for Primitive Sets of NZ Matrices. Developments in Language Theory : Lecture Notes in Computer Science, p. 59-73. https://doi.org/10.1007/978-3-030-24886-4_4