Regular language distance and entropy

DOI10.4230/LIPICS.MFCS.2017.3zbMATH Open1440.68161OpenAlexW2963255148MaRDI QIDQ5111217FDOQ5111217

Authors: Austin Parker, Kelly Yancey, Matthew Yancey 

Publication date: 26 May 2020

Abstract: This paper addresses the problem of determining the distance between two regular languages. It will show how to expand Jaccard distance, which works on finite sets, to potentially-infinite regular languages. The entropy of a regular language plays a large role in the extension. Much of the paper is spent investigating the entropy of a regular language. This includes addressing issues that have required previous authors to rely on the upper limit of Shannon's traditional formulation of entropy, because its limit does not always exist. The paper also includes proposing a new limit based formulation for the entropy of a regular language and proves that formulation to both exist and be equivalent to Shannon's original formulation (when it exists). Additionally, the proposed formulation is shown to equal an analogous but formally quite different notion of topological entropy from Symbolic Dynamics -- consequently also showing Shannon's original formulation to be equivalent to topological entropy. Surprisingly, the natural Jaccard-like entropy distance is trivial in most cases. Instead, the {it entropy sum} distance metric is suggested, and shown to be granular in certain situations.

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

Recommendations

• Definitions and properties of entropy and distance for regular languages
• Distances of formal languages
• Parameterized Prefix Distance between Regular Languages
• Finite Approximations and Similarity of Languages
• Topological entropy of formal languages

zbMATH Keywords

entropysymbolic dynamicsregular languageschannel capacityJaccard distance

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Measures of information, entropy (94A17) Symbolic dynamics (37B10) Topological entropy (37B40)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A Mathematical Theory of Communication
• A Similarity Measure for Cyclic Unary Regular Languages
• An Introduction to Symbolic Dynamics and Coding
• Computation of distances for regular and context-free probabilistic languages
• Conditional densities of regular languages
• Efficient Computation of the Relative Entropy of Probabilistic Automata
• Expansions of Sums of Matrix Powers
• Information rate of some classes of non-regular languages: an automata-theoretic approach (extended abstract)
• LATIN 2004: Theoretical Informatics
• On Li-Yorke pairs
• On the Computation of Some Standard Distances Between Probabilistic Automata
• On the computability of the topological entropy of subshifts
• On the entropy of context-free languages
• Regular language distance and entropy
• Similarity in languages and programs
• The QR Transformation A Unitary Analogue to the LR Transformation--Part 1
• Topological entropy of formal languages

Cited In (4)

• Regular language distance and entropy
• Definitions and properties of entropy and distance for regular languages
• Parameterized Prefix Distance between Regular Languages
• Fractal dimensions of \(k\)-automatic sets

This page was built for publication: Regular language distance and entropy

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