Please use this identifier to cite or link to this item: http://hdl.handle.net/10995/102733
Title: Primitive sets of nonnegative matrices and synchronizing automata
Authors: Gerencsér, B.
Gusev, V. V.
Jungers, R. M.
Issue Date: 2018
Publisher: Society for Industrial and Applied Mathematics Publications
Citation: Gerencsér B. Primitive sets of nonnegative matrices and synchronizing automata / B. Gerencsér, V. V. Gusev, R. M. Jungers. — DOI 10.1137/16M1094099 // SIAM Journal on Matrix Analysis and Applications. — 2018. — Vol. 39. — Iss. 1. — P. 83-98.
Abstract: A set of nonnegative matrices M = {M1, M2,⋯, Mk} is called primitive if there exist possibly equal indices i1,i2,⋯, im such that Mi1 Mi2 ··· Mim is entrywise positive. The length of the shortest such product is called the exponent of M. Recently, connections between synchronizing automata and primitive sets of matrices were established. In the present paper, we strengthen these links by providing equivalence results, both in terms of combinatorial characterization and computational complexity. We pay special attention to the set of matrices without zero rows and columns, denoted by NZ, due to its intriguing connections to the Černý conjecture. We rely on synchronizing automata theory to derive a number of results about primitive sets of matrices. Making use of an asymptotic estimate by Rystsov [Cybernetics, 16 (1980), pp. 194-198], we show that the maximal exponent exp(n) of primitive sets of n×n matrices satisfy limn→∞ log exp(n)/n= log 3/3 and that the problem of deciding whether a given set of matrices is primitive is PSPACE-complete, even in the case of two matrices. Furthermore, we characterize the computational complexity of different problems related to the exponent of NZ matrix sets and present a bound of 2n2 - 5n + 5 on the exponent when considering the subclass of matrices having total support. © 2018 Society for Industrial and Applied Mathematics.
Keywords: CAREFULLY SYNCHRONIZING AUTOMATA
NONNEGATIVE MATRICES
PRIMITIVE SETS OF MATRICES
THE CERNY CONJECTURE
THE EXPONENT OF A MATRIX SET
COMPUTATIONAL COMPLEXITY
MATRIX ALGEBRA
SYNCHRONIZATION
ASYMPTOTIC ESTIMATES
NON-NEGATIVE MATRIX
PSPACE-COMPLETE
SYNCHRONIZING AUTOMATA
THE CERNY CONJECTURE
THE EXPONENT OF A MATRIX SET
AUTOMATA THEORY
URI: http://hdl.handle.net/10995/102733
Access: info:eu-repo/semantics/openAccess
SCOPUS ID: 85045763222
PURE ID: 7140259
c8e5be49-7dc9-4320-9600-0d48ee103996
ISSN: 8954798
DOI: 10.1137/16M1094099
Appears in Collections:Научные публикации, проиндексированные в SCOPUS и WoS CC

Files in This Item:
File Description SizeFormat 
2-s2.0-85045763222.pdf584,45 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.