Improved algorithms for computing the greatest right and left invariant Boolean matrices and their application | Zendy

Stefan Stanimirović | Zendy; Aleksandar Stamenković | Zendy; Miroslav Ćirić | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Improved algorithms for computing the greatest right and left invariant Boolean matrices and their application

Author(s) -

Stefan Stanimirović,

Aleksandar Stamenković,

Miroslav Ćirić

Publication year - 2019

Publication title -

filomat

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.449

H-Index - 34

eISSN - 2406-0933

pISSN - 0354-5180

DOI - 10.2298/fil1909809s

Subject(s) - mathematics , idempotence , invariant (physics) , commutative property , automaton , discrete mathematics , partition (number theory) , algebra over a field , combinatorics , pure mathematics , theoretical computer science , computer science , mathematical physics

We define right and left invariant matrices as Boolean matrices that are solutions to certain systems of matrix equations and inequalities over additively idempotent semirings. We provide improved algorithms for computing the greatest right and left invariant equivalence and quasi-order matrices. The improvements are based on the usage of the well-known partition refinement technique. Afterwards, we present the application of right invariant matrices in the determinization of weighted automata over additively idempotent, commutative and zero-divisor free semirings. In particular, we provide improvements of the well-known determinization method of weighted automata over tropical semirings given by Mohri [Computational Linguistics 23 (2) (1997) 269–311].

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research