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

Yo Sub Han; Sang Ki Ko; Kai Salomaa

doi:10.1007/978-3-642-39274-0_14

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

Yo Sub Han, Sang Ki Ko, Kai Salomaa

Department of Artificial Intelligence

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

5 Scopus citations

Abstract

Given a context-free grammar (CFG) and a finite-state automaton (FA), we tackle the problem of computing the most similar pair of strings from two languages. We in particular consider three different gap cost models, linear, affine and concave models, that are crucial for finding a proper alignment between two bio sequences. We design efficient algorithms for computing 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 language	English
Title of host publication	Implementation and Application of Automata - 18th International Conference, CIAA 2013, Proceedings
Pages	146-157
Number of pages	12
DOIs	https://doi.org/10.1007/978-3-642-39274-0_14
State	Published - 2013
Event	18th International Conference on Implementation and Application of Automata, CIAA 2013 - Halifax, NS, Canada Duration: 16 Jul 2013 → 19 Jul 2013

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	7982 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	18th International Conference on Implementation and Application of Automata, CIAA 2013
Country/Territory	Canada
City	Halifax, NS
Period	16/07/13 → 19/07/13

Keywords

approximate matching
context-free grammars
edit-distance
finite-state automata

Access to Document

10.1007/978-3-642-39274-0_14

Cite this

Han, Y. S., Ko, S. K., & Salomaa, K. (2013). Approximate matching between a context-free grammar and a finite-state automaton. In Implementation and Application of Automata - 18th International Conference, CIAA 2013, Proceedings (pp. 146-157). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7982 LNCS). https://doi.org/10.1007/978-3-642-39274-0_14

Han, Yo Sub ; Ko, Sang Ki ; Salomaa, Kai. / Approximate matching between a context-free grammar and a finite-state automaton. Implementation and Application of Automata - 18th International Conference, CIAA 2013, Proceedings. 2013. pp. 146-157 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{7bd87dfd52c14c9b9dfd7c9bca506bdd,

title = "Approximate matching between a context-free grammar and a finite-state automaton",

abstract = "Given a context-free grammar (CFG) and a finite-state automaton (FA), we tackle the problem of computing the most similar pair of strings from two languages. We in particular consider three different gap cost models, linear, affine and concave models, that are crucial for finding a proper alignment between two bio sequences. We design efficient algorithms for computing 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.",

keywords = "approximate matching, context-free grammars, edit-distance, finite-state automata",

author = "Han, {Yo Sub} and Ko, {Sang Ki} and Kai Salomaa",

year = "2013",

doi = "10.1007/978-3-642-39274-0_14",

language = "English",

isbn = "9783642392733",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "146--157",

booktitle = "Implementation and Application of Automata - 18th International Conference, CIAA 2013, Proceedings",

note = "18th International Conference on Implementation and Application of Automata, CIAA 2013 ; Conference date: 16-07-2013 Through 19-07-2013",

}

Han, YS, Ko, SK & Salomaa, K 2013, Approximate matching between a context-free grammar and a finite-state automaton. in Implementation and Application of Automata - 18th International Conference, CIAA 2013, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7982 LNCS, pp. 146-157, 18th International Conference on Implementation and Application of Automata, CIAA 2013, Halifax, NS, Canada, 16/07/13. https://doi.org/10.1007/978-3-642-39274-0_14

Approximate matching between a context-free grammar and a finite-state automaton. / Han, Yo Sub; Ko, Sang Ki; Salomaa, Kai.
Implementation and Application of Automata - 18th International Conference, CIAA 2013, Proceedings. 2013. p. 146-157 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7982 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

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

AU - Han, Yo Sub

AU - Ko, Sang Ki

AU - Salomaa, Kai

PY - 2013

Y1 - 2013

N2 - Given a context-free grammar (CFG) and a finite-state automaton (FA), we tackle the problem of computing the most similar pair of strings from two languages. We in particular consider three different gap cost models, linear, affine and concave models, that are crucial for finding a proper alignment between two bio sequences. We design efficient algorithms for computing 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.

AB - Given a context-free grammar (CFG) and a finite-state automaton (FA), we tackle the problem of computing the most similar pair of strings from two languages. We in particular consider three different gap cost models, linear, affine and concave models, that are crucial for finding a proper alignment between two bio sequences. We design efficient algorithms for computing 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.

KW - approximate matching

KW - context-free grammars

KW - edit-distance

KW - finite-state automata

UR - http://www.scopus.com/inward/record.url?scp=84881258883&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-39274-0_14

DO - 10.1007/978-3-642-39274-0_14

M3 - Conference contribution

AN - SCOPUS:84881258883

SN - 9783642392733

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 146

EP - 157

BT - Implementation and Application of Automata - 18th International Conference, CIAA 2013, Proceedings

T2 - 18th International Conference on Implementation and Application of Automata, CIAA 2013

Y2 - 16 July 2013 through 19 July 2013

ER -

Han YS, Ko SK, Salomaa K. Approximate matching between a context-free grammar and a finite-state automaton. In Implementation and Application of Automata - 18th International Conference, CIAA 2013, Proceedings. 2013. p. 146-157. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-39274-0_14

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

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this