The Equivalence Problem for Single-Valued Two-Way Transducers (on NPDTOL Languages) is Decidable

DOI10.1137/0216018zbMath0632.68077OpenAlexW2033456284MaRDI QIDQ3769988

Juhani Karhumäki, Karel II Culik

Publication date: 1987

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0216018

zbMATH Keywords

equivalence problemEhrenfeucht conjecturetwo-way transducersunambiguous transducerDT0L languageNPDT0L languagesingle-valued transducer

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Semigroups in automata theory, linguistics, etc. (20M35)

Related Items (10)

The equivalence of finite valued transducers (on HDT0L languages) is decidable ⋮ The equivalence problem for deterministic MSO tree transducers is decidable ⋮ Equivalence of Finite-Valued Symbolic Finite Transducers ⋮ Equivalence problem of mappings relative to languages ⋮ On the decidability of the valuedness problem for two-way finite transducers ⋮ New techniques for proving the decidability of equivalence problem ⋮ Equations over finite sets of words and equivalence problems in automata theory ⋮ Unnamed Item ⋮ Origin-equivalence of two-way word transducers is in PSPACE ⋮ Normality and two-way automata

This page was built for publication: The Equivalence Problem for Single-Valued Two-Way Transducers (on NPDTOL Languages) is Decidable