On the existence of prime decompositions

Yo Sub Han, Arto Salomaa, Kai Salomaa, Derick Wood, Sheng Yu

Research output: Contribution to journalArticlepeer-review

16 Citations (Scopus)


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.

Original languageEnglish
Pages (from-to)60-69
Number of pages10
JournalTheoretical Computer Science
Issue number1-2
Publication statusPublished - 2007 May 10

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'On the existence of prime decompositions'. Together they form a unique fingerprint.

Cite this