Decomposing Finite-Valued Transducers and Deciding Their Equivalence

DOI10.1137/0222014zbMATH Open0767.68079OpenAlexW2100590693MaRDI QIDQ4037692FDOQ4037692

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

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

zbMATH Keywords

equivalence problemfinite transducersvaluednessfinite valued

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cited In (32)

• On the Decidability of the Equivalence for a Certain Class of Transducers
• Title not available (Why is that?)
• Algorithmic aspects of decomposition and equivalence of finite-valued transducers
• FINITELY SUBSEQUENTIAL TRANSDUCERS
• Title not available (Why is that?)
• On the containment and equivalence problems for GSMs, transducers, and linear CFGs
• On the containment and equivalence problems for two-way transducers
• A unified framework for disambiguating finite transductions
• Single-valuedness of tree transducers is decidable in polynomial time
• Equivalence of finite-valued symbolic finite transducers
• On the valuedness of 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
• Efficient Equivalence Checking Technique for Some Classes of Finite-State Machines
• The Equivalence Problem of Finite Substitutions on ab*c, with Applications
• On the decidability of the valuedness problem for two-way finite transducers
• Decomposing a $k$-valued transducer into $k$ unambiguous ones
• Multi-sequential word relations
• On the Decidability of the Equivalence for k-Valued Transducers
• On equivalence and uniformisation problems for finite transducers
• On the Decidability of Bounded Valuedness for Transducers
• Balance of many-valued transductions and equivalence problems
• Visibly pushdown transducers with look-ahead
• On the decomposition of finite-valued streaming string transducers
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Visibly pushdown transducers
• 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)