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

DOI10.4230/LIPICS.FSTTCS.2018.22MaRDI QIDQ5090958zbMATH OpenOpenAlexFDO

Authors Sougata Bose, Anca Muscholl, Vincent Penelle, Gabriele Puppis

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)

Recommendations

• On the containment and equivalence problems for two-way transducers
• On Synthesis of Resynchronizers for Transducers
• On two-way transducers
• Decision problems of tree transducers with origin
• Decision problems of tree transducers with origin

Cites work

• scientific article; zbMATH DE number 3660804 (Why is no real title available?)
• scientific article; zbMATH DE number 3497806 (Why is no real title available?)
• scientific article; zbMATH DE number 1059243 (Why is no real title available?)
• scientific article; zbMATH DE number 3254906 (Why is no real title available?)
• A general theory of translation
• A note on the reduction of two-way automata to one-way automata
• A remark on finite transducers
• Context-free graph grammars and concatenation of graphs
• Decision problems of tree transducers with origin
• Expressiveness of streaming string transducers
• Graph structure and monadic second-order logic. A language-theoretic approach
• Logics for word transductions with synthesis
• MSO definable string transductions and two-way finite-state transducers
• Nondeterministic Streaming String Transducers
• On equivalence and uniformisation problems for finite transducers
• On the degree of ambiguity of finite automata
• Regular Transformations of Data Words Through Origin Information
• The Equivalence Problem for Single-Valued Two-Way Transducers (on NPDTOL Languages) is Decidable
• The unsolvability of the Equivalence Problem for Λ-Free nondeterministic generalized machines
• Transducers with Origin Information
• Which classes of origin graphs are generated by transducers

Cited in

(5)

• One-way resynchronizability of word transducers
• A Büchi-Elgot-Trakhtenbrot theorem for automata with MSO graph storage
• Resynchronized uniformization and definability problems for rational relations
• On Synthesis of Resynchronizers for Transducers
• scientific article; zbMATH DE number 7559429 (Why is no real title available?)

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

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