Tytuł artykułu
Wybrane pełne teksty z tego czasopisma
Identyfikatory
Warianty tytułu
Języki publikacji
Abstrakty
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
Wydawca
Czasopismo
Rocznik
Tom
Strony
441--457
Opis fizyczny
bibliogr. 26 poz., wykr.
Twórcy
autor
autor
- Intelligence and Interaction Research Center, Korea Institute of Science and technology, P.O.Box 131, Cheongryang, Seoul, Korea, emmous@kist.kr
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.
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-article-BUS5-0014-0050