TY - GEN

T1 - Outfix-free regular languages and prime outfix-free decomposition

AU - Han, Yo Sub

AU - Wood, Derick

PY - 2005

Y1 - 2005

N2 - A string x is an outfix of a string y if there is a string w such that x 1wx 2 = y, where x = x 1x 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.

AB - A string x is an outfix of a string y if there is a string w such that x 1wx 2 = y, where x = x 1x 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.

UR - http://www.scopus.com/inward/record.url?scp=33646389805&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33646389805&partnerID=8YFLogxK

U2 - 10.1007/11560647_6

DO - 10.1007/11560647_6

M3 - Conference contribution

AN - SCOPUS:33646389805

SN - 3540291075

SN - 9783540291077

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 96

EP - 109

BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

T2 - 2nd International Colloquium on Theoretical Aspects of Computing - ICTAC 2005

Y2 - 17 October 2005 through 21 October 2005

ER -