JUCS - Journal of Universal Computer Science 16(5): 821-832, doi: 10.3217/jucs-016-05-0821
Ordered Catenation Closures and Decompositions of Languages Related to a Language of Derick Wood
expand article infoArto Salomaa‡
‡ Turku Centre for Computer Science, Turku, Finland

Corresponding author: Arto Salomaa ( asalomaa@utu.fi )

© Arto Salomaa.
This article is freely available under the J.UCS Open Content License.
Citation: Salomaa A (2010) Ordered Catenation Closures and Decompositions of Languages Related to a Language of Derick Wood. JUCS - Journal of Universal Computer Science 16(5): 821-832. https://doi.org/10.3217/jucs-016-05-0821
Open Access
Abstract
We investigate the problem of decomposing a language into a catenation of nontrivial languages, none of which can be decomposed further. In many cases this leads to the operation of an ordered catenation closure, introduced in this paper. We study properties of this operation, as well as its iterations. Special emphasis is on laid on ordered catenation closures of finite languages. It is also shown that if an infinite language is a code or a length code, then its ordered catenation closure does not possess a finite decomposition of indecomposable factors.
Keywords
decomposition of languages, indecomposable language, finite language, code, length code, ordered catenation closure