|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ПсковГУ |
||
An Algebraic Approach to the Equivalence Checking of Deterministic Top-down Tree Transducersстатья
- Авторы: Zhibo Deng, Tianxiang Tang, Zakharov Vladimir A.
- Сборник: Lecture Notes in Computer Science
- Год издания: 2025
- Издательство: Springer Nature
- Местоположение издательства: Switzerland
- Первая страница: 86
- Последняя страница: 98
- DOI: 10.1007/978-3-032-02602-6_7
- Аннотация: For many classes of automata, denotational semantics provides suitable means for specifying functions or relations ⟦s⟧, computed in all states s of an automaton, through the system of algebraic equations. By adding to this system an equation ⟦s'⟧=⟦s''⟧ which declares that the transducer computes in some states s' and s'' the same function or relation we reduce the equivalence checking problem to that of checking the solvability of the system of equations obtained thus. In general, this problem is intractable, but when dealing only with deterministic automata the solvability checking can be performed efficiently by means of a technique very much similar to Gaussian variable elimination used in linear algebra. In this paper we show that equivalence of total deterministic tree transducers can be resolved just as efficiently using this fairly general method. Moreover, this method can be very easy adapted for computing the most general unifiers of parameterized deterministic tree transducers.
- Добавил в систему: Захаров Владимир Анатольевич