Outfix-Free Regular Languages and Prime Outfix-Free Decomposition

Article type: Research Article

Authors: Han, Yo-Sub | Wood, Derick

Affiliations: Intelligence and Interaction Research Center, Korea Institute of Science and Technology, P.O. BOX 131, Cheongryang, Seoul, Korea. E-mail: emmous@kist.re.kr | Department of Computer Science, Hong Kong University of Science and Technology, Clear Water Bay, Kowloon, Hong Kong SAR. E-mail: dwood@cs.ust.hk

Abstract: A string x is an outfix of a string y if there is a string w such that x_1wx_2 = y and x = x_1x_2. 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 outfixfree 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.

Keywords: regular languages, outfix-freeness, prime decomposition

Journal: Fundamenta Informaticae, vol. 81, no. 4, pp. 441-457, 2007