A string x is an outfix of a string y if there is a string w such
that x
_1
wx
_2
= y and x = x
_1
x
_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.
