Regular language distance and entropy

DOI10.4230/LIPICS.MFCS.2017.3zbMATH Open1440.68161arXiv1602.07715OpenAlexW2963255148MaRDI 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

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

Cited In (4)

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

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)