2018/01/31 by Kamil Khadiev, Khadiev, Kamil, Rishat Ibrahimov +3
Biochemistry, Genetics and Molecular Biology · Computer Science · #Chemical Synthesis and Analysis #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Machine Learning and Algorithms #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1801.10483
openalex publication_date 2018/01/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.