Han, Yo-Sub Salomaa, Arto Salomaa, Kai Wood, Derick Yu, Sheng 2024-01-21T01:02:47Z 2024-01-21T01:02:47Z 2021-09-02 2007-05-10 0304-3975 https://pubs.kist.re.kr/handle/201004/134395 We investigate factorizations of regular languages in terms of prime languages. A language is said to be strongly prime decomposable if any way of factorizing it yields a prime decomposition in a finite number of steps. We give a characterization of the strongly prime decomposable regular languages and using the characterization we show that every regular language over a unary alphabet has a prime decomposition. We show that there exist non-regular unary languages that do not have prime decompositions. We also consider infinite factorizations of unary languages. (C) 2007 Elsevier B.V. All rights reserved. English ELSEVIER SCIENCE BV FINITE SETS LANGUAGES AUTOMATA EQUATIONS WORDS On the existence of prime decompositions Article 10.1016/j.tcs.2007.01.013 1 THEORETICAL COMPUTER SCIENCE, v.376, no.1-2, pp.60 - 69 THEORETICAL COMPUTER SCIENCE 376 1-2 60 69 scie scopus 000246375200007 2-s2.0-34147186347 Computer Science, Theory & Methods Computer Science Article; Proceedings Paper FINITE SETS LANGUAGES AUTOMATA EQUATIONS WORDS language decompositions primality unary languages