Quadratic Algorithms for Testing of Codes and ◊-Codes

• Autorzy: Han N. D. , Vinh H. N. , Thang D. Q. , Huy P. T.

Identyfikatory

DOI

10.3233/FI-2014-986

• Języki publikacji: EN

Abstrakty

EN

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

EN

Sardinas-Patterson; quadratic algorithm; monoid; code; ◊-code

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2014
• Tom: Vol. 130, nr 2
• Strony: 163--177
• Opis fizyczny: Bibliogr. 19 poz., rys.

Twórcy

autor

Han N. D.

• Hung Yen University of Technology and Education, Dan Tien, Khoai Chau, Hung Yen, Viet Nam

autor

Vinh H. N.

• Vinh University of Technology and Education, Hung Dung, Vinh, Viet Nam

autor

Thang D. Q.

• Nam Dinh University of Technology and Education, Phu Nghia, Nam Dinh, Viet Nam

autor

Huy P. T.

• Ha Noi University of Science and Technology, No. 1 Dai Co Viet, Ha Noi, Viet Nam

Bibliografia

• [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.