Outfix-Free Regular Languages and Prime Outfix-Free Decomposition

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

Abstrakty

EN

A string x is an outfix of a string y if there is a string w such that x1wx2=y and x = x1x2. A set X of strings is outfix-free if no string in X is an outfix of any other string in X. Based on the properties of outfix strings, we develop a polynomial-time algorithm that determines outfix-freeness of regular languages. Note that outfix-free regular languages are always finite. We consider two cases: 1) a language is given as a finite set of strings and 2) a language is given by a finite-state automaton. Furthermore, we investigate the prime outfix-free decomposition of outfix-free regular languages and design a linear-time algorithm that computes prime outfix-free decomposition for outfix-free regular languages. We also demonstrate the uniqueness of prime outfix-free decomposition.

Słowa kluczowe

EN

regular language; outfix-freeness; prime decompositions

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2007
• Tom: Vol. 81, nr 4
• Strony: 441--457
• Opis fizyczny: bibliogr. 26 poz., wykr.

Twórcy

autor

Han Y-S.

autor

Wood D.

• Intelligence and Interaction Research Center, Korea Institute of Science and technology, P.O.Box 131, Cheongryang, Seoul, Korea,

Bibliografia

• [1] Béal, M.-P., Crochemore,M., Mignosi, F., Restivo, A., Sciortino,M.: Computing forbidden words of regular languages., Fundamenta Informaticae, 56(1-2), 2003, 121-135.
• [2] Clarke, C. L. A., Cormack, G. V.: On the use of regular expressions for searching text, ACM Transactions on Programming Languages and Systems, 19(3), 1997, 413-426.
• [3] Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein, C.: Introduction to Algorithms, McGraw-Hill Higher Education, 2001.
• [4] Crochemore,M., Mignosi, F., Restivo, A.: Automata and ForbiddenWords., Information Processing Letters, 67(3), 1998, 111-117.
• [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] Giammarresi, D.,Montalbano, R.: Deterministic Generalized Automata, Theoretical Computer Science, 215, 1999, 191-208.
• [7] Golomb, S., Gordon, B., Welch, L.: Comma-Free Codes, The Canadian Journal of Mathematics, 10, 1958, 202-209.
• [8] Han, Y.-S., Salomaa, K.,Wood, D.: Intercode Regular Languages, Fundamenta Informaticae, 76(1-2), 2007, 113-128.
• [9] Han, Y.-S., Trippen, G., Wood, D.: Simple-regular expressions and languages, Proceedings of DCFS'05, 2005, 146-157.
• [10] Han, Y.-S.,Wang, Y.,Wood, D.: Prefix-Free Regular-ExpressionMatching, Proceedings of CPM'05, Lecture Notes in Computer Science 3537, 2005, 298-309.
• [11] 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.
• [12] Han, Y.-S., Wood, D.: The Generalization of Generalized Automata: Expression Automata, International Journal of Foundations of Computer Science, 16(3), 2005, 499-510.
• [13] Han, Y.-S.,Wood, D.: Outfix-free Regular Languages and Prime Outfix-free Decomposition, Proceedings of ICTAC'05, Lecture Notes in Computer Science 3722, 2005, 96-109.
• [14] Hopcroft, J., Ullman, J.: Introduction to Automata Theory, Languages, and Computation, 2 edition, Addison-Wesley, Reading, MA, 1979.
• [15] Ito, M., Jürgensen, H., Shyr, H.-J., Thierrin, G.: N-prefix-suffix languages, International Journal of Computer Mathematics, 30, 1989, 37-56.
• [16] Ito, M., Jürgensen, H., Shyr, H.-J., Thierrin, G.: Outfix and Infix Codes and Related Classes of Languages, Journal of Computer and System Sciences, 43, 1991, 484-508.
• [17] Jürgensen, H.: Infix codes, Proceedings of Hungarian Computer Science Conference, 1984, 25-29.
• [18] Jürgensen, H., Konstantinidis, S.: Codes, in: Word, Language, Grammar (G. Rozenberg, A. Salomaa, Eds.), vol. 1 of Handbook of Formal Languages, Springer-Verlag, 1997, 511-607.
• [19] Kari, L.: On Language Equations with Invertible Operations., Theoretical Computer Science, 132(2), 1994, 129-150.
• [20] Long, D. Y., Ma, J., Zhou, D.: Structure of 3-infix-outfix maximal codes, Theoretical Computer Science, 188(1-2), 1997, 231-240.
• [21] Mateescu, A., Salomaa, A., Yu, S.: On the Decomposition of Finite Languages, Technical Report 222, TUCS, 1998.
• [22] Mateescu, A., Salomaa, A., Yu, S.: Factorizations of Languages and Commutativity Conditions, Acta Cybernetica, 15(3), 2002, 339-351.
• [23] Shyr, H., Yu, S.: Intercodes and some related properties., Soochow J. Math., 16(1), 1990, 95-107.
• [24] Shyr, H.-J.: Lecture Notes: Free Monoids and Languages, Hon Min Book Company, Taichung, Taiwan R.O.C, 1991.
• [25] Wood, D.: Theory of Computation, John Wiley & Sons, Inc., New York, NY, 1987.
• [26] Wood, D.: Data structures, algorithms, and performance, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1993.