Miroslav Ćiríc: Systems of matrix equations and inequations and their applications in the theory of weighted automata, social network analysis and modal logic
Speaker: Miroslav Ćiríc, University of Niš, Faculty of Sciences and Mathematics, Department of Computer Science, Niš, Serbia
Title: Systems of matrix equations and inequations and their applications in the theory of weighted automata, social network analysis and modal logic
Abstract: In this lecture, I will briefly present the main ideas and results of my research group’s long-term work on the development of methods and algorithms for solving specific systems of matrix equattions and inequations having important applications in the theory of weighted automata, social network analysis and multimodal fuzzy logics.
Those systems emerged from research aimed at the fundamental problems of the theory of weighted automata – the comparison of the behavior of automata, where simulations and bisimulations play a key role, and the reduction of the number of states (called also the dimensionality reduction). In the linear representation of a weighted finite automaton over a semiring, the automaton is represented by a finite family of its transition matrices, as well as by its initial weights vector and terminal weights vector, while its behavior (the word function that the automaton computes) is defined by means of the products of these vectors and transition matrices that correspond to the letters of the input words for which the value of the function is computed. This allows to define simulations and bisimulations as matrices that are solutions of particular systems of matrix inequations and equations. Such simulations and bisimulations, if they exist, provide quantitative measures of the relationships between the states of different automata and testify to the existence of containment (in the case of simulations) or equivalence (in the case of bisimulations) between those automata. In addition, simulations and bisimulations that connect the states of the same automaton ensure the reduction of the number of states of that automaton, i.e. the construction of an equivalent automaton that has a smaller number of states.
The possibility and ways of solving these systems strongly depend on the properties of the semirings from which the weights are taken. In this respect, the semirings we have dealt with can be classified into two classes. The first of them consists of complete additively-idempotent semirings, which as their most important representatives include semiring reducts of various algebraic structures that are used as structures of truth values in fuzzy logic and fuzzy set theory (primarily com- plete residuated lattices), as well as the complete max-plus semiring and related semirings. The key property of complete additively-idempotent semirings, which allows us to solve systems of matrix inequations (the equations are treated as a system of two inequations), is the existence of residuation. The methodology we use is based on the well-known Knaster-Tarski Fixed-Point Theorem, which refers to the fixed-points of isotone functions on complete lattices, and a modification of the Kleene Fixed-Point Theorem. The second class consists of fields, where we are particularly focused on the field of real numbers, that is, on systems of inequations and equations for matrices with entries from the field of real numbers. A specific methodology was developed for solving those systems, based on the use of so-called zeroing neural networks (ZNN).
It turned out that a methodology similar to the one used in the study of weighted automata can also be employed in social network analysis and multimodal logics. I will present results that show how the concepts of quantitative simulations and bisimulations are used in positional analysis and blockmodeling of weighted social networks (known also as valued networks), as well as in determining the modal equivalence of Kripke models of multimodal fuzzy logics.
