Entropy of pebble automata and space complexity

J. Andres Montoya

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…