CLOSURE PROPERTY OF PROBABILISTIC TURING MACHINES AND ALTERNATING TURING MACHINES WITH SUBLOGARITHMIC SPACES

DOI10.1142/S0129054101000552zbMath1319.68082OpenAlexW1988675160MaRDI QIDQ5249267

Géza Harváth, Akira Ito, Yue Wang, Katsushi Inoue

Publication date: 30 April 2015

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0129054101000552

zbMATH Keywords

closure propertyprobabilistic Turing machinesalternating Turing machinessubalgorithmic spaces

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cites Work

• A lower bound for probabilistic algorithms for finite state machines
• Some observations concerning alternating Turing machines using small space
• A note on two-way probabilistic automata
• The alternation hierarchy for sublogarithmic space is infinite
• A Time Complexity Gap for Two-Way Probabilistic Finite-State Automata
• Sublogarithmic-space turing machines, nonuniform space complexity, and closure properties
• ${\text{ASPACE}}(o(\log \log n))$ is Regular
• Computational Complexity of Probabilistic Turing Machines
• The Sublogarithmic Alternating Space World

This page was built for publication: CLOSURE PROPERTY OF PROBABILISTIC TURING MACHINES AND ALTERNATING TURING MACHINES WITH SUBLOGARITHMIC SPACES