Edit Distance of Finite-Valued Transducers
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909021947035648 |
|---|---|
| author | Mathew, Prince Sunny, Saina |
| author_facet | Mathew, Prince Sunny, Saina |
| contents | Transducers generalise automata by producing output word(s) for each input word, thereby defining a relation over words. A transducer is said to be finite-valued if, for every input word, it produces at most $k$ output words, for some constant $k$. If $k = 1$, then the transducer is said to be functional. The edit distance between two transducers is the minimal number of edits required to transform every output of one transducer into some output of the other, for each input word. This notion has been studied for functional transducers, where it is shown to be computable. However, it is uncomputable for transducers in general. In this work, we show the computability of the edit distance of finite-valued transducers, a class that is strictly more expressive than functional transducers. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_06269 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Edit Distance of Finite-Valued Transducers Mathew, Prince Sunny, Saina Formal Languages and Automata Theory Logic in Computer Science F.1.1 Transducers generalise automata by producing output word(s) for each input word, thereby defining a relation over words. A transducer is said to be finite-valued if, for every input word, it produces at most $k$ output words, for some constant $k$. If $k = 1$, then the transducer is said to be functional. The edit distance between two transducers is the minimal number of edits required to transform every output of one transducer into some output of the other, for each input word. This notion has been studied for functional transducers, where it is shown to be computable. However, it is uncomputable for transducers in general. In this work, we show the computability of the edit distance of finite-valued transducers, a class that is strictly more expressive than functional transducers. |
| title | Edit Distance of Finite-Valued Transducers |
| topic | Formal Languages and Automata Theory Logic in Computer Science F.1.1 |
| url | https://arxiv.org/abs/2605.06269 |