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
FullText Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 190795666
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: A weak inverse of language neighborhoods and its properties.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Cheon%2C+Hyunjoon%22">Cheon, Hyunjoon</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> hyunjoon.cheon@gnu.ac.kr</i><br /><searchLink fieldCode="AR" term="%22Han%2C+Yo-Sub%22">Han, Yo-Sub</searchLink><relatesTo>1,2</relatesTo> (AUTHOR)<i> emmous@yonsei.ac.kr</i>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Theoretical+Computer+Science%22">Theoretical Computer Science</searchLink>. Feb2026, Vol. 1064, pN.PAG-N.PAG. 1p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Inverse+functions%22">Inverse functions</searchLink><br /><searchLink fieldCode="DE" term="%22Formal+languages%22">Formal languages</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: • 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]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>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.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=190795666
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1016/j.tcs.2025.115704
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 1
        StartPage: N.PAG
    Subjects:
      – SubjectFull: Inverse functions
        Type: general
      – SubjectFull: Formal languages
        Type: general
    Titles:
      – TitleFull: A weak inverse of language neighborhoods and its properties.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Cheon, Hyunjoon
      – PersonEntity:
          Name:
            NameFull: Han, Yo-Sub
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 26
              M: 02
              Text: Feb2026
              Type: published
              Y: 2026
          Identifiers:
            – Type: issn-print
              Value: 03043975
          Numbering:
            – Type: volume
              Value: 1064
          Titles:
            – TitleFull: Theoretical Computer Science
              Type: main
ResultId 1