2025/11/21 by Daowen Qiu, Qiu, Daowen
Computer Science · Biochemistry, Genetics and Molecular Biology · #Quantum Computing Algorithms and Architecture #DNA and Biological Computing #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2511.17264
Multi-stack machines and Turing machines can simulate to each other. In this note, we give a succinct definition of multi-stack machines, and from this definition it is clearly seen that pushdown automata and deterministic finite automata are special cases of multi-stack machines. Also, with this mode of definition, pushdown automata and deterministic pushdown automata are equivalent and recognize all context-free languages. In addition, we are motivated to formulate concise definitions of quantum pushdown automata and quantum stack machines.