\(L(A)=L(B)\)? A simplified decidability proof.

DOI10.1016/S0304-3975(02)00027-0zbMath1050.68096MaRDI QIDQ1603704

Géraud Sénizergues

Publication date: 15 July 2002

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

zbMATH Keywords

Rational languagesComplete formal systemsDeterministic pushdown automataFinite dimensional vector spacesMatrix semi-groups

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (9)

The Hoare Logic of Deterministic and Nondeterministic Monadic Recursion Schemes ⋮ Bisimulation equivalence and regularity for real-time one-counter automata ⋮ Selected Ideas Used for Decidability and Undecidability of Bisimilarity ⋮ On the structure of graphs in the Caucal hierarchy ⋮ Nested session types ⋮ Some properties of iterated languages ⋮ Iterated pushdown automata and sequences of rational numbers ⋮ One-Reversal Counter Machines and Multihead Automata: Revisited ⋮ Model-Checking Games for Typed λ-Calculi

Cites Work

• Unnamed Item
• On equivalence of grammars through transformation trees
• \(L(A)=L(B)\)? decidability results from complete formal systems
• An axiomatic approach to the Korenjak-Hopcroft algorithms
• The equivalence problem for real-time DPDAs
• The equivalence problem for deterministic pushdown automata is decidable
• The equivalence problem for deterministic finite-turn pushdown automata
• Decidability of DPDA equivalence

This page was built for publication: \(L(A)=L(B)\)? A simplified decidability proof.