The Equivalence Problem for Deterministic Two-Way Sequential Transducers is Decidable

DOI10.1137/0211035zbMath0486.68037OpenAlexW2034701711MaRDI QIDQ3947121

Eitan M. Gurari

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

zbMATH Keywords

decidabilitydeterministic two-way sequential transducersPSPACE- completeness

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

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