|
ИСТИНА |
Войти в систему Регистрация |
Интеллектуальная Система Тематического Исследования НАукометрических данных |
||
On the membership problem for finite automata over symmetric groupsстатья
- Автор: Khashaev Arthur
- Журнал: Discrete Mathematics and Applications
- Том: 32
- Номер: 6
- Год издания: 2022
- Издательство: de Gruyter
- Местоположение издательства: Germany
- Первая страница: 389
- Последняя страница: 395
- DOI: 10.1515/dma-2022-0033
- Аннотация: We consider automata in which transitions are labelled with arbitrary permutations. The language of such an automaton consists of compositions of permutations for all possible admissible computation paths. The membership problem for finite automata over symmetric groups is the following decision problem: does a given permutation belong to the language of a given automaton? We show that this problem is NP-complete. We also propose an efficient algorithm for the case of strongly connected automata.
- Добавил в систему: Хашаев Артур Акрамович