On languages specified by relative acceptance |
| |
| Authors: | Ronald V Book Celia Wrathall |
| |
| Affiliation: | Department of Mathematics and Computer Science Program, University of California, Santa Barbara, CA 93106, U.S.A.;Department of Systems Science, University of California, Los Angeles, CA 90024, U.S.A. |
| |
| Abstract: | For any language A, the class NP(A) of languages accepted in polynomial time by nondeterministic oracle machines with A as oracle set is characterized in terms of the regular sets and the operations of homomorphic replication and intersection. A similar characterization is obtained for the class EXRUD(A) of languages that are extended rudimentary in A. Other classes which can be similarly characterized are described. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
