Equivalence checking problem for finite state transducers over semigroups

DOI10.1007/978-3-319-23021-4_19MaRDI QIDQ2947161zbMATH OpenOpenAlexFDO

Authors Vladimir A. Zakharov

Publication date 22 September 2015

Published in Algebraic Informatics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-23021-4_19

Mathematics Subject Classification ID

Algebraic theory of languages and automata (68Q70) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Semigroups in automata theory, linguistics, etc. (20M35)

Recommendations

• Efficient Equivalence Checking Technique for Some Classes of Finite-State Machines
• On equivalence and uniformisation problems for finite transducers
• Equivalence problems for transducers with a bounded number of states
• Equivalence of finite-valued symbolic finite transducers
• On some transducer equivalence problems for families of languages

Cites work

• scientific article; zbMATH DE number 3523154 (Why is no real title available?)
• A note on finite-valued and finitely ambiguous transducers
• Decomposing Finite-Valued Transducers and Deciding Their Equivalence
• On the Decidability of Bounded Valuedness for Transducers
• On the Decidability of the Equivalence for k-Valued Transducers
• On the decomposition of \(k\)-valued rational relations
• On the valuedness of finite transducers
• Single-valued a-transducers
• Squaring transducers: An efficient procedure for deciding functionality and sequentiality.
• Streaming transducers for algorithmic verification of single-pass list-processing programs
• Symbolic finite state transducers: algorithms and applications
• The Unsolvability of the Equivalence Problem for $\varepsilon $-Free NGSM’s with Unary Input (Output) Alphabet and Applications
• The decidability of equivalence for deterministic finite transducers
• The equivalence of finite valued transducers (on HDT0L languages) is decidable
• The unsolvability of the Equivalence Problem for Λ-Free nondeterministic generalized machines

Cited in

(8)

• Ferromagnetic Wire Memory
• scientific article; zbMATH DE number 2163034 (Why is no real title available?)
• On Equivalence Checking of Nondeterministic Finite Automata
• On the Satisfiability and Model Checking for one Parameterized Extension of Linear-time Temporal Logic
• A generic framework for checking semantic equivalences between pushdown automata and finite-state automata
• Encoding musical procedures by sequential transducers
• Equivalence checking of prefix-free transducers and deterministic two-tape automata
• Efficient Equivalence Checking Technique for Some Classes of Finite-State Machines

This page was built for publication: Equivalence checking problem for finite state transducers over semigroups

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