Han, Yo-Sub Salomaa, Kai Wood, Derick 2024-01-21T01:33:30Z 2024-01-21T01:33:30Z 2021-09-05 2007-02 0169-2968 https://pubs.kist.re.kr/handle/201004/134687 Intercodes are a generalization of comma-free codes. Using the structural properties of finite-state automata recognizing an intercode we develop a polynomial-time algorithm for determining whether or not a given regular language L is an intercode. If the answer is yes, our algorithm yields also the smallest index k such that L is a k-intercode. Furthermore, we examine the prime intercode decomposition of intercode regular languages and design an algorithm for the intercode primality test of an intercode recognized by a finite-state automaton. We also propose an algorithm that computes the prime intercode decomposition of an intercode regular language in polynomial time. Finally, we demonstrate that the prime intercode decomposition need not be unique. English IOS PRESS Intercode regular languages Article 1 FUNDAMENTA INFORMATICAE, v.76, no.1-2, pp.113 - 128 FUNDAMENTA INFORMATICAE 76 1-2 113 128 scie scopus 000245444000008 2-s2.0-33847746959 Computer Science, Software Engineering Mathematics, Applied Computer Science Mathematics Article regular languages finite-state automata intercodes state-pair graphs prime decompositions