RUS  ENG
Full version
JOURNALS // Zapiski Nauchnykh Seminarov POMI // Archive

Zap. Nauchn. Sem. POMI, 2001 Volume 277, Pages 5–13 (Mi znsl1426)

This article is cited in 1 paper

Combined hierarchies of finite random access machines

A. P. Beltiukov

Udmurt State University

Abstract: A finitary approach to the computational complexity theory is considered in the article. Classes of finite random access machines are investigated. Combined space-and-time computational complexity hierarchies of predicates (properties, sets) recognizable by these machines are built. The corresponding theorem is proved.

UDC: 510

Received: 29.04.2001


 English version:
Journal of Mathematical Sciences (New York), 2003, 118:2, 4943–4947

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024