Determining unambiguous degree of regular languages by automata.
Đặng Quyết Thắng, Nguyen Dinh Han, Phan Trung Huy · Journal of Computer Science and Cybernetics · 2012
In this paper, we introduce and study on unambiguous degree of languages, a new concept which fills the gap between code and unambiguity product notions. We can use some languages which are not codes but having finite unambiguous degree large enough for encrypting secret information... We propose algorithms to determine unambiguous degree of regular languages with time complexity O(n4) for the general case of non-deterministic automata, O(n2 logn) for the case of deterministic automata, where n is the number of states of finite automata recognizing these languages.