Uncountable realtime probabilistic classes

DOI10.1007/978-3-319-60252-3_8zbMath1489.68123arXiv1705.01773OpenAlexW2962970555WikidataQ126565915 ScholiaQ126565915MaRDI QIDQ2400994

Maksims Dimitrijevs, Abuzer Yakaryılmaz

Publication date: 31 August 2017

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

Full work available at URL: https://arxiv.org/abs/1705.01773

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items

Uncountable realtime probabilistic classes ⋮ Uncountable classical and quantum complexity classes

Cites Work

• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• Turing machines with sublogarithmic space
• More on quantum, stochastic, and pseudo stochastic languages with few states
• Uncountable realtime probabilistic classes
• New Results on the Minimum Amount of Useful Space
• A Time Complexity Gap for Two-Way Probabilistic Finite-State Automata
• Quantum Computability
• TIGHT BOUNDS FOR THE SPACE COMPLEXITY OF NONREGULAR LANGUAGE RECOGNITION BY REAL-TIME MACHINES
• Uncountable classical and quantum complexity classes
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item