Uncountable Realtime Probabilistic Classes

被引：2

作者：

Dimitrijevs, Maksims ^{[1
]}

Yakaryilmaz, Abuzer ^{[1
]}

机构：

[1] Univ Latvia, Fac Comp, Raina Bulvaris 19, LV-1586 Riga, Latvia

来源：

DESCRIPTIONAL COMPLEXITY OF FORMAL SYSTEMS, DCFS 2017 | 2017年 / 10316卷

关键词：

COMPLEXITY; MACHINES; SPACE;

D O I：

10.1007/978-3-319-60252-3_8

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

We investigate the minimum cases for realtime probabilistic machines that can define uncountably many languages with bounded error. We show that logarithmic space is enough for realtime PTMs on unary languages. On binary case, we follow the same result for double logarithmic space, which is tight. When replacing the worktape with some limited memories, we can follow uncountable results on unary languages for two counters.

引用

页码：102 / 113

页数：12

共 9 条

[1] Quantum computability [J].

Adleman, LM ;

Demarrais, J ;

Huang, MDA .

SIAM JOURNAL ON COMPUTING, 1997, 26 (05) :1524-1540

[2]

[Anonymous], 1967, Computation

[3]

Chandrasekharan K., 1968, CHEBYSHEVS THEOREM D, P63

[4]

Dimitrijevs M., 2016, 8 WORKSH NONCL MOD A, V321, P131

[5]

Freivalds R., 1985, Topics in the Theory of Computation. Selected Papers of the International Conference on `Foundations of Computation Theory', FCT '83, P39

[6]

FREIVALDS R, 1983, LECT NOTES COMPUT SC, V158, P159

[7]

Kaneps J., 1997, Randomization and Approximation Techniques in Computer Science. International Workshop RANDOM '97 Proceedings, P187

[8]

Say A. C. C, 2016, TR14159 ECCC

[9] TIGHT BOUNDS FOR THE SPACE COMPLEXITY OF NONREGULAR LANGUAGE RECOGNITION BY REAL-TIME MACHINES [J].

Yakaryilmaz, Abuzer ;

Say, A. C. Cem .

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 2013, 24 (08) :1243-1253

← 1 →