DROPS

Document

Track B: Automata, Logic, Semantics, and Theory of Programming

DOI: 10.4230/LIPIcs.ICALP.2026.178

Asymptotic Hausdorff and Language Similarity

Authors: Dana Fisman and Gal Meirom

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract

We introduce the Asymptotic Hausdorff lifting, denoted AH_d, a general method for lifting an element-level metric d to a (pseudo-) metric on sets, that captures asymptotic similarity in infinite domains equipped with a notion of size. The construction is designed to be insensitive to finite deviations and to avoid the limitations of classical Hausdorff-based approaches, which are often overly sensitive to outliers and fail to reflect asymptotic behavior. Formal languages provide a central motivating instance of this framework, where elements are words and sets are languages. When applied to normalized edit distances, the Asymptotic Hausdorff lifting yields metric-valued distances between languages that reflect asymptotic edit behavior while preserving metric structure. We study the equivalence classes of regular languages induced by AH_d for normalized edit distances d, and characterize their asymptotic essence. Focusing in particular on the normalized edit distance of Marzal and Vidal, ned, we investigate the computation of AH_ned for regular languages and for bounded context-free languages.

Cite as

Dana Fisman and Gal Meirom. Asymptotic Hausdorff and Language Similarity. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 178:1-178:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{fisman_et_al:LIPIcs.ICALP.2026.178,
  author =	{Fisman, Dana and Meirom, Gal},
  title =	{{Asymptotic Hausdorff and Language Similarity}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{178:1--178:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.178},
  URN =		{urn:nbn:de:0030-drops-265660},
  doi =		{10.4230/LIPIcs.ICALP.2026.178},
  annote =	{Keywords: Automata theory, formal Languages, Metric Spaces, Language similarity, Edit Distance, asymptotic Analysis}
}

Search Results

Documents authored by Meirom, Gal

Asymptotic Hausdorff and Language Similarity

Abstract

Cite as

Thanks for your feedback!

Could not send message