New Size Hierarchies for Two Way Automata

Abstract

We introduce a new type of nonuniform two-way automaton that can use a different transition function for each tape square. We also enhance this model by allowing to shuffle the given input at the beginning of the computation. Then we present some hierarchy and incomparability results on the number of states for the types of deterministic, nondeterministic, and bounded-error probabilistic models. For this purpose, we provide some lower bounds for all three models based on the numbers of subfunctions and we define two witness functions.

More by Kamil Khadiev

• Quantum Hashing Circuit Optimization for Arbitrary Qubit Connectivity Graphs Based on 1-Covering PatharXiv · 2026
• Quantum k-means based on Quantum Local Sensitive Hashing with Application to Irrigation Machine Sensors Data ClusteringIEEE International Conference on Smart Computing Workshops and Other Affiliated Events · 2026
• Circuits of Quantum Hashing and Quantum Fourier Transform for a Cactus as a Qubit Connectivity GrapharXiv · 2026
• Quantum Circuit for Quantum Fourier Transform for Arbitrary Qubit Connectivity Graphs Based on 1-Cover PathInternational Conference on Quantum Communications, Networking, and Computing · 2026 · Citations: 1