Free Access
Issue
RAIRO-Theor. Inf. Appl.
Volume 54, 2020
Article Number 3
Number of page(s) 23
DOI https://doi.org/10.1051/ita/2020002
Published online 10 April 2020
  1. I. Aalbersberg and G. Rozenberg. Theory of traces. Theor. Comput. Sci. 60 (1988) 1–82. [Google Scholar]
  2. J.M. Autebert, J. Berstel and L. Boasson. Context-free languages and pushdown automata, in Vol. 1 of Handbook of Formal Languages, edited by G. Rozenberg and A. Salomaa. Springer, Berlin (1997) 111–174. [CrossRef] [Google Scholar]
  3. J. Berstel. Transductions and Context-Free Languages. Leitfäden der angewandten Mathematik und Mechanik, Vol. 38. Teubner, Stuttgart (1979). [Google Scholar]
  4. A. Bertoni, G. Mauri and N. Sabadini, Membership problems for regular and context-free trace languages. Inf. Comput. 82 (1989) 135–150. [Google Scholar]
  5. G. Buntrock and F. Otto, Growing context-sensitive languages and Church-Rosser languages. Inf. Comput. 141 (1998) 1–36. [Google Scholar]
  6. E. Czeizler and E. Czeizler, A short survey on Watson-Crick automata. Bull. EATCS 88 (2006) 104–119. [CrossRef] [Google Scholar]
  7. E. Dahlhaus and M. Warmuth, Membership for growing context-sensitive grammars is polynomial. J. Comput. Syst. Sci. 33 (1986) 456–472. [Google Scholar]
  8. V. Diekert and G. Rozenberg, The Book of Traces. World Scientific, Singapore (1995). [CrossRef] [Google Scholar]
  9. H. Fernau, M. Paramasivan and M.L. Schmid, Jumping finite automata: Characterizations and complexity, CIAA 2012, Proc., edited by F. Drewes. In Vol. 9223 of Lect. Notes Comput. Sci. Springer, Heidelberg (2012) 89–101. [Google Scholar]
  10. R. Freund, Gh. Păun, G. Rozenberg and A. Salomaa, Watson-Crick finite automata, DNA Based Computers, Proc., DIMACS Series in Discrete Mathematics and Theoretical Computer Science, edited by H. Rubin and D.H. Wood. DIMACS/AMS, Rhode Island, USA (1999) 297–328. [CrossRef] [Google Scholar]
  11. S. Greibach, A note on undecidable properties of formal languages. Math. Syst. Theory 2 (1968) 1–6. [CrossRef] [Google Scholar]
  12. J.E. Hopcroft and J.D. Ullman, Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading, MA (1979). [Google Scholar]
  13. R. Kocman, B. Nagy, Z. Krivka and A. Meduna, A jumping 5′→3′ Watson-Crick finite automata model, Tenth Workshop on Non-Classical Models of Automata and Applications (NCMA 2018), Proc., edited by R. Freund, M. Hospodár, G. Jirásková and G. Pighizzini. Österreichische Computer Gesellschaft (2018) 117–132. [Google Scholar]
  14. P. Leupold and B. Nagy, 5→ 3 Watson-Crick automata with several runs. Fund. Inf. 104 (2010) 71–91. [Google Scholar]
  15. R. Loukanova, Linear context free languages, ICTAC 2007, Proc., edited by C.B. Jones, Z. Liu, and J. Woodcock. In Vol. 4711 of Lect. Notes Comput. Sci. Springer, Heidelberg (2007) 351–365. [Google Scholar]
  16. A. Meduna and P. Zemek, Jumping finite automata. Int. J. Found. Comput. Sci. 23 (2012) 1555–1578. [CrossRef] [Google Scholar]
  17. B. Nagy, On 5′→ 3′ sensing Watson-Crick automata, DNA Computing, 13th International Meeting (2007), Revised Selected Papers, edited by M. Garzon and H. Yan. In Vol. 4848 of Lect. Notes Comput. Sci. Springer, Heidelberg (2008) 256–262. [Google Scholar]
  18. B. Nagy, A class of 2-head finite automata for linear languages. Triangle 8 (2012) 89–99. [Google Scholar]
  19. B. Nagy, On a hierarchy of 5→ 3 sensing Watson-Crick finite automata languages, J. Logic Comput. 23 (2013) 855–872. [CrossRef] [Google Scholar]
  20. B. Nagy and L. Kovács, Finite automata with translucent letters applied in natural and formal language theory, Transactions on Computational Collective Intelligence XVII, edited by N.T. Nguyen, R. Kowalczyk, A. Fred and F. Joaquim. In Vol. 8790 of Lect. Notes Comput. Sci. Springer, Heidelberg (2014), pages 107–127. [Google Scholar]
  21. B. Nagy and Z. Kovács, On simple 5′→3′ sensing Watson-Crick finite-state transducers, Eleventh Workshop on Non-Classical Models of Automata and Applications (NCMA 2019), Proc., edited by R. Freund, M. Holzer and J.M. Sempere. Österreichische Computer Gesellschaft (2019) 155–170. [Google Scholar]
  22. B. Nagy and F. Otto, CD-systems of stateless deterministic R(1)-automata accept all rational trace languages. LATA 2010, Proc., edited by A.H. Dediu, H. Fernau and C. Martin-Vide. In Vol. 6031 of Lect. Notes Comput. Sci. Springer, Heidelberg (2010) 463–474. [Google Scholar]
  23. B. Nagy and F. Otto, An automata-theoretical characterization of context-free trace languages, SOFSEM 2011, Proc., edited by I. Cerná, T. Gyimóthy, J. Hromkovic, K.G. Jeffery, R. Královic, M. Vukolic and S. Wolf. In Vol. 6543 of Lect. Notes Comput. Sci. Springer, Heidelberg (2011) 406–417. [Google Scholar]
  24. B. Nagy and F. Otto, CD-systems of stateless deterministic R(1)-automata governed by an external pushdown store. RAIRO: ITA 45 (2011) 413–448. [Google Scholar]
  25. B. Nagy and F. Otto, Finite-state acceptors with translucent letters, BILC 2011: AI Methods for Interdisciplinary Research in Language and Biology Proc., edited by G. Bel-Enguix, V. Dahl and A.O. De La Puente. SciTePress, Portugal (2011) 3–13. [Google Scholar]
  26. B. Nagy and F. Otto, On CD-systems of stateless deterministic R-automata with window size one, J. Comput. Syst. Sci. 78 (2012) 780–806. [Google Scholar]
  27. B. Nagy and F. Otto, Globally deterministic CD-systems of stateless R-automata with window size 1, Int. J. Comput. Math. 90 (2013) 1254–1277. [Google Scholar]
  28. B. Nagy and F. Otto, Two-head finite-state acceptors with translucent letters, SOFSEM 2019, Proc., edited by B. Catania, R. Královič, J. Nawrocki and G. Pighizzini. In Vol. 11376 of Lect. Notes Comput. Sci. Springer, Heidelberg (2019) 406–418. [Google Scholar]
  29. B. Nagy and S. Parchami, On deterministic sensing 5→ 3 Watson-Crick finite automata: A full hierarchy in 2detlin. Acta Inf. DOI: 10.1007/s00236-019-00362-6 (2020). [Google Scholar]
  30. B. Nagy, S. Parchami and H.M.M. Sadeghi, A new sensing 5′→ 3′ Watson-Crick automata concept, 15th International Conference on Automata and Languages (AFL 2017), in Vol. 252 of EPTCS, edited by E. Csuhaj-Varjú, P. Dömösi and Gy. Vaszil (2017) 195–204. [Google Scholar]
  31. S. Parchami and B. Nagy, Deterministic sensing 5′→ 3′ Watson-Crick automata without sensing parameter, Unconventional Computation and Natural Computation - 17th Int. Conf. (UCNC 2018) Proc., edited by S. Stepney and S. Verlan. In Vol. 10867 of Lect. Notes Comput. Sci. Springer, Heidelberg (2018) 173–187. [Google Scholar]
  32. Gh. Păun, G. Rozenberg and A. Salomaa, DNA Computing - New Computing Paradigms. Springer, Heidelberg (1998). [Google Scholar]
  33. A.L. Rosenberg, On multi-head finite automata. IBM J. Res. Dev. 10 (1966) 388–394. [Google Scholar]
  34. G. Rozenberg and A. Salomaa, Handbook of Formal Languages. Springer, Heidelberg (1997). [Google Scholar]
  35. M. Sipser, Introduction to the Theory of Computation. PWS Publishing Company, Boston, MA (1997). [Google Scholar]

Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.

Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.

Initial download of the metrics may take a while.