Topological entropy of formal languages

DOI10.1007/S00233-016-9782-0MaRDI QIDQ2362264zbMATH OpenOpenAlexFDO

Authors Daniel Borchmann, Friedrich Martin Schneider

Publication date 7 July 2017

Published in Semigroup Forum (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1507.03393

zbMATH Keywords

automatacomplexity of formal languagestopology entropy

Mathematics Subject Classification ID

Topological entropy (37B40) Formal languages and automata (68Q45)

Abstract: We introduce the notion of topological entropy of a formal languages 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.

Recommendations

• Exploring the topological entropy of formal languages
• scientific article; zbMATH DE number 3932938
• On the computability of the topological entropy of subshifts
• Cost and dimension of words of zero topological entropy
• On the entropy of regular languages.

Cites work

• An analogue of the variational principle for group and pseudogroup actions
• Cogrowth and amenability of discrete groups
• Entropies of a semigroup of maps
• Entropy of distal groups, pseudogroups, foliations and laminations
• Expansion growth, entropy and invariant measures of distal groups and pseudogroups of homeo- and diffeomorphisms
• Geometric entropy of foliations
• scientific article; zbMATH DE number 5137519 (Why is no real title available?)
• scientific article; zbMATH DE number 3234211 (Why is no real title available?)
• Partial variational principle for finitely generated groups of polynomial growth and some foliated spaces
• Specification and thermodynamical properties of semigroup actions
• State complexity of regular languages
• Syntactic complexity of ideal and closed languages
• Topological complexity
• TOPOLOGICAL COMPLEXITY OF SEMIGROUP ACTIONS
• Topological Entropy

Cited in

(10)

• On the entropy of regular languages.
• Entropy of generating series for nonlinear input-output systems and their interconnections
• Exploring the topological entropy of formal languages
• Generalised entropies and asymptotic complexities of languages
• Cost and dimension of words of zero topological entropy
• scientific article; zbMATH DE number 3932938 (Why is no real title available?)
• scientific article; zbMATH DE number 4051587 (Why is no real title available?)
• scientific article; zbMATH DE number 2087219 (Why is no real title available?)
• Regular language distance and entropy
• Definitions and properties of entropy and distance for regular languages

This page was built for publication: Topological entropy of formal languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2362264)