Equivalence Checking Problem for Finite State Transducers over Semigroups

DOI10.1007/978-3-319-23021-4_19zbMath1465.68187OpenAlexW2261362537MaRDI QIDQ2947161

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) Semigroups in automata theory, linguistics, etc. (20M35) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)

Related Items (3)

Efficient Equivalence Checking Technique for Some Classes of Finite-State Machines ⋮ Encoding musical procedures by sequential transducers ⋮ On the Satisfiability and Model Checking for one Parameterized Extension of Linear-time Temporal Logic

Cites Work

• Unnamed Item
• Unnamed Item
• The decidability of equivalence for deterministic finite transducers
• The equivalence of finite valued transducers (on HDT0L languages) is decidable
• On the valuedness of finite transducers
• Single-valued a-transducers
• Squaring transducers: An efficient procedure for deciding functionality and sequentiality.
• Symbolic finite state transducers
• On the Decidability of the Equivalence for k-Valued Transducers
• On the Decidability of Bounded Valuedness for Transducers
• A note on finite-valued and finitely ambiguous transducers
• Decomposing Finite-Valued Transducers and Deciding Their Equivalence
• The Unsolvability of the Equivalence Problem for $\varepsilon $-Free NGSM’s with Unary Input (Output) Alphabet and Applications
• Streaming transducers for algorithmic verification of single-pass list-processing programs
• The unsolvability of the Equivalence Problem for Λ-Free nondeterministic generalized machines

This page was built for publication: Equivalence Checking Problem for Finite State Transducers over Semigroups