Han, Yo-Sub Wood, Derick 2024-01-21T02:35:05Z 2024-01-21T02:35:05Z 2021-09-02 2006-08 0302-9743 https://pubs.kist.re.kr/handle/201004/135286 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 overlap-freeness 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. English SPRINGER-VERLAG BERLIN EXPRESSIONS Overlap-free regular languages Article 1 COMPUTING AND COMBINATORICS, PROCEEDINGS, v.4112, pp.469 - 478 COMPUTING AND COMBINATORICS, PROCEEDINGS 4112 469 478 scie scopus 000240077300049 2-s2.0-33749541514 Computer Science, Theory & Methods Mathematics Computer Science Mathematics Article; Proceedings Paper EXPRESSIONS overlap-freeness regular languages