Complete formal systems for equivalence problems

DOI10.1016/S0304-3975(99)00106-1zbMath0951.68065MaRDI QIDQ1575907

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)

Related Items

On decision problems for parameterized machines ⋮ On the universe, disjointness, and containment problems for simple machines ⋮ Frontier between decidability and undecidability: A survey ⋮ Deterministic input-driven queue automata: finite turns, decidability, and closure properties

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Pushdown machines for the macro tree transducer
• On equivalence of grammars through transformation trees
• A polynomial algorithm for deciding bisimilarity of normed context-free processes
• An axiomatic approach to the Korenjak-Hopcroft algorithms
• Iterated linear control and iterated one-turn pushdowns
• The equivalence problem for real-time strict deterministic pushdown automata
• Bisimulation equivalence is decidable for one-counter processes
• The equivalence problem for deterministic pushdown automata is decidable
• A fast algorithm to decide on the equivalence of stateless DPDA
• Decidability of bisimulation equivalence for normed pushdown processes