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

DOI10.1137/0211035MaRDI QIDQ3947121zbMATH OpenOpenAlexFDO

Authors 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)

Cited in

(18)

• Hierarchies of primitive recursive wordsequence functions: Comparisons and decision problems
• The equivalence of finite valued transducers (on HDT0L languages) is decidable
• The Dyck language \(D_ 1^{'*}\) is not generated by any matrix grammar of finite index
• Normality and two-way automata
• On the decidability of the valuedness problem for two-way finite transducers
• A survey on decidable equivalence problems for tree transducers
• Two-way counter machines and finite-state transducers†
• On some transducer equivalence problems for families of languages
• On the containment and equivalence problems for two-way transducers
• scientific article; zbMATH DE number 7559390 (Why is no real title available?)
• Register Transducers Are Marble Transducers
• The many facets of string transducers (invited talk)
• scientific article; zbMATH DE number 7561615 (Why is no real title available?)
• Sequentiality of string-to-context transducers
• Pebble minimization: the last theorems
• Sequences of words defined by two-way transducers
• The equivalence problem for deterministic MSO tree transducers is decidable
• New techniques for proving the decidability of equivalence problem

This page was built for publication: The Equivalence Problem for Deterministic Two-Way Sequential Transducers is Decidable

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3947121)