View in EDS

A weak inverse of language neighborhoods and its properties.

Saved in:
Bibliographic Details
Title: A weak inverse of language neighborhoods and its properties.
Authors: Cheon, Hyunjoon1 (AUTHOR) hyunjoon.cheon@gnu.ac.kr, Han, Yo-Sub1,2 (AUTHOR) emmous@yonsei.ac.kr
Source: Theoretical Computer Science. Feb2026, Vol. 1064, pN.PAG-N.PAG. 1p.
Subjects: Inverse functions, Formal languages
Abstract: • Introduces the edit distance interior, a new inverse-like operation to the edit distance neighborhood. • Characterizes a hierarchy of interior languages, and their closure and decision properties. • Proves regular languages are closed under the operation, but context-free languages are not. While the edit distance neighborhood is useful for approximate pattern matching, it is not suitable for the negative lookahead feature for the practical regex matching engines. This motivates us to introduce a new operation. We define the edit distance interior operation on a language L , which is to compute the largest subset I (L) of L such that the edit distance neighborhood of I (L) is in L. In other words, L includes the edit distance neighborhood of the largest edit distance interior language. Given an edit distance value r , we show that the radius- r edit distance interior operation is a weak inverse of the radius- r edit distance neighborhood operation, and vice versa. A characterization of the edit distance interior languages and their proper hierarchy with respect to the radius are presented. Closure properties up to basic Boolean operations and decision properties of such languages are also discussed. In addition, we demonstrate that the regular languages are closed under the edit distance interior operation whereas the context-free languages are not. [ABSTRACT FROM AUTHOR]
Copyright of Theoretical Computer Science is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
Description
Abstract:• Introduces the edit distance interior, a new inverse-like operation to the edit distance neighborhood. • Characterizes a hierarchy of interior languages, and their closure and decision properties. • Proves regular languages are closed under the operation, but context-free languages are not. While the edit distance neighborhood is useful for approximate pattern matching, it is not suitable for the negative lookahead feature for the practical regex matching engines. This motivates us to introduce a new operation. We define the edit distance interior operation on a language L , which is to compute the largest subset I (L) of L such that the edit distance neighborhood of I (L) is in L. In other words, L includes the edit distance neighborhood of the largest edit distance interior language. Given an edit distance value r , we show that the radius- r edit distance interior operation is a weak inverse of the radius- r edit distance neighborhood operation, and vice versa. A characterization of the edit distance interior languages and their proper hierarchy with respect to the radius are presented. Closure properties up to basic Boolean operations and decision properties of such languages are also discussed. In addition, we demonstrate that the regular languages are closed under the edit distance interior operation whereas the context-free languages are not. [ABSTRACT FROM AUTHOR]
ISSN:03043975
DOI:10.1016/j.tcs.2025.115704