Tianrong Lin

collaborators

5 papers

cs.LO2026

On Probabilistic $I ¨ $ -Pushdown Systems, and $I ¨ $ -Probabilistic Computational Tree Logic

Deren Lin, Tianrong Lin

In this paper, we define the notion of a {\em probabilistic $I ¨ $ -pushdown automaton} and study its model-checking problem against $I ¨ $ -probabilistic computational tree logic ( $I ¨ $ -…

cs.CC2026

Probabilistic Computers (and Hence Quantum Computers) Are Rigorously More Powerful Than Classical Deterministic Computers, and Derandomization

Tianrong Lin

In this paper, we extend the techniques developed in our previous work to construct a probabilistic Turing machine that runs within time $O (n^{k})$ for every $k \in N_{1}$ and a…

cs.CC2025

Diagonalization of Polynomial-Time Deterministic Turing Machines via Nondeterministic Turing Machines

Tianrong Lin

The {\em diagonalization technique} was invented by Georg Cantor to show that there are more real numbers than algebraic numbers and is very crucial in {\em theoretical computer sc…

cs.CC2025

Resolution of The Linear-Bounded Automata Question

Tianrong Lin

This paper resolves a famous and longstanding open question in automata theory, i.e., the {\it linear-bounded automata question} (or, for short, the LBA question), which can also b…

cs.CC2025

The Separation of $N P$ and $P S P A C E$

Tianrong Lin

There is an important and interesting open question in computational complexity on the relation between the complexity classes $NP$ and $P S P A C E$ . It is a widesp…

On Probabilistic I¨-Pushdown Systems, and I¨-Probabilistic Computational Tree Logic

Probabilistic Computers (and Hence Quantum Computers) Are Rigorously More Powerful Than Classical Deterministic Computers, and Derandomization

Diagonalization of Polynomial-Time Deterministic Turing Machines via Nondeterministic Turing Machines

Resolution of The Linear-Bounded Automata Question

The Separation of NP and PSPACE

On Probabilistic $I ¨ $ -Pushdown Systems, and $I ¨ $ -Probabilistic Computational Tree Logic

The Separation of $N P$ and $P S P A C E$