New Size Hierarchies for Two Way Automata
- Авторы: Ibrahimov R.1, Khadiev K.1,2, Yakaryılmaz A.2
-
Учреждения:
- Institute of Computational Mathematics and Information Technologies
- Center for Quantum Computer Science, Faculty of Computing
- Выпуск: Том 39, № 7 (2018)
- Страницы: 997-1009
- Раздел: Article
- URL: https://journals.rcsi.science/1995-0802/article/view/202813
- DOI: https://doi.org/10.1134/S1995080218070120
- ID: 202813
Цитировать
Аннотация
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.
Об авторах
R. Ibrahimov
Institute of Computational Mathematics and Information Technologies
Автор, ответственный за переписку.
Email: rishat.ibrahimov@yandex.ru
Россия, ul. Kremlevskaya 35, Kazan, Tatarstan, 420008
K. Khadiev
Institute of Computational Mathematics and Information Technologies; Center for Quantum Computer Science, Faculty of Computing
Email: rishat.ibrahimov@yandex.ru
Россия, ul. Kremlevskaya 35, Kazan, Tatarstan, 420008; Raina bulv. 19, Riga, LV-1586
A. Yakaryılmaz
Center for Quantum Computer Science, Faculty of Computing
Email: rishat.ibrahimov@yandex.ru
Латвия, Raina bulv. 19, Riga, LV-1586