| Форма представления | Статьи в зарубежных журналах и сборниках |
| Год публикации | 2017 |
| Язык | английский |
|
Хадиев Камиль Равилевич, автор
|
|
Nakanishi Masaki , автор
Prūsis Krišjānis , автор
Vihrovs Jevgenijs , автор
Yakaryılmaz Abuzer , автор
|
| Библиографическое описание на языке оригинала |
Exact Affine Counter Automata / Masaki Nakanishi, Kamil Khadiev, Krišjānis Prūsis, Jevgēnijs Vihrovs, Abuzer Yakaryılmaz // Proceedings 15th International Conference on Automata and Formal Languages (AFL 2017), Debrecen, Hungary, September 4-6, 2017, Electronic Proceedings in Theoretical Computer Science. - 2017. - Vol. 252. - p. 205–218. |
| Аннотация |
Electronic Proceedings in Theoretical Computer Science |
| Ключевые слова |
quantum computing, automata, affine computing, counter automata, pushdown automata, computational complexity |
| Название журнала |
Electronic Proceedings in Theoretical Computer Science
|
| Ссылка для РПД |
http://dspace.kpfu.ru/xmlui/bitstream/handle/net/116440/1703.04281v3.pdf?sequence=1&isAllowed=y
|
| URL |
http://eptcs.web.cse.unsw.edu.au/paper.cgi?AFL2017.20 |
| Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на эту карточку |
https://repository.kpfu.ru/?p_id=163697 |
| Файлы ресурса | |
|
|
Полная запись метаданных  |
| Поле DC |
Значение |
Язык |
| dc.contributor.author |
Хадиев Камиль Равилевич |
ru_RU |
| dc.contributor.author |
Nakanishi Masaki |
ru_RU |
| dc.contributor.author |
Prūsis Krišjānis |
ru_RU |
| dc.contributor.author |
Vihrovs Jevgenijs |
ru_RU |
| dc.contributor.author |
Yakaryılmaz Abuzer |
ru_RU |
| dc.date.accessioned |
2017-01-01T00:00:00Z |
ru_RU |
| dc.date.available |
2017-01-01T00:00:00Z |
ru_RU |
| dc.date.issued |
2017 |
ru_RU |
| dc.identifier.citation |
Exact Affine Counter Automata / Masaki Nakanishi, Kamil Khadiev, Krišjānis Prūsis, Jevgēnijs Vihrovs, Abuzer Yakaryılmaz // Proceedings 15th International Conference on Automata and Formal Languages (AFL 2017), Debrecen, Hungary, September 4-6, 2017, Electronic Proceedings in Theoretical Computer Science. - 2017. - Vol. 252. - p. 205–218. |
ru_RU |
| dc.identifier.uri |
https://repository.kpfu.ru/?p_id=163697 |
ru_RU |
| dc.description.abstract |
Electronic Proceedings in Theoretical Computer Science |
ru_RU |
| dc.description.abstract |
Electronic Proceedings in Theoretical Computer Science |
ru_RU |
| dc.description.abstract |
We introduce an affine generalization of counter automata, and analyze their ability as well as affine finite automata. Our contributions are as follows. We show that there is a language that can be recognized by exact realtime affine counter automata but by neither 1-way deterministic pushdown automata nor realtime deterministic k-counter automata. We also show that a certain promise problem, which is conjectured not to be solved by two-way quantum finite automata in polynomial time, can be solved by Las Vegas affine finite automata. Lastly, we show that how a counter helps for affine finite automata by showing that the language MANYTWINS, which is conjectured not to be recognized by affine, quantum or classical finite state models in polynomial time, can be recognized by affine counter automata with one-sided bounded-error in realtime. |
ru_RU |
| dc.language.iso |
ru |
ru_RU |
| dc.subject |
quantum computing |
ru_RU |
| dc.subject |
automata |
ru_RU |
| dc.subject |
affine computing |
ru_RU |
| dc.subject |
counter automata |
ru_RU |
| dc.subject |
pushdown automata |
ru_RU |
| dc.subject |
computational complexity |
ru_RU |
| dc.title |
Exact Affine Counter Automata |
ru_RU |
| dc.type |
Статьи в зарубежных журналах и сборниках |
ru_RU |
|
EN 
中文 
ES 
Карта сайта
