Efficient Equivalence Checking Technique for Some Classes of Finite-State Machines

DOI10.18255/1818-1015-2020-3-260-303MaRDI QIDQ5060068zbMATH OpenOpenAlexFDO

Authors Vladimir A. Zakharov

Publication date 17 January 2023

Published in Modeling and Analysis of Information Systems (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL http://mathnet.ru/eng/mais716

zbMATH Keywords

biautomatondecision procedureequivalence checkinglanguage equationprefix-free languagesimple grammartransducertwo-tape automaton

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70)

Recommendations

• Equivalence checking of prefix-free transducers and deterministic two-tape automata
• Equivalence of infinite behavior of finite automata
• Equivalence checking problem for finite state transducers over semigroups
• Equivalence problems for transducers with a bounded number of states
• On the equivalence problem for deterministic multitape automata and transducers

Cites work

• A direct algorithm for checking equivalence of LL(k) grammars
• A machine realization of the linear context-free languages
• A note on finite-valued and finitely ambiguous transducers
• A polynomial algorithm for deciding bisimilarity of normed context-free processes
• A Polynomial Time Algorithm for Deciding the Equivalence Problem for 2-Tape Deterministic Finite State Acceptors
• An Efficient Unification Algorithm
• An extended direct branching algorithm for checking equivalence of deterministic pushdown automata
• An improvement on Valiant's decision procedure for equivalence of deterministic finite turn pushdown machines
• Decision problems for language equations
• Decomposing Finite-Valued Transducers and Deciding Their Equivalence
• Deterministic biautomata and subclasses of deterministic linear languages
• Deterministic one-counter automata
• Equations over finite sets of words and equivalence problems in automata theory
• Equivalence checking problem for finite state transducers over semigroups
• scientific article; zbMATH DE number 3174044 (Why is no real title available?)
• scientific article; zbMATH DE number 4155910 (Why is no real title available?)
• scientific article; zbMATH DE number 4060732 (Why is no real title available?)
• scientific article; zbMATH DE number 3497806 (Why is no real title available?)
• scientific article; zbMATH DE number 3523154 (Why is no real title available?)
• scientific article; zbMATH DE number 2038732 (Why is no real title available?)
• scientific article; zbMATH DE number 1517989 (Why is no real title available?)
• scientific article; zbMATH DE number 2086674 (Why is no real title available?)
• scientific article; zbMATH DE number 6164504 (Why is no real title available?)
• scientific article; zbMATH DE number 3382323 (Why is no real title available?)
• Implementation and Application of Automata
• Language equivalence of deterministic real-time one-counter automata is NL-complete
• Lexicographic decomposition of \(k\)-valued transducers
• Linear Context Free Languages
• Minimization algorithms for sequential transducers
• Minimization and characterizations for biautomata
• Multitape one-way nonwriting automata
• Nondeterministic biautomata and their descriptional complexity
• On biautomata
• On formalised computer programs
• On size reduction techniques for multitape automata
• On the Decidability of Bounded Valuedness for Transducers
• On the Decidability of the Equivalence for a Certain Class of Transducers
• On the Decidability of the Equivalence for k-Valued Transducers
• On the lengths of values in a finite transducer
• On the valuedness of finite transducers
• Program equivalence checking by two-tape automata
• Properties of deterministic top-down grammars
• Revisiting the equivalence problem for finite multitape automata
• 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 decidability of equivalence for deterministic finite transducers
• The equivalence of finite valued transducers (on HDT0L languages) is decidable
• The equivalence problem for deterministic finite-turn pushdown automata
• The equivalence problem for deterministic pushdown automata is decidable
• The equivalence problem for deterministic two-tape automata
• The equivalence problem for real-time deterministic pushdown automata
• The equivalence problem for real-time DPDAs
• The equivalence problem for real-time strict deterministic pushdown automata
• The equivalence problem for some non-real-time deterministic pushdown automata
• The equivalence problem of multitape finite automata
• The inclusion problem for simple languages
• The Unsolvability of the Equivalence Problem for \varepsilon -Free NGSM’s with Unary Input (Output) Alphabet and Applications
• The unsolvability of the Equivalence Problem for Λ-Free nondeterministic generalized machines
• Two decidability results for deterministic pushdown automata

Cited in

(5)

• Equivalence of infinite behavior of finite automata
• Equivalence and preorder checking for finite-state systems
• Equivalence checking problem for finite state transducers over semigroups
• On Equivalence Checking of Nondeterministic Finite Automata
• Ferromagnetic Wire Memory

This page was built for publication: Efficient Equivalence Checking Technique for Some Classes of Finite-State Machines

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