Overlap-free languages and solid codes

Yo Sub Han, Kai Salomaa

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)


Solid codes have a nice property called synchronization property, which is useful in data transmission. The property is derived from infix-freeness and overlap-freeness of solid codes. Since a code is a language, we look at solid codes from formal language viewpoint. In particular, we study regular solid codes (that are solid codes and regular). We first tackle the solid code decidability problem for regular languages and propose a polynomial time algorithm. We, then, investigate the decidability of the overlap-freeness property and show that it is decidable for regular languages but is undecidable for context-free languages. Then, we study the prime solid code decomposition of regular solid codes and propose an efficient algorithm for the prime solid code decomposition problem. We also demonstrate that a solid code does not always have a unique prime solid code decomposition.

Original languageEnglish
Pages (from-to)1197-1209
Number of pages13
JournalInternational Journal of Foundations of Computer Science
Issue number5
Publication statusPublished - 2011 Aug

Bibliographical note

Funding Information:
Han was supported by the IT R&D program of MKE/IITA 2008-S-024-01 and the Basic Science Research Program through NRF funded by MEST (2010-0009168). Salomaa was supported by the Natural Sciences and Engineering Research Council of Canada Grant OGP0147224.

All Science Journal Classification (ASJC) codes

  • Computer Science (miscellaneous)


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

Cite this