The Equivalence Problem for Deterministic Two-Way Sequential Transducers is Decidable
From MaRDI portal
Publication:3947121
DOI10.1137/0211035zbMath0486.68037OpenAlexW2034701711MaRDI QIDQ3947121
Publication date: 1982
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0211035
Related Items
The equivalence of finite valued transducers (on HDT0L languages) is decidable, The equivalence problem for deterministic MSO tree transducers is decidable, The Dyck language \(D_ 1^{'*}\) is not generated by any matrix grammar of finite index, On the decidability of the valuedness problem for two-way finite transducers, Pebble minimization: the last theorems, On the containment and equivalence problems for two-way transducers, New techniques for proving the decidability of equivalence problem, On some transducer equivalence problems for families of languages, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Sequences of words defined by two-way transducers, A Survey on Decidable Equivalence Problems for Tree Transducers, Register Transducers Are Marble Transducers, Normality and two-way automata, Two-way counter machines and finite-state transducers†, Hierarchies of primitive recursive wordsequence functions: Comparisons and decision problems