Decomposing Finite-Valued Transducers and Deciding Their Equivalence

DOI10.1137/0222014MaRDI QIDQ4037692zbMATH OpenOpenAlexFDO

Authors

Publication date 16 May 1993

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0222014

zbMATH Keywords

equivalence problemfinite transducersvaluednessfinite valued

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• scientific article; zbMATH DE number 4060732
• On the valuedness of finite transducers
• Decomposing a $k$-valued transducer into $k$ unambiguous ones
• Algorithmic aspects of decomposition and equivalence of finite-valued transducers
• On the lengths of values in a finite transducer

Cited in

(32)

• On the Decidability of the Equivalence for a Certain Class of Transducers
• Algorithmic aspects of decomposition and equivalence of finite-valued transducers
• scientific article; zbMATH DE number 4060732 (Why is no real title available?)
• scientific article; zbMATH DE number 4003554 (Why is no real title available?)
• FINITELY SUBSEQUENTIAL TRANSDUCERS
• On the containment and equivalence problems for two-way transducers
• On the containment and equivalence problems for GSMs, transducers, and linear CFGs
• A unified framework for disambiguating finite transductions
• Single-valuedness of tree transducers is decidable in polynomial time
• On the valuedness of finite transducers
• Equivalence of finite-valued symbolic finite transducers
• Extended symbolic finite automata and transducers
• A pattern logic for automata with outputs
• Lexicographic decomposition of \(k\)-valued transducers
• On the difference set of two transductions
• Equivalence checking problem for finite state transducers over semigroups
• On the decidability of the valuedness problem for two-way finite transducers
• Efficient Equivalence Checking Technique for Some Classes of Finite-State Machines
• The Equivalence Problem of Finite Substitutions on ab*c, with Applications
• Decomposing a $k$-valued transducer into $k$ unambiguous ones
• Multi-sequential word relations
• On the Decidability of the Equivalence for k-Valued Transducers
• Balance of many-valued transductions and equivalence problems
• On the Decidability of Bounded Valuedness for Transducers
• On equivalence and uniformisation problems for finite transducers
• Visibly pushdown transducers with look-ahead
• On the decomposition of finite-valued streaming string transducers
• scientific article; zbMATH DE number 17828 (Why is no real title available?)
• scientific article; zbMATH DE number 7561615 (Why is no real title available?)
• Visibly pushdown transducers
• scientific article; zbMATH DE number 125895 (Why is no real title available?)
• Equivalence of finite-valued tree transducers is decidable

This page was built for publication: Decomposing Finite-Valued Transducers and Deciding Their Equivalence

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