Origin-equivalence of two-way word transducers is in PSPACE

DOI10.4230/LIPIcs.FSTTCS.2018.22OpenAlexW2963785939MaRDI QIDQ5090958

Vincent Penelle, Gabriele Puppis, Sougata Bose, Anca Muscholl

Publication date: 21 July 2022

Full work available at URL: https://arxiv.org/abs/1807.08053

zbMATH Keywords

equivalencetransducersorigin semantics

Mathematics Subject Classification ID

Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Theory of computing (68Qxx)

Related Items (4)

Unnamed Item ⋮ One-way resynchronizability of word transducers ⋮ Unnamed Item ⋮ On Synthesis of Resynchronizers for Transducers

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on the reduction of two-way automata to one-way automata
• On the degree of ambiguity of finite automata
• Context-free graph grammars and concatenation of graphs
• Decision problems of tree transducers with origin
• Regular Transformations of Data Words Through Origin Information
• Expressiveness of Streaming String Transducers
• Nondeterministic Streaming String Transducers
• The Equivalence Problem for Single-Valued Two-Way Transducers (on NPDTOL Languages) is Decidable
• MSO definable string transductions and two-way finite-state transducers
• On equivalence and uniformisation problems for finite transducers
• Logics for Word Transductions with Synthesis
• Transducers with Origin Information
• The unsolvability of the Equivalence Problem for Λ-Free nondeterministic generalized machines
• A general theory of translation
• A remark on finite transducers

This page was built for publication: Origin-equivalence of two-way word transducers is in PSPACE