Bracket-languages are recognizable in logarithmic space

DOI10.1016/0020-0190(76)90013-2MaRDI QIDQ1235984zbMATH OpenOpenAlexFDO

Authors K. Mehlhorn

Publication date 1976

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(76)90013-2

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Algorithms in computer science (68W99)

Cites work

• An observation on time-storage trade off
• scientific article; zbMATH DE number 3575000 (Why is no real title available?)
• scientific article; zbMATH DE number 3428547 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• On tape-bounded complexity classes and multihead finite automata
• Recognition and parsing of context-free languages in time n3

Cited in

(5)

• An application of Mehlhorn's algorithm for bracket languages to log(n) space recognition of input-driven languages
• Optimal parallel parsing of bracket languages
• Lower bounds on space complexity for contextfree recognition
• A combinatorial characterization of smooth LTCs and applications
• Probabilistic input-driven pushdown automata

This page was built for publication: Bracket-languages are recognizable in logarithmic space

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