Free submonoids and minimal ω-generators of Rω

Let A be an alphabet and let R be a language in A+. An (¿-generator of -R" is a language G such that G" = R". The language Stab(-R") = {u G A* : ttiZ" Ç R"} is a submonoid of A*. We give results concerning the wgenerators for the case when Stab(Ru ) is a free submonoid...

Full description

Saved in:
Bibliographic Details
Main Author: Litovsky Igor
Format: Article
Published: 1991
Series:Acta cybernetica 10 No. 1-2
Kulcsszavak:Számítástechnika, Kibernetika
Subjects:
Online Access:http://acta.bibl.u-szeged.hu/12491
Description
Summary:Let A be an alphabet and let R be a language in A+. An (¿-generator of -R" is a language G such that G" = R". The language Stab(-R") = {u G A* : ttiZ" Ç R"} is a submonoid of A*. We give results concerning the wgenerators for the case when Stab(Ru ) is a free submonoid which are not available in the general case. In particular, we prove that every ((»-generator of 22" contains at least one minimal w-generator of R". Furthermore these minimal w-generators are codes. We also characterize the w-languagea having only finite languages as minimal u-generators. Finally, we characterize the w- languages »-generated by finite prefix codes.
Physical Description:35-43
ISSN:0324-721X