Equivalence of finite-valued streaming string transducers is decidable

2019/02/19 by Anca Muscholl, Muscholl, Anca, Gabriele Puppis +1 · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · #Computability, Logic, AI Algorithms #DNA and Biological Computing #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #cs.FL #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1902.06973

openalex publication_date 2019/02/19 · openalex created_date 2019/03/02 · arxiv created 2019/04/30 · arxiv updated 2019/05/01 · openalex updated_date 2026/07/28

Abstract

In this paper we provide a positive answer to a question left open by Alur and and Deshmukh in 2011 by showing that equivalence of finite-valued copyless streaming string transducers is decidable.

Cited by

• Minimization of Streaming Transducers

Related

• On Streaming String Transducers and HDT0L Systems
• Composing Copyless Streaming String Transducers
• The Equivalence Problem for Deterministic MSO Tree Transducers is Decidable
• Register transducers are marble transducers
• A Regular and Complete Notion of Delay for Streaming String Transducers