P-disjunctive ω-languages

Abstract

An ω-language over a finite alphabet X is a set of infinite sequences of letters of X. An ω-language L is P-disjunctive if P _{ω, L} is the equality, where P _{ω, L} is the congruence on X* introduced by L. We prove that L contains a P-disjunctive ω-language if and only if L is P-dense. In order to determine whether a given ω-language is P-disjunctive or not, the concept of P-disjunctive domains is defined in this paper. And it is showed that P-disjunctive domains are equivalent to disjunctive domains.

Keywords:

• ω-language
• congruence
• P-disjunctivity
• P-disjunctive domain
• P-density

2000 AMS Subject Classification :

• 68Q70

Acknowledgements

We are grateful to the editor and the anonymous referees for the thorough comments which improved the paper. And thanks to Yun Liu, Aifang Feng, and Shoufeng Wang for their valuable comments and suggestions.