2018/01/22 by Starke, Florian
#68Q45 #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL)
paper · doi:10.48550/arxiv.1801.07321
We introduce the notions of topological entropy of a formal language and of a topological automaton. We show that the entropy function is surjective and bound the entropy of languages accepted by deterministic ε-free push-down automata with an arbitrary amount of stacks.