Complete formal systems for equivalence problems

DOI10.1016/S0304-3975(99)00106-1MaRDI QIDQ1575907zbMATH OpenFDO

Authors Géraud Sénizergues

Publication date 23 August 2000

Published in Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

language equivalenceformal systemsbisimulation equivalence

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Decidability of theories and sets of sentences (03B25)

Recommendations

• \(L(A)=L(B)\)? decidability results from complete formal systems
• The equivalence problem for deterministic pushdown automata is decidable
• scientific article; zbMATH DE number 1232245
• Decidability of the equivalence problem for deterministic pushdown automata

Cites work

• scientific article; zbMATH DE number 4035115 (Why is no real title available?)
• scientific article; zbMATH DE number 3716792 (Why is no real title available?)
• scientific article; zbMATH DE number 42752 (Why is no real title available?)
• scientific article; zbMATH DE number 41838 (Why is no real title available?)
• scientific article; zbMATH DE number 3562528 (Why is no real title available?)
• scientific article; zbMATH DE number 3639163 (Why is no real title available?)
• scientific article; zbMATH DE number 1222568 (Why is no real title available?)
• scientific article; zbMATH DE number 1142312 (Why is no real title available?)
• scientific article; zbMATH DE number 3448092 (Why is no real title available?)
• A fast algorithm to decide on the equivalence of stateless DPDA
• A polynomial algorithm for deciding bisimilarity of normed context-free processes
• An axiomatic approach to the Korenjak-Hopcroft algorithms
• Bisimulation equivalence is decidable for one-counter processes
• Decidability of bisimulation equivalence for normed pushdown processes
• Iterated linear control and iterated one-turn pushdowns
• On equivalence of grammars through transformation trees
• Pushdown machines for the macro tree transducer
• The equivalence problem for deterministic pushdown automata is decidable
• The equivalence problem for real-time strict deterministic pushdown automata

Cited in

(8)

• A complete and consistent formal system for sortals
• On the universe, disjointness, and containment problems for simple machines
• Frontier between decidability and undecidability: A survey
• On decision problems for parameterized machines
• Deterministic input-driven queue automata: finite turns, decidability, and closure properties
• Formal Systems for Tuple and Equality Generating Dependencies
• scientific article; zbMATH DE number 3887686 (Why is no real title available?)
• scientific article; zbMATH DE number 6287618 (Why is no real title available?)

This page was built for publication: Complete formal systems for equivalence problems

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