The Online Space Complexity of Probabilistic Languages

DOI10.1007/978-3-319-27683-0_8zbMath1474.68171OpenAlexW2293632979MaRDI QIDQ5283421

Nathanaël Fijalkow

Publication date: 21 July 2017

Published in: Logical Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-27683-0_8

zbMATH Keywords

automataonline algorithmscomplexity theoryprobabilistic languagesonline complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Online algorithms; streaming algorithms (68W27)

Cites Work

• Unnamed Item
• Probabilistic counting algorithms for data base applications
• Selection and sorting with limited storage
• Irregular behaviours for probabilistic automata
• Probabilistic automata

This page was built for publication: The Online Space Complexity of Probabilistic Languages