Streaming algorithms for language recognition problems

DOI10.1016/j.tcs.2012.12.028zbMath1294.68100MaRDI QIDQ391078

Jaikumar Radhakrishnan, Girish Varma, Ajesh Babu, Nutan Limaye

Publication date: 10 January 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2012.12.028

zbMATH Keywords

context-free language; randomized algorithms; communication complexity; streaming algorithms

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q45: Formal languages and automata

68W20: Randomized algorithms

Related Items

Unnamed Item, Derandomization for sliding window algorithms with strict correctness, Extension complexity of formal languages, Dynamic data structures for timed automata acceptance, Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Some subclasses of context-free languages in \(NC^ 1\)
• Left-derivation bounded languages
• Testing and spot-checking of data streams
• Top-down syntax nalysis
• Recognizing well-parenthesized expressions in the streaming model
• The Space Complexity of Recognizing Well-Parenthesized Expressions in the Streaming Model: The Index Function Revisited
• Stable distributions, pseudorandom generators, embeddings, and data stream computation
• Streaming Algorithms for Some Problems in Log-Space
• Best-Order Streaming Model
• Turn-bounded grammars and their relation to ultralinear languages
• Finite-Turn Pushdown Automata
• Syntax-Directed Transduction
• Notes on top-down languages
• Mappings induced by PGSM-mappings and some recursively unsolvable problems of finite probabilistic automata