PAIS Lab seminar: Equivalence checking problem for finite state transducers // Vladimir Zakharov

At the session of our seminar,  Vladimir Zakharov (Lead research fellow of the PAIS Lab) delivered a report "Equivalence checking problem for finite state transducers".

Abstract:
Transducers is a simple computational model which allows for describing the process of on-line transformation of finite strings (text, images, data streams, and others.) using a limited amount of memory. In case when output lines are viewed as a semigroup expression, transducers can be used as a model of successive reactive programs. To verify correctness of the behavior of such models, equivalence checking algorithms should be used.