Overlap-free regular languages

Yo Sub Han, Derick Wood

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Citations (Scopus)


We define a language to be overlap-free if any two distinct strings in the language do not overlap with each other. We observe that overlap-free languages are a proper subfamily of infix-free languages and also a proper subfamily of comma-free languages. Based on these observations, we design a polynomial-time algorithm that determines overlapfreeness of a regular language. We consider two cases: A language is specified by a nondeterministic finite-state automaton and a language is described by a regular expression. Furthermore, we examine the prime overlap-free decomposition of overlap-free regular languages and show that the prime overlap-free decomposition is not unique.

Original languageEnglish
Title of host publicationComputing and Combinatorics - 12th Annual International Conference, COCOON 2006, Proceedings
PublisherSpringer Verlag
Number of pages10
ISBN (Print)3540369252, 9783540369257
Publication statusPublished - 2006
Event12th Annual International Conference on Computing and Combinatorics, COCOON 2006 - Taipei, Taiwan, Province of China
Duration: 2006 Aug 152006 Aug 18

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4112 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other12th Annual International Conference on Computing and Combinatorics, COCOON 2006
Country/TerritoryTaiwan, Province of China

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


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

Cite this