Tianrong Lin

collaborators

2 papers

cs.CC2024

Simulating Polynomial-Time Nondeterministic Turing Machines via Nondeterministic Turing Machines

Tianrong Lin

We prove in this paper that there exists a language $L_{s}$ accepted by some nondeterministic Turing machine that runs within time $O (n^{k})$ for any positive integer $k\in\mathbb{N}_1…

cs.CC2012

On equivalence, languages equivalence and minimization of multi-letter and multi-letter measure-many quantum automata

Tianrong Lin

We first show that given a $k_{1}$ -letter quantum finite automata $A_{1}$ and a $k_{2}$ -letter quantum finite automata $A_{2}$ over the same input alphabet $Σ$ , they ar…