{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:10:26Z","timestamp":1725664226182},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540612582"},{"type":"electronic","value":"9783540683902"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/3-540-61258-0_28","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T21:21:26Z","timestamp":1330291286000},"page":"384-391","source":"Crossref","is-referenced-by-count":2,"title":["Finite-state computability of annotations of strings and trees (extended abstract)"],"prefix":"10.1007","author":[{"given":"Hans L.","family":"Bodlaender","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael R.","family":"Fellows","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Patricia A.","family":"Evans","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"28_CR1","doi-asserted-by":"crossref","first-page":"539","DOI":"10.1090\/conm\/147\/01199","volume":"147","author":"K. Abrahamson","year":"1993","unstructured":"K. Abrahamson and M. Fellows. [AF93] K. Abrahamson and M. Fellows. Finite automata, bounded treewidth and well-quasi-ordering. In: Graph Structure Theory: Proceedings of the Joint Summer Research Conference on Graph Minors, Seattle, June, 1991, American Mathematical Society, Contemporary Mathematics 147 (1993), 539\u2013564.","journal-title":"American Mathematical Society, Contemporary Mathematics"},{"key":"28_CR2","doi-asserted-by":"crossref","unstructured":"H. Bodlaender. A linear time algorithm for finding tree-decompositions of small width. In Proceedings of the 25th Annual Symposium on Theory of Computing (1993), 226\u2013234. To appear in SIAM J. Comput.","DOI":"10.1145\/167088.167161"},{"key":"28_CR3","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B. Courcelle","year":"1990","unstructured":"B. Courcelle. The monadic second-order logic of graphs I: Recognizable sets of finite graphs. Information and Computation 85 (1990), 12\u201375.","journal-title":"Information and Computation"},{"key":"28_CR4","first-page":"389","volume":"10","author":"F. Corpet","year":"1994","unstructured":"F. Corpet and B. Minchot. RNAlign program: alignment of RNA sequences using both primary and secondary structures. Computer Applications in the Biosciences 10 (1994), 389\u2013399.","journal-title":"Computer Applications in the Biosciences"},{"key":"28_CR5","doi-asserted-by":"crossref","first-page":"540","DOI":"10.1006\/geno.1994.1541","volume":"23","author":"S. Dong","year":"1994","unstructured":"S. Dong and D. Searls. Gene structure prediction by linguistic methods. Genomics 23 (1994), 540\u2013551.","journal-title":"Genomics"},{"key":"28_CR6","unstructured":"S. Eilenberg. Automata, Languages, and Machines: Volume A. Academic Press, 1974."},{"key":"28_CR7","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1147\/rd.91.0047","volume":"9","author":"C. Elgot","year":"1965","unstructured":"C. Elgot and J. Mezei. On relations defined by generalized finite automata. IBM Journal of Research 9 (1965), 47\u201368.","journal-title":"IBM Journal of Research"},{"key":"28_CR8","doi-asserted-by":"crossref","first-page":"1251","DOI":"10.1093\/nar\/21.5.1251","volume":"21","author":"K. Han","year":"1993","unstructured":"K. Han and H. Kim. Prediction of common folding structures of homologous RNAs. Nucleic Acids Res. 21 (1993), 1251\u20131257.","journal-title":"Nucleic Acids Res."},{"key":"28_CR9","doi-asserted-by":"crossref","unstructured":"C. Johnson. Formal Aspects of Phonological Description. Mouton, 1972.","DOI":"10.1515\/9783110876000"},{"key":"28_CR10","first-page":"331","volume":"20","author":"R. Kaplan","year":"1994","unstructured":"R. Kaplan and M. Kay. Regular models of phonological rule systems. Computational Linguistics 20 (1994), 331\u2013378.","journal-title":"Computational Linguistics"},{"key":"28_CR11","unstructured":"K. Koskenniemi. Two-level morphology: a general computational model for word-form recognition and production. Ph.D. thesis, University of Helsinki."},{"key":"28_CR12","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1016\/0022-2836(70)90057-4","volume":"48","author":"S. Needleman","year":"1970","unstructured":"S. Needleman and C. Wunsch. A general method applicable to the search for similarities in the amino-acid sequence of two proteins. Journal of Molecular Biology 48 (1970), 443\u2013453.","journal-title":"Journal of Molecular Biology"},{"key":"28_CR13","unstructured":"B. Rost, R. Schneider, A. de Daruvar, and C. Sander. The PredictProtein server. http:\/\/www.embl-heidelberg.de\/predictprotein\/predictprotein.html"},{"key":"28_CR14","doi-asserted-by":"crossref","unstructured":"D. Searls and S. Dong. A syntactic pattern recognition system for DNA sequences. Proceedings of the Second International Conference on Bioinformatics, Supercomputing, and Complex Genome Analysis (1993), 89\u2013101.","DOI":"10.1142\/9789814503655_0008"},{"key":"28_CR15","unstructured":"D. Searls. The computational linguistics of biological sequences. In Artificial Intelligence and Molecular Biology, AAAI Press, 1993, 47\u2013120."},{"key":"28_CR16","doi-asserted-by":"crossref","unstructured":"D. Searls. Formal grammars for intermolecular structure. Proceedings of the International IEEE Symposium on Intelligence in Neural and Biological Systems (1995).","DOI":"10.1109\/INBS.1995.404291"},{"key":"28_CR17","doi-asserted-by":"crossref","unstructured":"R. Sproat. Morphology and Computation. MIT Press, 1992.","DOI":"10.7551\/mitpress\/4775.001.0001"},{"key":"28_CR18","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/0022-2836(81)90087-5","volume":"147","author":"T. Smith","year":"1981","unstructured":"T. Smith and M. Waterman. Identification of common molecular subsequences. Journal of Molecular Biology 147 (1981), 195\u2013197.","journal-title":"Journal of Molecular Biology"},{"key":"28_CR19","doi-asserted-by":"crossref","unstructured":"G. Stephen. String Searching Algorithms. Lecture Notes Series on Computing, vol. 3. World Scientific, 1994.","DOI":"10.1142\/2418"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-61258-0_28.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:04:44Z","timestamp":1605647084000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-61258-0_28"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540612582","9783540683902"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/3-540-61258-0_28","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1996]]}}}