An efficient unique state coding algorithm for signal transition graphs

Current algorithms to force the complete state coding (CSC) property for signal transition graphs work on the state graph and, therefore require exponential time and space. Polynomial algorithms have been only proposed for marked graphs. In this paper, a P-time algorithm for unique state coding (USC) is presented. Although more restrictive than CSC, it is shown that the USC property can be efficiently guaranteed for large STGs. Several experiments evidence that the obtained results are even better than those generated by exponential-time techniquesPeer ReviewedPostprint (published version