License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2017.3
URN: urn:nbn:de:0030-drops-80945
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/8094/
Go to the corresponding LIPIcs Volume Portal

Parker, Austin J. ; Yancey, Kelly B. ; Yancey, Matthew P.

Regular Language Distance and Entropy

pdf-format:
LIPIcs-MFCS-2017-3.pdf (0.6 MB)

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 channel capacity, 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 entropy sum distance metric is suggested, and shown to be granular in certain situations.

BibTeX - Entry

@InProceedings{parker_et_al:LIPIcs:2017:8094,
  author =	{Austin J. Parker and Kelly B. Yancey and Matthew P. Yancey},
  title =	{{Regular Language Distance and Entropy}},
  booktitle =	{42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
  pages =	{3:1--3:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-046-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{83},
  editor =	{Kim G. Larsen and Hans L. Bodlaender and Jean-Francois Raskin},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/8094},
  URN =		{urn:nbn:de:0030-drops-80945},
  doi =		{10.4230/LIPIcs.MFCS.2017.3},
  annote =	{Keywords: regular languages, channel capacity, entropy, Jaccard, symbolic dynamics}
}

Keywords: regular languages, channel capacity, entropy, Jaccard, symbolic dynamics
Collection: 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)
Issue Date: 2017
Date of publication: 01.12.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI