Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
Tytuł artykułu

Quadratic Algorithms for Testing of Codes and ◊-Codes

Warianty tytułu
Języki publikacji
The Sardinas-Patterson's test for codes has contributed many effective testing algorithms to the development of theory of codes, formal languages, etc. However, we will show that a modification of this test proposed in this paper can deduce more effective testing algorithms for codes. As a consequence, we establish a quadratic algorithm that, given as input a regular language X defined by a tuple (ϕ, M, B), where ϕ : A* → M is a monoid morphism saturating X, M is a finite monoid, B Í M, X = ϕ−1(B), decides in time complexity O(n2) whether X is a code, where n = Card(M). Specially, n can be chosen as the finite index of X. A quadratic algorithm for testing of ◊-codes is also established.
Słowa kluczowe
Opis fizyczny
Bibliogr. 19 poz., rys.
  • Hung Yen University of Technology and Education, Dan Tien, Khoai Chau, Hung Yen, Viet Nam
  • Vinh University of Technology and Education, Hung Dung, Vinh, Viet Nam
  • Nam Dinh University of Technology and Education, Phu Nghia, Nam Dinh, Viet Nam
  • Ha Noi University of Science and Technology, No. 1 Dai Co Viet, Ha Noi, Viet Nam
  • [1] Andreas, W., Tom, H.: The Finest Homophonic Partition and Related Code Concepts, Lecture Notes in Computer Science, 841, 1994, 618–628.
  • [2] Anselmo, M.: On zigzag Codes and Their Decidability, Theoretical Computer Science, 74, 1990, 341–354.
  • [3] Bandyopadhyay, G.: A Simple Proof of the Decipherability Criterion of Sardinas and Patterson, Information and Control, 6, 1963, 331–336.
  • [4] Berstel, J., Perrin, D., Reutenauer, C.: Codes and Automata, Cambridge University Press, 2010.
  • [5] Bruyère, V., Wang, L., Zhang, L.: On Completion of Codes with Finite Deciphering Delay, Europ. J. Combinatorics, 11, 1990, 513–521.
  • [6] Burderi, F., Restivo, A.: Coding Partitions, Discrete Mathematics and Theoretical Computer Science, 9(2), 2007, 227–240.
  • [7] Tiplea, F.,Mäkinen, E., Trincă, D., Enea, C.: Characterization Results for Time-Varying Codes, Fundamenta Informaticae, 52(2), 2002, 185–198.
  • [8] Halava, V., Harju, T., Kärki, T.: Relational Codes of Words, Theoretical Computer Science, 389(1-2), 2007, 237–249.
  • [9] Han, N. D., Huy, P. T.: On Unambiguity of Languages Related to Codes, Future Information Technology, Application, and Service (James J. (Jong Hyuk) Park, Victor Leung, Taeshik Shon, Cho-Li Wang. Eds.), LNEE 179, Springer, Heidelberg, June 2012.
  • [10] Han, N. D., Vinh, H. N., Huy, P. T.: An Extension of Codes by Unambiguity of Languages, Proc. the Eighth International Conference on Intelligent Information Hiding and Multimedia Signal Processing (Jeng-Shyang Pan, Kebin Jia, Eds.), IEEE Computer Society, July 2012.
  • [11] Lallement, G.: Semigroups and Combinational Applications, JohnWiley and Sons, Inc, 1979.
  • [12] Madonia, M., Selemi, S., Sportelli, T.: A Generalization of Sardinas and Patterson’s Algorithm to z-Codes, Theoretical Computer Science, 108, 1993, 251–270.
  • [13] McCloskey, R.: An O(n2) Time Algorithm for Deciding Whether a Regular Language is a Code, Journal of Computing and Information, 2(1), 1996, 79–89.
  • [14] Perrin, D., ´Eric Pin, J.: Infinite Words, Automata, Semigroups, Logic and Games, Elsevier Inc, 2004.
  • [15] Rodeh,M.: A Fast Test for Unique Decipherability Based on Suffix Trees, IEEE Transactions on Information Theory, 28(4), 1982, 648–648.
  • [16] Van, D. L., Lam, N. H., Huy, P. T.: On Codes Concerning Bi-infinite Words, Acta Cybernetica, 11(1-2), 1993, 97–109.
  • [17] Van, D. L., Lesaëc, B., Litovsky, I.: On Coding Morphisms for zigzag Codes, Informatique Théorique et Applications, 26(6), 1992, 565–580.
  • [18] Vinh, H. N., Huy, P. T.: Codes of Bounded Words, Proc. the 3rd International Conference on Computer and Electrical Engineering, Section 2, V2-89, IEEE, November 2010.
  • [19] Vinh, H. N., Nam, V. T., Huy, P. T.: Codes Base on Unambiguous Products, Proc. Computational Collective Intelligence (J.-S Pan, S.-M. Chen, N.T. Nguyen, Eds.), Part III, LNCS 6423, Springer, Heidelberg, November 2010.
Typ dokumentu
Identyfikator YADDA
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.