2026-10-01T23:07:41Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26566 2026-09-24T00:10:56Z ddc:004 open_access

Asymptotic Hausdorff and Language Similarity Fisman, Dana Meirom, Gal Automata theory formal Languages Metric Spaces Language similarity Edit Distance asymptotic Analysis 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Dana Fisman and Gal Meirom 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.178 urn:nbn:de:0030-drops-265660 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.178 eng https://creativecommons.org/licenses/by/4.0/legalcode