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