{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T20:19:14Z","timestamp":1725740354888},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642392733"},{"type":"electronic","value":"9783642392740"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-39274-0_14","type":"book-chapter","created":{"date-parts":[[2013,7,10]],"date-time":"2013-07-10T21:07:42Z","timestamp":1373490462000},"page":"146-157","source":"Crossref","is-referenced-by-count":2,"title":["Approximate Matching between a Context-Free Grammar and a Finite-State Automaton"],"prefix":"10.1007","author":[{"given":"Yo-Sub","family":"Han","sequence":"first","affiliation":[]},{"given":"Sang-Ki","family":"Ko","sequence":"additional","affiliation":[]},{"given":"Kai","family":"Salomaa","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"4","key":"14_CR1","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1137\/0201022","volume":"1","author":"A. Aho","year":"1972","unstructured":"Aho, A., Peterson, T.: A minimum distance error-correcting parser for context-free languages. SIAM Journal on Computing\u00a01(4), 305\u2013312 (1972)","journal-title":"SIAM Journal on Computing"},{"key":"14_CR2","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1090\/qam\/102435","volume":"16","author":"R. Bellman","year":"1958","unstructured":"Bellman, R.: On a routing problem. Quarterly of Applied Mathematics\u00a016, 87\u201390 (1958)","journal-title":"Quarterly of Applied Mathematics"},{"issue":"1","key":"14_CR3","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1016\/S0304-3975(01)00238-9","volume":"286","author":"C. Choffrut","year":"2002","unstructured":"Choffrut, C., Pighizzini, G.: Distances between languages and reflexivity of relations. Theoretical Computer Science\u00a0286(1), 117\u2013138 (2002)","journal-title":"Theoretical Computer Science"},{"key":"14_CR4","unstructured":"Cocke, J.: Programming languages and their compilers: Preliminary notes. Courant Institute of Mathematical Sciences. New York University (1969)"},{"key":"14_CR5","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"E. Dijkstra","year":"1959","unstructured":"Dijkstra, E.: A note on two problems in connexion with graphs. Numerische Mathematik\u00a01, 269\u2013271 (1959)","journal-title":"Numerische Mathematik"},{"issue":"2","key":"14_CR6","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1145\/362007.362035","volume":"13","author":"J. Earley","year":"1970","unstructured":"Earley, J.: An efficient context-free parsing algorithm. Communications of the ACM\u00a013(2), 94\u2013102 (1970)","journal-title":"Communications of the ACM"},{"issue":"6","key":"14_CR7","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1145\/367766.368168","volume":"5","author":"R.W. Floyd","year":"1962","unstructured":"Floyd, R.W.: Algorithm 97: Shortest path. Communications of the ACM\u00a05(6), 345\u2013348 (1962)","journal-title":"Communications of the ACM"},{"issue":"2","key":"14_CR8","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/S0019-9958(67)80007-X","volume":"10","author":"D.H. Younger","year":"1967","unstructured":"Younger, D.H.: Recognition and parsing of context-free languages in time n\n 3. Information and Control\u00a010(2), 189\u2013208 (1967)","journal-title":"Information and Control"},{"key":"14_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-3-642-31653-1_9","volume-title":"Developments in Language Theory","author":"Y.-S. Han","year":"2012","unstructured":"Han, Y.-S., Ko, S.-K., Salomaa, K.: Computing the edit-distance between a regular language and a context-free language. In: Yen, H.-C., Ibarra, O.H. (eds.) DLT 2012. LNCS, vol.\u00a07410, pp. 85\u201396. Springer, Heidelberg (2012)"},{"key":"14_CR10","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"J. Hopcroft","year":"1979","unstructured":"Hopcroft, J., Ullman, J.: Introduction to Automata Theory, Languages, and Computation, 2nd edn. Addison-Wesley, Reading (1979)","edition":"2"},{"key":"14_CR11","first-page":"293","volume":"9","author":"L. Kari","year":"2004","unstructured":"Kari, L., Konstantinidis, S.: Descriptional complexity of error\/edit systems. Journal of Automata, Languages and Combinatorics\u00a09, 293\u2013309 (2004)","journal-title":"Journal of Automata, Languages and Combinatorics"},{"key":"14_CR12","unstructured":"Kasami, T.: An efficient recognition and syntax-analysis algorithm for context-free languages. Technical report, Air Force Cambridge Research Lab, Bedford, MA (1965)"},{"key":"14_CR13","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1007\/BF01300375","volume":"14","author":"J.R. Knight","year":"1995","unstructured":"Knight, J.R., Myers, E.W.: Approximate regular expression pattern matching with concave gap penalties. Algorithmica\u00a014, 67\u201378 (1995)","journal-title":"Algorithmica"},{"key":"14_CR14","doi-asserted-by":"publisher","first-page":"1307","DOI":"10.1016\/j.ic.2007.06.001","volume":"205","author":"S. Konstantinidis","year":"2007","unstructured":"Konstantinidis, S.: Computing the edit distance of a regular language. Information and Computation\u00a0205, 1307\u20131316 (2007)","journal-title":"Information and Computation"},{"issue":"8","key":"14_CR15","first-page":"707","volume":"10","author":"V.I. Levenshtein","year":"1966","unstructured":"Levenshtein, V.I.: Binary codes capable of correcting deletions, insertions, and reversals. Soviet Physics Doklady\u00a010(8), 707\u2013710 (1966)","journal-title":"Soviet Physics Doklady"},{"issue":"1","key":"14_CR16","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1145\/360767.360771","volume":"17","author":"G. Lyon","year":"1974","unstructured":"Lyon, G.: Syntax-directed least-errors analysis for context-free languages: a practical approach. Communications of the ACM\u00a017(1), 3\u201314 (1974)","journal-title":"Communications of the ACM"},{"issue":"2","key":"14_CR17","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1007\/BF02459948","volume":"50","author":"W. Miller","year":"1988","unstructured":"Miller, W., Myers, E.W.: Sequence comparison with concave weighting functions. Bulletin of Mathematical Biology\u00a050(2), 97\u2013120 (1988)","journal-title":"Bulletin of Mathematical Biology"},{"issue":"6","key":"14_CR18","doi-asserted-by":"publisher","first-page":"957","DOI":"10.1142\/S0129054103002114","volume":"14","author":"M. Mohri","year":"2003","unstructured":"Mohri, M.: Edit-distance of weighted automata: General definitions and algorithms. International Journal of Foundations of Computer Science\u00a014(6), 957\u2013982 (2003)","journal-title":"International Journal of Foundations of Computer Science"},{"key":"14_CR19","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/0020-0190(95)00007-Y","volume":"54","author":"G. Myers","year":"1995","unstructured":"Myers, G.: Approximately matching context-free languages. Information Processing Letters\u00a054, 85\u201392 (1995)","journal-title":"Information Processing Letters"},{"issue":"3","key":"14_CR20","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1016\/0022-2836(70)90057-4","volume":"48","author":"S.B. Needleman","year":"1970","unstructured":"Needleman, S.B., Wunsch, C.D.: A general method applicable to the search for similarities in the amino acid sequence of two proteins. Journal of Molecular Biology\u00a048(3), 443\u2013453 (1970)","journal-title":"Journal of Molecular Biology"},{"key":"14_CR21","unstructured":"Sankoff, D., Kruskal, J.B.: Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison. Addison-Wesley (1983)"},{"key":"14_CR22","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1016\/S0022-5193(84)80037-5","volume":"108","author":"M.S. Waterman","year":"1984","unstructured":"Waterman, M.S.: Efficient sequence alignment algorithms. Journal of Theoretical Biology\u00a0108, 333\u2013337 (1984)","journal-title":"Journal of Theoretical Biology"},{"key":"14_CR23","unstructured":"Wood, D.: Theory of Computation. Harper & Row (1987)"}],"container-title":["Lecture Notes in Computer Science","Implementation and Application of Automata"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-39274-0_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,15]],"date-time":"2019-05-15T14:44:45Z","timestamp":1557931485000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-39274-0_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642392733","9783642392740"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-39274-0_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}