Linear automata with translucent letters and linear context-free trace languages

Nagy, Benedek; Otto, Friedrich

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 54 (2020), article no. 3.

Suite au passage du modèle économique de la revue en S20, le texte intégral des articles des années 2019 et 2020 est accessible uniquement sur le site de l'éditeur et est réservé aux abonnés.

Linear automata with translucent letters are studied. These are finite-state acceptors that have two heads that read the input from opposite sides and for which a set of translucent letters is associated with each state. Thus, head 1, which proceeds from left to right, does not necessarily read the first letter of the current tape content, but it skips a prefix that consists of translucent letters only and reads the first letter after that prefix. Analogously, head 2, which proceeds from right to left, does not necessarily read the last letter, but it skips a suffix that consists of translucent letters only and reads the last letter before that. After such a read operation, the head always returns to its corresponding end of the tape. These linear automata with translucent letters are a generalization of the finite-state acceptors with translucent letters that were studied by the authors in B. Nagy and F. Otto [Finite-state acceptors with translucent letters. In BILC 2011, Proc., edited by G. Bel-Enguix, V. Dahl, and A.O. De La Pente, SciTePress, Portugal (2011) 3-13.] It is shown that these linear automata are strictly more expressive than the model with a single head, but that they still only accept languages that have a semi-linear Parikh image. On the other hand, we obtain a characterization for the class of linear context-free trace languages in terms of a specific class of linear automata with translucent letters.

[1] I. Aalbersberg and G. Rozenberg. Theory of traces.   Theor. Comput. Sci. 60 (1988) 1–82. | DOI | MR | Zbl

[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. | DOI | MR

[3] J. Berstel. Transductions and Context-Free Languages. Leitfäden der angewandten Mathematik und Mechanik, Vol. 38. Teubner, Stuttgart (1979). | MR | Zbl

[4] A. Bertoni, G. Mauri and N. Sabadini, Membership problems for regular and context-free trace languages.   Inf. Comput. 82 (1989) 135–150. | DOI | MR | Zbl

[5] G. Buntrock and F. Otto, Growing context-sensitive languages and Church-Rosser languages.   Inf. Comput. 141 (1998) 1–36. | DOI | MR | Zbl

[6] E. Czeizler and E. Czeizler, A short survey on Watson-Crick automata. Bull. EATCS 88 (2006) 104–119. | MR | Zbl

[7] E. Dahlhaus and M. Warmuth, Membership for growing context-sensitive grammars is polynomial.   J. Comput. Syst. Sci. 33 (1986) 456–472. | DOI | MR | Zbl

[8] V. Diekert and G. Rozenberg, The Book of Traces. World Scientific, Singapore (1995). | DOI | MR

[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. | MR | Zbl

[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. | DOI | MR | Zbl

[11] S. Greibach, A note on undecidable properties of formal languages.   Math. Syst. Theory 2 (1968) 1–6. | DOI | MR | Zbl

[12] J. E. Hopcroft and J. D. Ullman, Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading, MA (1979). | MR

[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.

[14] P. Leupold and B. Nagy, 5′→ 3′ Watson-Crick automata with several runs. Fund. Inf. 104 (2010) 71–91. | MR | Zbl

[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. | Zbl

[16] A. Meduna and P. Zemek, Jumping finite automata.   Int. J. Found. Comput. Sci. 23 (2012) 1555–1578. | DOI | MR | Zbl

[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. | Zbl

[18] B. Nagy, A class of 2-head finite automata for linear languages. Triangle 8 (2012) 89–99.

[19] B. Nagy, On a hierarchy of 5′→ 3′ sensing Watson-Crick finite automata languages, J. Logic Comput. 23 (2013) 855–872. | DOI | MR | Zbl

[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. | DOI

[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.

[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. | DOI | MR | Zbl

[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. | DOI | MR | Zbl

[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. | Numdam | MR | Zbl

[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.

[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. | DOI | MR | Zbl

[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. | DOI | MR | Zbl

[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. | MR | Zbl

[29] B. Nagy and S. Parchami, On deterministic sensing 5′→ 3′ Watson-Crick finite automata: A full hierarchy in 2detlin. Acta Inf. DOI: (2020). | DOI | MR | Zbl

[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. | MR | Zbl

[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. | MR | Zbl

[32] Gh. Păun, G. Rozenberg and A. Salomaa, DNA Computing - New Computing Paradigms. Springer, Heidelberg (1998). | MR | Zbl

[33] A. L. Rosenberg, On multi-head finite automata. IBM J. Res. Dev. 10 (1966) 388–394. | DOI | MR | Zbl

[34] G. Rozenberg and A. Salomaa, Handbook of Formal Languages. Springer, Heidelberg (1997). | MR | Zbl

[35] M. Sipser, Introduction to the Theory of Computation. PWS Publishing Company, Boston, MA (1997). | Zbl