Context-free languages can be accepted with absolutely no space overhead

DOI10.1016/J.IC.2005.05.005MaRDI QIDQ2581536zbMATH OpenOpenAlexFDO

Authors Proshanto Mukherji, Till Tantau, Lane A. Hemaspaandra

Publication date 10 January 2006

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ic.2005.05.005

zbMATH Keywords

Context-free languagesDeterministic context-free languagesEditing Turing machinesIn-place algorithmsLinear spaceOverhead-free computationRestarting automataRRW-automataSpace overheadSpace reuseTwo-stack automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• scientific article; zbMATH DE number 2040917
• scientific article; zbMATH DE number 3978426
• The recognition of deterministic CFLs in small time and space
• Sliding windows over context-free languages
• Publication:4207603

Cites work

• A class of universal linear bounded automata
• An introduction to three algorithms for sorting in situ
• Asymptotically efficient in-place merging
• Church-Rosser Thue systems and formal languages
• DNA Computing
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 2040896 (Why is no real title available?)
• scientific article; zbMATH DE number 2040917 (Why is no real title available?)
• scientific article; zbMATH DE number 1394484 (Why is no real title available?)
• scientific article; zbMATH DE number 7627630 (Why is no real title available?)
• In-place sorting with fewer moves
• Inplace run-length 2d compressed search.
• Nondeterministic Space is Closed under Complementation
• On membrane hierarchy in P systems
• On non-determinacy in simple computing devices
• Relating refined space complexity classes
• Restarting automata
• Restarting automata, Church-Rosser languages, and representations of {r. e. \ }languages
• Smoothsort, an alternative for sorting in situ
• SOFSEM 2004: Theory and Practice of Computer Science
• The method of forced enumeration for nondeterministic automata

Cited in

(4)

• Without Remnant Movement, MGs Are Context-Free
• scientific article; zbMATH DE number 2040917 (Why is no real title available?)
• Freezing 1-Tag Systems with States
• Restarting automata with restricted utilization of auxiliary symbols

This page was built for publication: Context-free languages can be accepted with absolutely no space overhead

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