Intercode Regular Languages

• Autorzy: Han Y-S. , Salomaa K. , Wood D.
• Języki publikacji: EN

Abstrakty

EN

Intercodes are a generalization of comma-free codes. Using the structural properties of finite-state automata recognizing an intercode we develop a polynomial-time algorithm for determining whether or not a given regular language L is an intercode. If the answer is yes, our algorithm yields also the smallest index k such that L is a k-intercode. Furthermore, we examine the prime intercode decomposition of intercode regular languages and design an algorithm for the intercode primality test of an intercode recognized by a finite-state automaton. We also propose an algorithm that computes the prime intercode decomposition of an intercode regular language in polynomial time. Finally, we demonstrate that the prime intercode decomposition need not be unique.

Słowa kluczowe

EN

regular language; finite state automata; intercodes; state-pair graphs; prime decompositions

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2007
• Tom: Vol. 76, nr 1-2
• Strony: 113--128
• Opis fizyczny: bibliogr. 23 poz.

Twórcy

autor

Han Y-S.

autor

Salomaa K.

autor

Wood D.

• System Technology Division, Korea Institute of Science and technology, P.O.Box 131, Cheongryang, Seoul, Korea,

Bibliografia

• [1] Berstel, J., Perrin, D.: Theory of Codes, Academic Press, Inc., 1985.
• [2] Berstel, J., Perrin, D.: Trends in the theory of codes, EATCS Bulletin, 29, 1986, 84-95.
• [3] Caron, P., Ziadi, D.: Characterization of Glushkov automata, Theoretical Computer Science, 233(1-2), 2000, 75-90.
• [4] Cormen, T.H., Leiserson, C.E., Rivest, R.L.,Stein, C.: Introduction to Algorithms, McGraw-Hill Higher Education, 2001.
• [5] Czyzowicz, J., Fraczak, W., Pelc, A., Rytter, W.: Linear-time prime decomposition of regular prefix codes, International Journal of Foundations of Computer Science, 14, 2003, 1019-1032.
• [6] Fernau, H., Reinhardt, K., Staiger, L.: Decidability of code properties, Proc. 4th International Conference Developments in Language Theory, (G. Rozenberg, W. Thomas, Eds.) World Scientific, Singapore, 2000, 153-160.
• [7] Giammarresi, D., Ponty, J.-L., Wood, D., Ziadi, D.: A characterization of Thompson digraphs, Discrete Applied Mathematics, 134, 2004, 317-337.
• [8] Glushkov, V.: The abstract theory of automata, Russian Mathematical Surveys, 16, 1961, 1-53.
• [9] Golomb, S., Gordon, B.,Welch, L.: Comma-free codes, The Canadian Journal of Mathematics, 10, 1958, 202-209.
• [10] Han, Y.-S., Salomaa, K., Wood, D.: Prime decompositions of regular languages, Proceedings of DLT'06, LNCS 4036, Springer-Verlag, 2006, 145-155.
• [11] Han, Y.-S., Wang, Y., Wood, D.: Prefix-free regular-expression matching, Proceedings of CPM'05, LNCS 3537, Springer-Verlag, 2005, 298-309.
• [12] Han, Y.-S., Wang, Y., Wood, D.: Infix-free regular expressions and languages, International Journal of Foundations of Computer Science, 17(2), 2006, 379-393.
• [13] Han, Y.-S., Wood, D.: Overlap-free regular languages, Proceedings of COCOON'06, LNCS 4112, Springer-Verlag, 2006, 469-478.
• [14] Han, Y.-S., Wood, D.: Outfix-free regular languages and prime outfix-free decomposition, Proceedings of ICTAC'05, LNCS 3722, Springer-Verlag, 2005, 96-109.
• [15] Jürgensen, H., Konstantinidis, S.: Codes, in: Word, Language, Grammar, volume 1 of Handbook of Formal Languages (G. Rozenberg, A. Salomaa, Eds.), Springer-Verlag, 1997, 511-607.
• [16] Jürgensen, H., Salomaa, K., Yu, S.: Decidability of the intercode property, Elektronische Informationsverarbeitung und Kybernetik, 29(6), 1993, 375-380.
• [17] Jürgensen, H., Salomaa, K., Yu, S.: Transducers and the decidability of independence in free monoids, Theoretical Computer Science, 134, 1994, 107-117.
• [18] Mateescu, A., Salomaa, A., Yu, S.: On the decomposition of finite languages, Technical Report 222, TUCS, 1998.
• [19] Mateescu, A., Salomaa, A., Yu, S.: Factorizations of languages and commutativity conditions, Acta Cybernetica, 15(3), 2002, 339-351.
• [20] McNaughton, R., Yamada, H.: Regular expressions and state graphs for automata, IEEE Transactions on Electronic Computers, 9, 1960, 39-47.
• [21] Shyr, H., Yu, S.S.: Intercodes and some related properties, Soochow J. Math., 16(1), 1990, 95-107.
• [22] Thompson, K.: Regular expression search algorithm, Communications of the ACM, 11, 1968, 419-422.
• [23] Yu, S.S.: A characterization of intercodes, International Journal of Computer Mathematics, 36, 1990, 39-45.