An application of Mehlhorn's algorithm for bracket languages to log(n) space recognition of input-driven languages

DOI10.1016/0020-0190(86)90047-5zbMath0596.68045OpenAlexW2050655409MaRDI QIDQ1079015

Wojciech Rytter

Publication date: 1986

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

Full work available at URL: https://doi.org/10.1016/0020-0190(86)90047-5

zbMATH Keywords

space complexitylanguage recognition

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Related Items (6)

Descriptional Complexity of Input-Driven Pushdown Automata ⋮ Optimal parallel parsing of bracket languages ⋮ Input-driven languages are linear conjunctive ⋮ Descriptional complexity of unambiguous input-driven pushdown automata ⋮ Input-driven pushdown automata for edit distance neighborhood ⋮ Optimal parallel algorithms for dynamic expression evaluation and context-free recognition

Cites Work

• Bracket-languages are recognizable in logarithmic space
• Unnamed Item
• Unnamed Item

This page was built for publication: An application of Mehlhorn's algorithm for bracket languages to log(n) space recognition of input-driven languages