Name
Abstract | ||
|---|---|---|
Well-known examples of dot operators are the existential, the counting, and the BP-operator. We will generalize this notion of a dot operator so that every language A will determine an operator A· . In fact, we will introduce the more general notion of promise dot operators for which the BP-operator is an example. Dot operators are a refinement of the leaf language concept because the class determined by a leaf language A equals A · P . Moreover, we are able to represent not only classes but reducibilities, in fact most of the known polynomial-time reducibilities can be represented by dot operators. We show that two languages determine the same dot operator if and only if they are reducible to each other by polylog-time computable monotone projections. |
Year | DOI | Venue |
|---|---|---|
2001 | 10.1016/S0304-3975(00)00323-6 | Theor. Comput. Sci. |
DocType | Volume | Issue |
Journal | 262 | 1-2 |
ISSN | Citations | PageRank |
Theoretical Computer Science | 1 | 0.35 |
References | Authors | |
24 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Bernd Borchert | 1 | 109 | 10.58 |
| Riccardo Silvestri | 2 | 1324 | 90.84 |