Mahajan, Meena ; Krithivasan, Kamala (1992) Some results on time-varying and relativised cellular automata* International Journal of Computer Mathematics, 43 (1-2). pp. 21-38. ISSN 0020-7160
Full text not available from this repository.
Official URL: http://doi.org/10.1080/00207169208804070
Related URL: http://dx.doi.org/10.1080/00207169208804070
Abstract
Cellular automata (CA) are parallel language recognition devices. In this paper, the notion of a time-varying CA (TVCA) is introduced. In a TVCA, the transition function can vary with time, and the variation is controlled by a prespecified language. This language can be viewed as an oracle to which the TVCA makes implicit queries; thus TVCA provide a mechanism for defining relativised CA. In this paper, the recognition capabilities of CA and TVCA are compared. TVCA as relativised CA are formalised, and the power of this implicit query mechanism is compared with the traditional oracle access in Turing machines.
| Item Type: | Article |
|---|---|
| Source: | Copyright of this article belongs to England & Wales. |
| Keywords: | Cellular automata; Turing machines; Relativisations; Language recognition |
| ID Code: | 128008 |
| Deposited On: | 14 Oct 2022 11:28 |
| Last Modified: | 14 Oct 2022 11:28 |
Repository Staff Only: item control page
