2018/01/22 by Florian Starke, Starke, Florian
Computer Science · #68Q45 #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #cs.CC #cs.FL #msc:68Q45
paper · pdf · doi:10.48550/arxiv.1801.07321
22 pages
arxiv created 2019/04/24 · arxiv updated 2019/04/25
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.