ISSN: 2310-757X
Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на этот ресурс:
http://elar.urfu.ru/handle/10995/89984| Название: | Reset Complexity of Ideal Languages over a Binary Alphabet |
| Авторы: | Maslennikova, M. |
| Дата публикации: | 2019 |
| Издатель: | World Scientific Publishing Co. Pte Ltd |
| Библиографическое описание: | Maslennikova, M. Reset Complexity of Ideal Languages over a Binary Alphabet / M. Maslennikova. — DOI 10.1142/S0129054119400343 // International Journal of Foundations of Computer Science. — 2019. — Vol. 6-7. — Iss. 30. — P. 1177-1196. |
| Аннотация: | We prove PSPACE-completeness of checking whether a given ideal language serves as the language of reset words for some automaton with at most four states over a binary alphabet. We compare the reset complexity and the state complexity for languages related to slowly synchronizing automata. © 2019 World Scientific Publishing Company. |
| Ключевые слова: | IDEAL LANGUAGE PSPACE-COMPLETENESS RESET COMPLEXITY RESET WORD STATE COMPLEXITY SYNCHRONIZING AUTOMATON |
| URI: | http://elar.urfu.ru/handle/10995/89984 |
| Условия доступа: | info:eu-repo/semantics/openAccess |
| Идентификатор SCOPUS: | 85072910392 |
| Идентификатор WOS: | 000486709700016 |
| Идентификатор PURE: | 10786749 |
| ISSN: | 0129-0541 |
| DOI: | 10.1142/S0129054119400343 |
| Сведения о поддержке: | Russian Foundation for Basic Research, RFBR: 16-01-00795 Ministry of Education and Science of the Russian Federation, Minobrnauka: 1.3253.2017 Ural Federal University, UrFU The author acknowledges anonymous reviewers for comments and suggestions. Also the author acknowledges support by the Russian Foundation for Basic Research, Grant No. 16-01-00795, the Ministry of Education and Science of the Russian Federation, Project No. 1.3253.2017, and the Competitiveness Enhancement Program of Ural Federal University. |
| Располагается в коллекциях: | Научные публикации, проиндексированные в SCOPUS и WoS CC |
Файлы этого ресурса:
| Файл | Описание | Размер | Формат | |
|---|---|---|---|---|
| 10.1142-S0129054119400343.pdf | 524,55 kB | Adobe PDF | Просмотреть/Открыть |
Все ресурсы в архиве электронных ресурсов защищены авторским правом, все права сохранены.