KFU. Card publication. Exact Affine Counter Automata

KAZAN
FEDERAL UNIVERSITY

- RUS
- 中文
- ES

EXACT AFFINE COUNTER AUTOMATA

Form of presentation

Articles in international journals and collections

Year of publication

2017

Язык

английский

Authors, employees of KFU

Khadiev Kamil Ravilevich, author

Other authors

Nakanishi Masaki , author

Prūsis Krišjānis , author

Vihrovs Jevgenijs , author

Yakaryılmaz Abuzer , author

Bibliographic description in the original language

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.

Annotation

Electronic Proceedings in Theoretical Computer Science

Keywords

quantum computing, automata, affine computing, counter automata, pushdown automata, computational complexity

The name of the journal

Electronic Proceedings in Theoretical Computer Science

On-line resource for training course

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

Please use this ID to quote from or refer to the card

https://repository.kpfu.ru/eng/?p_id=163697&p_lang=2

Resource files

File name	Size (MB)	Format
1703.04281v3.pdf	0,19	pdf	show / download

Full metadata record

Field DC	Value	Language
dc.contributor.author	Khadiev Kamil Ravilevich	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/eng/?p_id=163697&p_lang=2	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	Articles in international journals and collections	ru_RU