Approximate matching between a context-free grammar and a finite-state automaton

Sang Ki Ko, Yo Sub Han, Kai Salomaa

Research output: Contribution to journalArticlepeer-review

9 Citations (Scopus)


For a given context-free grammar (CFG) and a finite-state automaton (FA), we tackle the edit-distance problem-the problem of computing the most similar pair of strings in the two respective languages. In particular, we consider three different gap cost models for the edit-distance that are crucial for finding a proper alignment between two bio sequences: The linear, affine and concave models. We design efficient algorithms for the edit-distance between a CFG and an FA under these gap cost models. The time complexity of our algorithm for computing the linear or affine gap distance is polynomial and the time complexity for the concave gap distance is exponential.

Original languageEnglish
Pages (from-to)278-289
Number of pages12
JournalInformation and Computation
Publication statusPublished - 2016 Apr 1

Bibliographical note

Publisher Copyright:
© 2016 Elsevier Inc. All rights reserved.

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics


Dive into the research topics of 'Approximate matching between a context-free grammar and a finite-state automaton'. Together they form a unique fingerprint.

Cite this