Abstract
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 language | English |
|---|---|
| Pages (from-to) | 1197-1209 |
| Number of pages | 13 |
| Journal | International Journal of Foundations of Computer Science |
| Volume | 22 |
| Issue number | 5 |
| DOIs | |
| Publication status | Published - 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)