Infix-free regular expressions and languages

Y. O.Sub Han, Yajun Wang, Derick Wood

Research output: Contribution to journalArticlepeer-review

20 Citations (Scopus)


We study infix-free regular languages. We observe the structural properties of finite-state automata for infix-free languages and develop a polynomial-time algorithm to determine infix-freeness of a regular language using state-pair graphs. We consider two cases: 1) A language is specified by a nondeterministic finite-state automaton and 2) a language is specified by a regular expression. Furthermore, we examine the prime infix-free decomposition of infix-free regular languages and design an algorithm for the infix-free primality test of an infix-free regular language. Moreover, we show that we can compute the prime infix-free decomposition in polynomial time. We also demonstrate that the prime infix-free decomposition is not unique.

Original languageEnglish
Pages (from-to)379-393
Number of pages15
JournalInternational Journal of Foundations of Computer Science
Issue number2
Publication statusPublished - 2006 Apr

All Science Journal Classification (ASJC) codes

  • Computer Science (miscellaneous)


Dive into the research topics of 'Infix-free regular expressions and languages'. Together they form a unique fingerprint.

Cite this