Unification problem for finite state parameterized transducers

Recieved: 02/21/2025

Accepted: 03/19/2025

Keywords: finite state machine, substitution, equivalence, unification problem

To cite this article

Tang T., Zakharov V. Unification problem for finite state parameterized transducers. // Moscow University Journal. Series 15. Computational Mathematics and Cybernetics. 2025. N 3, p.74-84 https://doi.org/10.55959/MSU/0137–0782–15–2025–49–3–74–84.

This work is licensed under a Сreative Commons Atribiution - NonCommercial 4.0 International (CC BY-NC 4.0)

Tang T. (Shenzhen MSU-BIT University)
Zakharov V. (Shenzhen MSU-BIT University)

Abstract

The unification problem for parameterized finite state machines consists in finding for two given automata such values of their parameters that these automata will compute the same transduction relations. This presents a quadratic time algorithm for computing the most general unifiers of parameterized deterministic finite state machines. This algorithm is based on the Martelli–Montanari unification algorithm for terms and the equivalence checking algorithm for deterministic finite state machines