Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10333903 | Theoretical Computer Science | 2011 | 6 Pages |
Abstract
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âCSâ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âLâ², Lâ²âL is infinite, and there is no context-sensitive language Lâ³, with Lâ³âLâ² unless Lâ³âL is finite; similarly, for every coinfinite regular language L there exists a context-sensitive language Lâ² such that LâLâ², Lâ²âL is infinite, and there is no regular language Lâ³ such that Lâ³âLâ², unless Lâ³âL is finite.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Claudio Marini, Giulia Simi, Andrea Sorbi, Marianna Sorrentino,