scientific article; zbMATH DE number 2038732

MaRDI QIDQ4449197zbMATH OpenFDO

Authors Géraud Sénizergues

Publication date 8 February 2004

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2719/27190478.htm

zbMATH Keywords

complexitydeterministic pushdown automataequivalence problemmatrix semi-groups

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Recommendations

• The equivalence problem for real-time DPDAs
• The equivalence problem for deterministic pushdown automata is decidable
• Decidability of the equivalence problem for deterministic pushdown automata
• scientific article; zbMATH DE number 2086674
• The extended equivalence problem for a class of non-real-time deterministic pushdown automata

Cited in

(5)

• On long words avoiding Zimin patterns
• Bisimulation equivalence and regularity for real-time one-counter automata
• Efficient Equivalence Checking Technique for Some Classes of Finite-State Machines
• The Hoare logic of deterministic and nondeterministic monadic recursion schemes
• A fast algorithm to decide on the equivalence of stateless DPDA

This page was built for publication:

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