Bracket-languages are recognizable in logarithmic space

DOI10.1016/0020-0190(76)90013-2zbMath0352.68089OpenAlexW1987971864MaRDI QIDQ1235984

Kurt 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)

Related Items

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On tape-bounded complexity classes and multihead finite automata
• An observation on time-storage trade off
• Recognition and parsing of context-free languages in time n3