●Project title:

QUANTITATIVE AUTOMATA MODELS: FUNDAMENTAL PROBLEMS AND APPLICATIONS●Acronym:

QUAM●Sub-program:

Natural sciences and mathematics●Participating Scientific and Research Organizations (SROs) and their acronyms:

University of Niš, Faculty of Sciences and Mathematics - UNFSM

University of Kragujevac, Faculty of Technical Sciences in Čačak - FTSC

University of Niš, Faculty of Pedagogy in Vranje - UNFPV

University of Kragujevac, Faculty of Sciences - FSUKG●Principal Investigator (PI):

Miroslav Ćirić, PhD, Full Professor, University of Niš, Faculty of Sciences and Mathematics● Abstract:

The general objective of the Project is to contribute to the development of the theory of quantitative automata, especially weighted automata over semirings, and thus to contribute to further revision of fundaments of Computer Science in which classical Boolean methods for modeling and analysis of hardware and software systems are increasingly replaced by quantitative methods. The Project primarily address several extremely important general problems of automata theory: comparing the behaviour of automata, finding simulations and bisimulations, state reduction and minimization, determinization, reconstruction of an automaton from its behaviour and extraction of an automaton from a black-box model. These problems are considered in the general context of weighted finite automata over semirings, but even more intensively for three particularly important types of weighted automata - weighted finite automata over the field of real numbers, max-plus automata and fuzzy finite automata. The methodology by which the mentioned problems are attacked is based on the linear representation of weighted automata over semirings, and such a representation allows the methods and ideas of linear algebra and matrix theory to be used in solving these problems. In particular, the problems of finding simulations and bisimulations, as well as the problem of reducing the number of states, boil down to the problem of solving particular systems of matrix inequations and equations, while solving the problems of reconstruction and minimization is based on matrix factorizations and generalized inverses of matrices. Consequently, the legitimate subject of the Project will also be research in the area of solving systems of matrix inequations and equations, matrix factorizations and computing generalized inverses. The project also enters into the field of machine learning and address the issue of learning weighted automata