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

DOI10.4230/LIPICS.FSTTCS.2018.22OpenAlexW2963785939MaRDI QIDQ5090958FDOQ5090958

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

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

zbMATH Keywords

equivalencetransducersorigin semantics

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (5)

• One-way resynchronizability of word transducers
• Resynchronized uniformization and definability problems for rational relations
• A Büchi-Elgot-Trakhtenbrot theorem for automata with MSO graph storage
• On Synthesis of Resynchronizers for Transducers
• Title not available (Why is that?)

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)