Factorizations of languages and commutativity conditions

Mateescu, Alexandru and Salomaa, Arto and Yu, Sheng: Factorizations of languages and commutativity conditions. In: Acta cybernetica, (15) 3. pp. 339-351. (2002)

[img] Cikk, tanulmány, mű

Download (822kB)


Representations of languages as a product (catenation) of languages are investigated, where the factor languages are "prime", that is, cannot be decomposed further in a nontrivial manner. In general, such prime decompositions do not necessarily exist. If they exist, they are not necessarily unique - the number of factors can vary even exponentially. The paper investigates prime decompositions, as well as the commuting of the factors, especially for the case of finite languages. In particular, a technique about commuting is developed in Section 4, where the factorization of languages L1 and L2 is discussed under the assumption L1L2 = L2L1.

Item Type: Article
Journal or Publication Title: Acta cybernetica
Date: 2002
Volume: 15
Number: 3
ISSN: 0324-721X
Page Range: pp. 339-351
Language: angol
Uncontrolled Keywords: Természettudomány
Additional Information: Bibliogr.: 351. p.; Abstract
Date Deposited: 2016. Oct. 15. 12:25
Last Modified: 2018. Jun. 05. 15:06
URI: http://acta.bibl.u-szeged.hu/id/eprint/12682

Actions (login required)

View Item View Item