|
|||||
|
|
Topological entropy of formal languages |
|
| Authors: | Friedrich?Martin?Schneider |
| Institution: | 1.Institute of Algebra,Technische Universit?t Dresden,Dresden,Germany;2.Institute of Theoretical Computer Science,Technische Universit?t Dresden,Dresden,Germany |
| Abstract: | We introduce the notion of topological entropy of a formal language as the topological entropy of the minimal topological automaton accepting it. Using a characterization of this notion in terms of approximations of the Myhill–Nerode congruence relation, we are able to compute the topological entropies of certain example languages. Those examples suggest that the notion of a “simple” formal language coincides with the language having zero entropy. |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ | |