Simulation of two-way pushdown automata revisited

MaRDI QIDQ4994698zbMATHFDO

Authors Robert Glück

Publication date 21 June 2021

Full work available at URL https://arxiv.org/abs/1309.5142

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• A practical simulation result for two-way pushdown automata
• Partial memoization for obtaining linear time behavior of a 2DPDA
• Simulating two pushdown stores by one tape in \(O(n^{1.5}\,\sqrt{\log \,n})\) time
• scientific article; zbMATH DE number 3926247
• scientific article; zbMATH DE number 3958761

Cited in

(10)

• scientific article; zbMATH DE number 3907803 (Why is no real title available?)
• scientific article; zbMATH DE number 4101166 (Why is no real title available?)
• scientific article; zbMATH DE number 1951589 (Why is no real title available?)
• A linear-time simulation of deterministic \(d\)-limited automata
• On space and time efficient TM simulations of some restricted classes of PDA's
• Generalizing Cook's transformation to imperative stack programs
• A practical simulation result for two-way pushdown automata
• scientific article; zbMATH DE number 3926247 (Why is no real title available?)
• scientific article; zbMATH DE number 1502111 (Why is no real title available?)
• scientific article; zbMATH DE number 1543035 (Why is no real title available?)

This page was built for publication: Simulation of two-way pushdown automata revisited

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