Simulation of two-way pushdown automata revisited

zbMATH Open1464.68167arXiv1309.5142MaRDI QIDQ4994698FDOQ4994698

Robert Glück

Publication date: 21 June 2021

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

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

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cited In (8)

• A linear-time simulation of deterministic \(d\)-limited automata
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On space and time efficient TM simulations of some restricted classes of PDA's

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)