|
ИСТИНА |
Войти в систему Регистрация |
ФНКЦ РР |
||
Equivalence checking of prefix-free transducers and deterministic two-tape automataстатья
Информация о цитировании статьи получена из
Scopus
Дата последнего поиска статьи во внешних источниках: 3 сентября 2019 г.
- Автор: Zakharov V.A.
- Сборник: Language and Automata Theory and Applications, 13th International Conference, LATA 2019, St. Petersburg, Russia, March 26-29, 2019, Proceedings
- Серия: Lecture Notes in Computer Science
- Том: 11417
- Год издания: 2019
- Место издания: Springer Cham, Switzelrand
- Первая страница: 146
- Последняя страница: 158
- DOI: 10.1007/978-3-030-13435-8_11
- Аннотация: Although the equivalence problem for finite transducers is undecidable in the general case, it was shown that for some classes of transducers (bounded ambiguous, bounded valued, of bounded length degree) this problem has effective solutions which, however, require significant computational costs. In this paper we distinguish a new class of transducers (we call them prefix-free since their transitions are characterized by this property of languages) such that (1) the equivalence problem for transducers in this class is decidable in quadratic time, and (2) this class does not fall into the scope of previously known decidable cases. We also show that deterministic two-tape finite state automata (2-DFSAs) are convertible into prefix-free transducers. Due to this translation we obtain a simple procedure for checking equivalence of 2-DFSAs in polynomial time. We believe that the further development of this approach could bring us to an efficient equivalence checking algorithm for deterministic multi-tape automata with an arbitrary number of tapes.
- Добавил в систему: Захаров Владимир Анатольевич