{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,28]],"date-time":"2026-06-28T18:49:51Z","timestamp":1782672591776,"version":"3.54.5"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2020,1,6]],"date-time":"2020-01-06T00:00:00Z","timestamp":1578268800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,1,6]],"date-time":"2020-01-06T00:00:00Z","timestamp":1578268800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[2021,6]]},"DOI":"10.1007\/s00236-019-00362-6","type":"journal-article","created":{"date-parts":[[2020,1,6]],"date-time":"2020-01-06T18:03:55Z","timestamp":1578333835000},"page":"153-175","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":15,"title":["On deterministic sensing $$5'\\rightarrow 3'$$ Watson\u2013Crick finite automata: a full hierarchy in 2detLIN"],"prefix":"10.1007","volume":"58","author":[{"given":"Benedek","family":"Nagy","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shaghayegh","family":"Parchami","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2020,1,6]]},"reference":[{"key":"362_CR1","doi-asserted-by":"publisher","first-page":"1021","DOI":"10.1126\/science.7973651","volume":"226","author":"LM Adleman","year":"1994","unstructured":"Adleman, L.M.: Molecular computation of solutions to combinational problems. Science 226, 1021\u20131024 (1994)","journal-title":"Science"},{"issue":"3","key":"362_CR2","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1016\/S0019-9958(64)90294-3","volume":"7","author":"V Amar","year":"1964","unstructured":"Amar, V., Putzolu, G.R.: On a family of linear grammars. Inf. Control 7(3), 283\u2013291 (1964)","journal-title":"Inf. Control"},{"key":"362_CR3","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1308\/147363506X101210","volume":"88","author":"E Czeizler","year":"2006","unstructured":"Czeizler, E.: A short survey on Watson\u2013Crick automata. Bull. EATCS 88, 104\u2013119 (2006)","journal-title":"Bull. EATCS"},{"key":"362_CR4","doi-asserted-by":"crossref","unstructured":"Fernau, F., Sempere, J.M.: Permutations and control sets for learning non-regular language families. In: ICGI 2000, LNCS\/LNAI 1891, pp. 75\u201388 (2000)","DOI":"10.1007\/978-3-540-45257-7_7"},{"key":"362_CR5","doi-asserted-by":"crossref","unstructured":"Freund, R., P\u0103un, G., Rozenberg, G. , Salomaa, A.: Watson\u2013Crick finite automata. In: 3rd DIMACS Symposium on DNA Based Computers, pp. 297\u2013328, Philadelphia (1997)","DOI":"10.1090\/dimacs\/048\/22"},{"issue":"3","key":"362_CR6","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1007\/s11047-011-9290-9","volume":"11","author":"L Heged\u00fcs","year":"2012","unstructured":"Heged\u00fcs, L., Nagy, B., Egecioglu, \u00d6.: Stateless multicounter $$5^{\\prime } \\rightarrow 3^{\\prime }$$ Watson\u2013Crick automata: the deterministic case. Nat. Comput. 11(3), 361\u2013368 (2012)","journal-title":"Nat. Comput."},{"key":"362_CR7","first-page":"135","volume":"2017","author":"M Holzer","year":"2017","unstructured":"Holzer, M., Kutrib, M., Otto, F.: Two-sided strictly locally testable languages. NCMA 2017, 135\u2013150 (2017)","journal-title":"NCMA"},{"key":"362_CR8","series-title":"Languages and Computation","volume-title":"Introduction to Automata Theory","author":"JE Hopcroft","year":"1979","unstructured":"Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory. Languages and Computation. Addison-Wesley Publishing Company, Reading (1979)"},{"key":"362_CR9","first-page":"117","volume":"2018","author":"R Kocman","year":"2018","unstructured":"Kocman, R., Nagy, B., Krivka, Z., Meduna, A.: A jumping $$5^{\\prime } \\rightarrow 3^{\\prime }$$ Watson\u2013Crick finite automata model. NCMA 2018, 117\u2013132 (2018)","journal-title":"NCMA"},{"key":"362_CR10","doi-asserted-by":"crossref","unstructured":"Kuske, D., Weigel, P.: The role of the complementarity relation in Watson\u2013Crick automata and sticker systems. In: DLT 2004, LNCS 3340, pp. 272\u2013283 (2004)","DOI":"10.1007\/978-3-540-30550-7_23"},{"key":"362_CR11","first-page":"133","volume":"2018","author":"M Kutrib","year":"2018","unstructured":"Kutrib, M., Otto, F.: Two-sided locally testable languages. NCMA 2018, 133\u2013148 (2018)","journal-title":"NCMA"},{"key":"362_CR12","doi-asserted-by":"publisher","first-page":"71","DOI":"10.3233\/FI-2010-336","volume":"104","author":"P Leupold","year":"2010","unstructured":"Leupold, P., Nagy, B.: $$5^{\\prime } \\rightarrow 3^{\\prime }$$ Watson\u2013Crick automata with several runs. Fundam. Inform. 104, 71\u201391 (2010)","journal-title":"Fundam. Inform."},{"key":"362_CR13","unstructured":"Nagy, B.: On $$5^{\\prime } \\rightarrow 3^{\\prime }$$ sensing Watson\u2013Crick finite automata. In: Preproceedings of DNA07, the 13th International Meeting on DNA Computing, pp. 327\u2013336, Memphis, Tennessee, USA (2007)"},{"key":"362_CR14","doi-asserted-by":"crossref","unstructured":"Nagy, B.: On $$5^{\\prime } \\rightarrow 3^{\\prime }$$ sensing Watson\u2013Crick finite automata. In: DNA 2007: Selected, Revised Papers, LNCS 4848, pp. 256\u2013262 (2008)","DOI":"10.1007\/978-3-540-77962-9_27"},{"key":"362_CR15","unstructured":"Nagy, B.: On a hierarchy of $$5^{\\prime } \\rightarrow 3^{\\prime }$$ sensing WK finite automata languages. In: CiE 2009, Abstract Booklet, pp. 266\u2013275 (2009)"},{"key":"362_CR16","unstructured":"Nagy, B.: $$5^{\\prime } \\rightarrow 3^{\\prime }$$ sensing Watson\u2013Crick finite automata. In: Fung, G. (ed.) Sequence and Genome Analysis II\u2014Methods and Applications, pp. 39\u201356. iConcept Press (2010)"},{"key":"362_CR17","doi-asserted-by":"crossref","unstructured":"Nagy, B.: A class of 2-head finite automata for linear languages. Triangle: Lang. Math. Approaches 8, 89\u201399 (2012)","DOI":"10.17345\/triangle8.89-99"},{"issue":"4","key":"362_CR18","doi-asserted-by":"publisher","first-page":"855","DOI":"10.1093\/logcom\/exr049","volume":"23","author":"B Nagy","year":"2013","unstructured":"Nagy, B.: On a hierarchy of $$5^{\\prime } \\rightarrow 3^{\\prime }$$ sensing Watson\u2013Crick finite automata languages. J. Log. Comput. 23(4), 855\u2013872 (2013)","journal-title":"J. Log. Comput."},{"key":"362_CR19","first-page":"177","volume":"2015","author":"B Nagy","year":"2015","unstructured":"Nagy, B.: A family of two-head pushdown automata. NCMA 2015, 177\u2013191 (2015)","journal-title":"NCMA"},{"key":"362_CR20","first-page":"155","volume":"2019","author":"B Nagy","year":"2019","unstructured":"Nagy, B., Kov\u00e1cs, Z.: On simple $$5^{\\prime } \\rightarrow 3^{\\prime }$$ sensing Watson\u2013Crick finite-state transducers. NCMA 2019, 155\u2013170 (2019)","journal-title":"NCMA"},{"key":"362_CR21","doi-asserted-by":"crossref","unstructured":"Nagy, B., Otto, F.: Two-head finite-state acceptors with translucent letters. In: SOFSEM 2019, LNCS 11376, pp. 406\u2013418 (2019)","DOI":"10.1007\/978-3-030-10801-4_32"},{"key":"362_CR22","doi-asserted-by":"crossref","unstructured":"Nagy, B., Otto, F.: Linear automata with translucent letters and linear context-free trace languages. In: RAIRO\u2014Theoretical Informatics and Applications, accepted for publication (2019)","DOI":"10.1051\/ita\/2020002"},{"key":"362_CR23","doi-asserted-by":"crossref","unstructured":"Nagy, B., Parchami, Sh., Mir-Mohammad-Sadeghi, H.: A new sensing $$5^{\\prime } \\rightarrow 3^{\\prime }$$ Watson\u2013Crick automata concept. In: AFL 2017, EPTCS 252, pp. 195\u2013204 (2017)","DOI":"10.4204\/EPTCS.252.19"},{"key":"362_CR24","doi-asserted-by":"crossref","unstructured":"Parchami, Sh., Nagy B.: Deterministic sensing $$5^{\\prime }\\rightarrow 3^{\\prime }$$ Watson\u2013Crick automata without sensing parameter. In: UCNC 2018, LNCS 10867, pp. 173\u2013187 (2018)","DOI":"10.1007\/978-3-319-92435-9_13"},{"key":"362_CR25","volume-title":"DNA Computing\u2014New Computing Paradigms","author":"G P\u0103un","year":"2002","unstructured":"P\u0103un, G., Rozenberg, G., Salomaa, A.: DNA Computing\u2014New Computing Paradigms. Springer, Berlin (2002)"},{"key":"362_CR26","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-59126-6","volume-title":"The Handbook of Formal Languages","author":"G Rozenberg","year":"1997","unstructured":"Rozenberg, G., Salomaa, A.: The Handbook of Formal Languages. Springer, Berlin (1997)"},{"key":"362_CR27","first-page":"29","volume":"2018","author":"JM Sempere","year":"2018","unstructured":"Sempere, J.M.: On the application of Watson\u2013Crick finite automata for the resolution of bioinformatic problems. NCMA 2018, 29\u201330 (2018)","journal-title":"NCMA"},{"key":"362_CR28","doi-asserted-by":"crossref","unstructured":"Sempere, J.M., Garc\u00eda, P.: A characterization of even linear languages and its application to the learning problem. In: ICGI 1994, LNCS\/LNAI 862, pp. 38\u201344 (1994)","DOI":"10.1007\/3-540-58473-0_135"},{"key":"362_CR29","doi-asserted-by":"crossref","unstructured":"Sempere, J.M., Garc\u00eda, P.: Learning locally testable even linear languages from positive data. In: ICGI 2002, LNCS\/LNAI 2484, pp. 225\u2013236 (2002)","DOI":"10.1007\/3-540-45790-9_18"}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-019-00362-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00236-019-00362-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-019-00362-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,15]],"date-time":"2021-05-15T08:03:57Z","timestamp":1621065837000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00236-019-00362-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1,6]]},"references-count":29,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,6]]}},"alternative-id":["362"],"URL":"https:\/\/doi.org\/10.1007\/s00236-019-00362-6","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"value":"0001-5903","type":"print"},{"value":"1432-0525","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,1,6]]},"assertion":[{"value":"21 November 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 December 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 January 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}