Determining unambiguous degree of regular languages by automata.

Đặng Quyết Thắng, Nguyễn Đình Hân, Phan Trung Huy

Abstract


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.




DOI: https://doi.org/10.15625/1813-9663/28/1/1065 Display counter: Abstract : 176 views. PDF : 147 views. PDF (Tiếng Việt) : 18 views.

Oktrik

Journal of Computer Science and Cybernetics ISSN: 1813-9663

Published by Vietnam Academy of Science and Technology