|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ИНХС РАН |
||
On the Complexity of Decision Problems for Parameterized Finite State Synchronous Transducersстатья
- Авторы: Tang Tianxiang, Zakharov Vladimir A.
- Сборник: Lecture Notes in Computer Science
- Год издания: 2024
- Издательство: Springer Nature
- Местоположение издательства: Switzerland
- Первая страница: 332
- Последняя страница: 346
- DOI: 10.1007/978-3-031-71112-1_24
- Аннотация: When designing and maintaining the information systems, there is a need to use parameterized automata, in which some components of the model that determine its behavior are replaced with variables. It has previously been shown that the complexity of many analysis and synthesis problems increases significantly when machines or programs have parameters. Nevertheless, it can be expected that for some classes of automata the complexity of certain important problems will remain low and the development of efficient algorithms will be possible. We present here the results of our study of some basic decision problems for finite state transducers parameterized on output data. When choosing this class of automata, we were guided by the intention of preserving the determinism of runs with uncertain values of some elements due to the presence of parameters in the model. We managed to show that for some decision problems their complexity remains low (NL-complete) even after parameters are added to the model, whereas the complexity of other problems that have efficient solutions for ordinary transducers increases significantly (from NL or P-completeness to NP-completeness and beyond) for their parameterized modifications.
- Добавил в систему: Захаров Владимир Анатольевич