Geodesic
Certain linear and weakly linear systems of matrix equations over semirings. applications in a state reduction of weighted automata
Filomat, Tome 36 (2022) no. 8, p. 2775

Voir la notice de l'article provenant de la source eLibrary of Mathematical Institute of the Serbian Academy of Sciences and Arts

DOI

In this paper we study particular linear and weakly linear systems of matrix equations over semirings, with the aim of describing and computing functions as solutions to those systems. Our special attention is devoted to solutions whose ranks are as small as possible. We prove the existence of solutions with the smallest ranks, give their characterizations, and present a method for their computations. Regarding weakly linear systems, the method is based on the well known partition refinement algorithm by Kanellakis and Smolka, adapted to work with weighted labeled transition systems. Moreover, we give a state reduction procedure of weighted automata based on a decomposition of solutions to particular linear and weakly linear systems.
DOI : 10.2298/FIL2208775S
Classification : 15A24, 15A80, 16Y60, 68Q70
Keywords: Semirings, Matrices over semirings, Weakly linear system, Partition refinement, Weighted automata, State reduction 
Aleksandar Stamenković; Stefan Stanimirović; Vesa Halava. Certain linear and weakly linear systems of matrix equations over semirings. applications in a state reduction of weighted automata. Filomat, Tome 36 (2022) no. 8, p. 2775 . doi: 10.2298/FIL2208775S
@article{10_2298_FIL2208775S,
     author = {Aleksandar Stamenkovi\'c and Stefan Stanimirovi\'c and Vesa Halava},
     title = {Certain linear and weakly linear systems of matrix equations over semirings. applications in a state reduction of weighted automata},
     journal = {Filomat},
     pages = {2775 },
     year = {2022},
     volume = {36},
     number = {8},
     doi = {10.2298/FIL2208775S},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.2298/FIL2208775S/}
}
TY  - JOUR
AU  - Aleksandar Stamenković
AU  - Stefan Stanimirović
AU  - Vesa Halava
TI  - Certain linear and weakly linear systems of matrix equations over semirings. applications in a state reduction of weighted automata
JO  - Filomat
PY  - 2022
SP  - 2775 
VL  - 36
IS  - 8
UR  - http://geodesic.mathdoc.fr/articles/10.2298/FIL2208775S/
DO  - 10.2298/FIL2208775S
LA  - en
ID  - 10_2298_FIL2208775S
ER  - 
%0 Journal Article
%A Aleksandar Stamenković
%A Stefan Stanimirović
%A Vesa Halava
%T Certain linear and weakly linear systems of matrix equations over semirings. applications in a state reduction of weighted automata
%J Filomat
%D 2022
%P 2775 
%V 36
%N 8
%U http://geodesic.mathdoc.fr/articles/10.2298/FIL2208775S/
%R 10.2298/FIL2208775S
%G en
%F 10_2298_FIL2208775S

Cité par Sources :