Day_LIPIcs-STACS-2021-25.pdf (783.69 kB)

The edit distance to k-subsequence universality

Download (783.69 kB)
conference contribution
posted on 21.05.2021, 10:25 by Joel DayJoel Day, Pamela Fleischmann, Maria Kosche, Tore Koss, Florin Manea, Stefan Siemer
A word u is a subsequence of another word w if u can be obtained from w by deleting some of its letters. In the early 1970s, Imre Simon defined the relation ∼k (called now Simon-Congruence) as follows: two words having exactly the same set of subsequences of length at most k are ∼k-congruent. This relation was central in defining and analysing piecewise testable languages, but has found many applications in areas such as algorithmic learning theory, databases theory, or computational linguistics. Recently, it was shown that testing whether two words are ∼k-congruent can be done in optimal linear time. Thus, it is a natural next step to ask, for two words w and u which are not ∼k-equivalent, what is the minimal number of edit operations that we need to perform on w in order to obtain a word which is ∼k-equivalent to u. In this paper, we consider this problem in a setting which seems interesting: when u is a k-subsequence universal word. A word u with alph(u) = Σ is called k-subsequence universal if the set of subsequences of length k of u contains all possible words of length k over Σ. As such, our results are a series of efficient algorithms computing the edit distance from w to the language of k-subsequence universal words.

Funding

DFG-grant 389613931

History

School

  • Science

Department

  • Mathematical Sciences

Published in

38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)

Pages

25:1-25:19

Source

38th International Symposium on Theoretical Aspects of Computer Science (STACS)

Publisher

Schloss Dagstuhl -- Leibniz-Zentrum Informatik

Version

VoR (Version of Record)

Rights holder

© The authors

Publisher statement

This is an Open Access Article. It is published by Schloss Dagstuhl under the Creative Commons Attribution 4.0 Unported Licence (CC BY). Full details of this licence are available at: http://creativecommons.org/licenses/by/4.0/

Publication date

2021-03-10

Copyright date

2021

ISBN

9783959771801

ISSN

1868-8969

Book series

Leibniz International Proceedings in Informatics (LIPIcs); 187

Language

en

Editor(s)

Markus Bläser; Benjamin Monmege

Location

ELECTR NETWORK

Event dates

16th March 2021 - 19th March 2021

Depositor

Dr Joel Day. Deposit date: 20 May 2021

Article number

25