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].
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.
Li and Pedrycz [Y. M. Li, W. Pedrycz, Fuzzy finite automata and fuzzy regular expressions with membership values in lattice ordered monoids, Fuzzy Sets and Systems 156 (2005) 68--92] have proved fundamental results that provide different equivalent ways to represent fuzzy languages with membership values in a lattice-ordered monoid, and generalize the well-known results of the classical theory of formal languages. In particular, they have shown that a fuzzy language over an integral lattice-ordered monoid can be represented by a fuzzy regular expression if and only if it can be recognized by a fuzzy finite automaton. However, they did not give any effective method for constructing an equivalent fuzzy finite automaton from a given fuzzy regular expression. In this paper we provide such an effective method. Transforming scalars appearing in a fuzzy regular expression {\alpha} into letters of the new extended alphabet, we convert the fuzzy regular expression {\alpha} to an ordinary regular expression {\alpha}_{R}. Then, starting from an arbitrary nondeterministic finite automaton A that recognizes the language ||{\alpha}_R|| represented by the regular expression {\alpha}_R, we construct fuzzy finite automata A_{\alpha} and A_{\alpha}^r with the same or even less number of states than the automaton A, which recognize the fuzzy language ||{\alpha}|| represented by the fuzzy regular expression {\alpha}. The starting nondeterministic finite automaton A can be obtained from {\alpha}_R using any of the well-known constructions for converting regular expressions to nondeterministic finite automata, such as Glushkov-McNaughton-Yamada's position automaton, Brzozowski's derivative automaton, Antimirov's partial derivative automaton, or Ilie-Yu's follow automaton.
This paper analyzes two approximation methods for the Laplacian eigenvectors of the Kronecker product, as recently presented in the literature. We enhance the approximations by comparing the correlation coefficients of the eigenvectors, which indicate how well an arbitrary vector approximates a matrix’s eigenvector. In the first method, some correlation coefficients are explicitly calculable, while others are not. In the second method, only certain coefficients can be estimated with good accuracy, as supported by empirical and theoretical evidence, with the rest remaining incalculable. The primary objective is to evaluate the accuracy of the approximation methods by analyzing and comparing limited sets of coefficients on one hand and the estimation on the other. Therefore, we compute the extreme values of the mentioned sets and theoretically compare them. Our observations indicate that, in most cases, the relationship between the majority of the values in the first set and those in the second set reflects the relationship between the remaining coefficients of both approximations. Moreover, it can be observed that each of the sets generally contains smaller values compared to the values found among the remaining correlation coefficients. Finally, we find that the performance of the two approximation methods is significantly influenced by imbalanced graph structures, exemplified by a class of almost regular graphs discussed in the paper.