A1 Refereed original research article in a scientific journal

Certain linear and weakly linear systems of matrix equations over semirings. Applications in a state reduction of weighted automata




AuthorsStamenković Aleksandar, Stanimirović Stefan, Halava Vesa

PublisherFilozofski fakultet

Publication year2022

JournalFilomat

Volume36

Issue8

eISSN2406-0933

DOIhttps://doi.org/10.2298/FIL2208775S(external)

Web address https://journal.pmf.ni.ac.rs/filomat/index.php/filomat/article/view/10983(external)


Abstract

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, themethod is based on thewell known partition refinement algorithmby Kanellakis and Smolka, adapted toworkwithweighted 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.



Last updated on 2024-26-11 at 22:22