KFU. Card publication. Вычислительная мощь конечных автоматов, решающих унарные задачи отделимости

KAZAN
FEDERAL UNIVERSITY

- RUS
- 中文
- ES

ВЫЧИСЛИТЕЛЬНАЯ МОЩЬ КОНЕЧНЫХ АВТОМАТОВ, РЕШАЮЩИХ УНАРНЫЕ ЗАДАЧИ ОТДЕЛИМОСТИ

Form of presentation

Conference proceedings in Russian journals and collections

Year of publication

2016

Язык

русский

Authors, employees of KFU

Gaynutdinova Aida Faritovna, author

Bibliographic description in the original language

Gaynutdinova A.F. Vychislitelnaya moshh konechnykh avtomatov, reshayushhikh unarnye zadachi otdelimosti / A.F.Gaynutdinova // Materialy XII Mezhdu-narodnogo seminara «Diskretnaya matematika i ee prilozheniya», imeni akademika O.B. Lupanova (Moskva, MGU, 20–25 iyunya 2016 g.) Pod red. O.M. Kasim-Zade. - M.: Izd-vo mekhaniko-matematicheskogo fakulteta MGU, 2016. - C.123-126

Annotation

Материалы XII Между-народного семинара ?Дискретная математика и ее приложения?, имени академика О.Б. Лупанова (Москва, МГУ, 20?25 июня 2016 г.)

Keywords

квантовый автомат, сложность вычисления, задача отделимости, унарный язык, регулярный язык, вероятностный автомат, детерминированный автомат

The name of the journal

URL

http://new.math.msu.su/department/dm/data/uploads/seminar12_prog/selection1.pdf

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

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

Full metadata record

Field DC	Value	Language
dc.contributor.author	Gaynutdinova Aida Faritovna	ru_RU
dc.date.accessioned	2016-01-01T00:00:00Z	ru_RU
dc.date.available	2016-01-01T00:00:00Z	ru_RU
dc.date.issued	2016	ru_RU
dc.identifier.citation	Гайнутдинова А.Ф. Вычислительная мощь конечных автоматов, решающих унарные задачи отделимости / А.Ф.Гайнутдинова // Материалы XII Между-народного семинара «Дискретная математика и ее приложения», имени академика О.Б. Лупанова (Москва, МГУ, 20–25 июня 2016 г.) Под ред. О.М. Касим-Заде. - М.: Изд-во механико-математического факультета МГУ, 2016. - C.123-126	ru_RU
dc.identifier.uri	https://repository.kpfu.ru/eng/?p_id=148836&p_lang=2	ru_RU
dc.description.abstract	Материалы XII Между-народного семинара ?Дискретная математика и ее приложения?, имени академика О.Б. Лупанова (Москва, МГУ, 20?25 июня 2016 г.)	ru_RU
dc.description.abstract	Исследована вычислительная мощь квантовых конечных автоматов, решающих унарные задачи отделимости. Показано, что квантовые унарные конечные автоматы могут отделять друг от друга языки, не являющиеся регулярными. Проведен сравнительный анализ сложности квантовых и классических унарных автоматов, решающих задачи отделимости. Показано, что такие квантовые автоматы могут быть эффективнее классических, и преимущество в сложности может превосходить максимальный предел, возможный при распознавании языков.	ru_RU
dc.language.iso	ru	ru_RU
dc.subject	квантовый автомат	ru_RU
dc.subject	сложность вычисления	ru_RU
dc.subject	задача отделимости	ru_RU
dc.subject	унарный язык	ru_RU
dc.subject	регулярный язык	ru_RU
dc.subject	вероятностный автомат	ru_RU
dc.subject	детерминированный автомат	ru_RU
dc.title	Вычислительная мощь конечных автоматов, решающих унарные задачи отделимости	ru_RU
dc.type	Conference proceedings in Russian journals and collections	ru_RU