Advertisement

Outfix-Free Regular Languages and Prime Outfix-Free Decomposition

  • Yo-Sub Han
  • Derick Wood
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 3722)

Abstract

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

Keywords

Regular Expression Regular Language Simple Path Prime Decomposition Decomposition Problem 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. 1.
    Béal, M.-P., Crochemore, M., Mignosi, F., Restivo, A., Sciortino, M.: Computing forbidden words of regular languages. Fundamenta Informaticae 56(1-2), 121–135 (2003)zbMATHMathSciNetGoogle Scholar
  2. 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), 413–426 (1997)CrossRefGoogle Scholar
  3. 3.
    Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. McGraw-Hill Higher Education, New York (2001)zbMATHGoogle Scholar
  4. 4.
    Crochemore, M., Mignosi, F., Restivo, A.: Automata and forbidden words. Information Processing Letters 67(3), 111–117 (1998)CrossRefMathSciNetGoogle Scholar
  5. 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, 1019–1032 (2003)zbMATHCrossRefMathSciNetGoogle Scholar
  6. 6.
    Giammarresi, D., Montalbano, R.: Deterministic generalized automata. Theoretical Computer Science 215, 191–208 (1999)zbMATHCrossRefMathSciNetGoogle Scholar
  7. 7.
    Han, Y.-S., Trippen, G., Wood, D.: Simple-regular expressions and languages. In: Proceedings of DCFS 2005, pp. 146–157 (2005)Google Scholar
  8. 8.
    Han, Y.-S., Wang, Y., Wood, D.: Infix-free regular expressions and languages. To appear in International Journal of Foundations of Computer Science (2005)Google Scholar
  9. 9.
    Han, Y.-S., Wang, Y., Wood, D.: Prefix-free regular-expression matching. In: Apostolico, A., Crochemore, M., Park, K. (eds.) CPM 2005. LNCS, vol. 3537, pp. 298–309. Springer, Heidelberg (2005)CrossRefGoogle Scholar
  10. 10.
    Han, Y.-S., Wood, D.: The generalization of generalized automata: Expression automata. International Journal of Foundations of Computer Science 16(3), 499–510 (2005)zbMATHCrossRefMathSciNetGoogle Scholar
  11. 11.
    Ito, M., Jürgensen, H., Shyr, H.-J., Thierrin, G.: N-prefix-suffix languages. International Journal of Computer Mathematics 30, 37–56 (1989)zbMATHCrossRefGoogle Scholar
  12. 12.
    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, 484–508 (1991)zbMATHCrossRefMathSciNetGoogle Scholar
  13. 13.
    Jürgensen, H.: Infix codes. In: Proceedings of Hungarian Computer Science Conference, pp. 25–29 (1984)Google Scholar
  14. 14.
    Jürgensen, H., Konstantinidis, S.: Codes. In: Rozenberg, G., Salomaa, A. (eds.) Word, Language, Grammar. Handbook of Formal Languages, vol. 1, pp. 511–607. Springer, Heidelberg (1997)Google Scholar
  15. 15.
    Long, D.Y., Ma, J., Zhou, D.: Structure of 3-infix-outfix maximal codes. Theoretical Computer Science 188(1-2), 231–240 (1997)zbMATHCrossRefMathSciNetGoogle Scholar
  16. 16.
    Mateescu, A., Salomaa, A., Yu, S.: On the decomposition of finite languages. Technical Report 222, TUCS (1998)Google Scholar
  17. 17.
    Mateescu, A., Salomaa, A., Yu, S.: Factorizations of languages and commutativity conditions. Acta Cybernetica 15(3), 339–351 (2002)zbMATHMathSciNetGoogle Scholar
  18. 18.
    Shyr, H.-J.: Lecture Notes: Free Monoids and Languages. Hon Min Book Company, Taichung (1991)Google Scholar
  19. 19.
    Wood, D.: Data structures, algorithms, and performance. Addison-Wesley Longman Publishing Co., Inc., Boston (1993)zbMATHGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2005

Authors and Affiliations

  • Yo-Sub Han
    • 1
  • Derick Wood
    • 1
  1. 1.Department of Computer ScienceThe Hong Kong University of Science and Technology 

Personalised recommendations