Name
Abstract | ||
|---|---|---|
An infinite and co-infinite setA is bi-immune for a complexity classC if neitherA nor its complement has an infinite subset inC. We prove various equivalent characterizations of this notion. Also, we introduce a stronger version of bi-immunity and show how both notions relate to density and other properties of sets in EXPTIME. |
Year | DOI | Venue |
|---|---|---|
1985 | 10.1007/BF01699457 | Theory of Computing Systems \/ Mathematical Systems Theory |
Keywords | Field | DocType |
Computational Mathematic,Complexity Class,Strong Version,Equivalent Characterization,Infinite Subset | Complexity class,Discrete mathematics,Combinatorics,EXPTIME,Mathematics | Journal |
Volume | Issue | ISSN |
18 | 1 | 1433-0490 |
Citations | PageRank | References |
65 | 7.06 | 12 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| José L. Balcázar | 1 | 701 | 62.06 |
| Uwe Schöning | 2 | 998 | 105.69 |