6 citations · 6 across the 2 of their papers we have counts for
2 papers
cs.DS2024
Improved Randomized Approximation of Hard Universality and Emptiness Problems
Pantelis Andreou, Stavros Konstantinidis, Taylor J. Smith
We build on recent research on polynomial randomized approximation (PRAX) algorithms for the hard problems of NFA universality and NFA equivalence. Loosely speaking, PRAX algorithm…
cs.FL2014★ 6 cited
An efficient algorithm for computing the edit distance of a regular language via input-altering transducers
Lila Kari, Stavros Konstantinidis, Steffen Kopecki +1
We revisit the problem of computing the edit distance of a regular language given via an NFA. This problem relates to the inherent maximal error-detecting capability of the languag…