6 citations · 8 across the 10 of their papers we have counts for
10 papers
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 for every and a…
On Probabilistic -Pushdown Systems, and -Probabilistic Computational Tree Logic
Deren Lin, Tianrong Lin
In this paper, we define the notion of a {\em probabilistic -pushdown automaton} and study its model-checking problem against -probabilistic computational tree logic (-PCT…
On Baker-Gill-Solovay Oracle Turing Machines and Relativization Barrier
Tianrong Lin
This work analyses the so-called "Relativization Barrier" with respect to the Baker-Gill-Solovay oracle Turing machine. We show that the {\em diagonalization} technique is a valid…
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…
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…
The Separation of and
Tianrong Lin
There is an important and interesting open question in computational complexity on the relation between the complexity classes and . It is a widesp…
Undecidability of MM-QFAs Language Equivalence Problem
Tianrong Lin
Let and be the languages recognized by {\em measure many 1-way quantum finite automata (MM-QFA)} (or,{\em enhanced 1-way quantum fini…
Simple characterizations for commutativity of quantum weakest preconditions
Tianrong Lin
In a recent letter [Information Processing Letters~104 (2007) 152-158], it has shown some sufficient conditions for commutativity of quantum weakest preconditions. This paper provi…
Some results on equivalence of multi-letter quantum finite automata
Tianrong Lin
Two quantum finite automata are equivalent if for all input string over the input alphabet the two automata accept with equal probability. In [Theoret. Comput. Sci. 410 (20…
Another approach to the equivalence of measure-many one-way quantum finite automata and its application
Tianrong Lin
In this paper, we present a much simpler, more direct, and more elegant approach to the equivalence problem for {\it measure-many one-way quantum finite automata} (MM-1QFAs). The a…