Entropy of pebble automata and space complexity

2026/05/08 by J. Andres Montoya · 1 voice
Computer Science · #cs.CC #cs.FL

paper · pdf · doi:10.48550/arxiv.2605.08555

Abstract

Let L denote the class Logpsace and NL the class NLogspace. We use logCFL to denote the closure under logspace reductions of the set of context-free languages. We prove that NL is different from logCFL. This result implies L different from Ptime and the stronger separation NL different from Ptime.

Discussions

• J. Andres Montoya: Entropy of pebble automata and space complexity https://arxiv.org/abs/2605.08555 https://arxiv.org/pdf/2605.08555 https://arxiv.org/html/2605.08555 [bsky, 1 points, 0 comments]

Related

• L is different from NP
• Exploring the Topological Entropy of Formal Languages
• Automata theory on sliding windows
• Maximizing entropy for power-free languages
• New Results on the Minimum Amount of Useful Space