A note on algebras of languages

作者：Marini Claudio; Simi Giulia; Sorbi Andrea^*; Sorrentino Marianna

来源：Theoretical Computer Science, 2011, 412(46): 6531-6536.

DOI：10.1016/j.tcs.2011.08.022

• Regular languages
• Context-sensitive languages
• Decidable languages
• Boolean algebras
• Algebras of languages
• Frechet ideal

We study the Boolean algebras R, CS, D of regular languages, context-sensitive languages and decidable languages, respectively, over any alphabet. It is well known that R subset of CS subset of D, with proper inclusions. After observing that these Boolean algebras are all isomorphic, we study some immunity properties: for instance we prove that for every coinfinite decidable language L there exists a decidable language L' such that L subset of L', L' - L is infinite, and there is no context-sensitive language L '', with L '' subset of L' unless L '' - L is finite; similarly, for every coinfinite regular language L there exists a context-sensitive language L' such that L subset of L', L' - L is infinite, and there is no regular language L '' such that L '' subset of L', unless L '' - L is finite.

• 出版日期2011-10-28