New Size Hierarchies for Two Way Automata
| العنوان: | New Size Hierarchies for Two Way Automata |
|---|---|
| المؤلفون: | Kamil Khadiev, Rishat Ibrahimov, Abuzer Yakaryilmaz |
| المصدر: | Lobachevskii Journal of Mathematics. 39:997-1009 |
| بيانات النشر: | Pleiades Publishing Ltd, 2018. |
| سنة النشر: | 2018 |
| مصطلحات موضوعية: | Hierarchy, TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES, Theoretical computer science, Transition function, General Mathematics, Computation, 010102 general mathematics, Probabilistic logic, 0102 computer and information sciences, Type (model theory), 01 natural sciences, Square (algebra), Automaton, Nondeterministic algorithm, 010201 computation theory & mathematics, 0101 mathematics, Computer Science::Formal Languages and Automata Theory, Mathematics |
| الوصف: | 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. |
| تدمد: | 1818-9962 1995-0802 |
| URL الوصول: | https://explore.openaire.eu/search/publication?articleId=doi_________::2c31c741188311e2dc058d631ea29bfb https://doi.org/10.1134/s1995080218070120 |
| حقوق: | OPEN |
| رقم الأكسشن: | edsair.doi...........2c31c741188311e2dc058d631ea29bfb |
| قاعدة البيانات: | OpenAIRE |
Find this article in full text from Springer Verlag. | تدمد: | 18189962 19950802 |
|---|