Top

Acta Informatica

Published in:

24-01-2022 | Original Article

A jumping \(5'\rightarrow 3'\) Watson–Crick finite automata model

Authors: Radim Kocman, Zbyněk Křivka, Alexander Meduna, Benedek Nagy

Published in: Acta Informatica | Issue 5/2022

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Jumping finite automata and sensing \(5'\rightarrow 3'\) Watson–Crick finite automata are finite-state models of computation which allow to process the input word not only in the strictly left-to-right manner. In this paper a new combined model of them is presented. The accepting power of the new model is studied and compared with the original models and also other well-known language families. Furthermore, the paper investigates changes in the accepting power when commonly studied restrictions from Watson–Crick finite automata, e.g., all states are final, are applied to this combined model. In the end, the paper presents a comprehensive hierarchy of all related language families.

previous article Interface Automata for Shared Memory

next article Index appearance record with preorders

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Beier, S., Holzer, M.: Decidability of right one-way jumping finite automata. In: DLT 2018, LNCS, vol. 11088, pp. 109–120 (2018). https://doi.org/10.1007/978-3-319-98654-8_9

Beier, S., Holzer, M., Kutrib, M.: Operational state complexity and decidability of jumping finite automata. In: DLT 2017, LNCS, vol. 10396, pp. 96–108 (2017). https://doi.org/10.1007/978-3-319-62809-7_6

Chigahara, H., Fazekas, S.Z., Yamamura, A.: One-way jumping finite automata. Int. J. Found. Comput. Sci. 27(03), 391–405 (2016). https://doi.org/10.1142/S0129054116400165MathSciNetCrossRefMATH

Fazekas, S.Z., Hoshi, K., Yamamura, A.: Enhancement of automata with jumping modes. In: Automata 2019, LNCS, vol. 11525, pp. 62–76 (2019). https://doi.org/10.1007/978-3-030-20981-0_5

Fazekas, S.Z., Yamamura, A.: On regular languages accepted by one-way jumping finite automata. In: Eighth Workshop on Non-classical Models of Automata and Applications (NCMA 2016) Short papers, pp. 7–14 (2016)

Fernau, H., Paramasivan, M., Schmid, M.L.: Jumping finite automata: characterizations and complexity. In: CIAA 2015, LNCS, vol. 9223, pp. 89–101. Springer (2015). https://doi.org/10.1007/978-3-319-22360-5_8

Fernau, H., Paramasivan, M., Schmid, M.L., Vorel, V.: Characterization and complexity results on jumping finite automata. Theor. Comput. Sci. 679, 31–52 (2017). https://doi.org/10.1016/j.tcs.2016.07.006MathSciNetCrossRefMATH

Kocman, R., Křivka, Z., Meduna, A.: On double-jumping finite automata. In: Eighth Workshop on Non-classical Models of Automata and Applications (NCMA 2016), OCG, vol. 321, pp. 195–210 (2016)

Kocman, R., Křivka, Z., Meduna, A.: On double-jumping finite automata and their closure properties. RAIRO Theor. Inf. Appl. 52(2–4), 185–199 (2018). https://doi.org/10.1051/ita/2018013MathSciNetCrossRefMATH

10.

Kocman, R., Meduna, A.: On parallel versions of jumping finite automata. In: SDOT 2015, AICS, vol. 511, pp. 142–149 (2016). https://doi.org/10.1007/978-3-319-46535-7_12

11.

Kocman, R., Nagy, B., Křivka, Z., Meduna, A.: A jumping \(5^{\prime }\rightarrow 3^{\prime }\) Watson–Crick finite automata model. In: Tenth Workshop on Non-classical Models of Automata and Applications (NCMA 2018), OCG, vol. 332, pp. 117–132 (2018)

12.

Kuske, D., Weigel, P.: The role of the complementarity relation in Watson–Crick automata and sticker systems. In: DLT 2004, LNCS, vol. 3340, pp. 272–283 (2005). https://doi.org/10.1007/978-3-540-30550-7_23

13.

Křivka, Z., Meduna, A.: Jumping grammars. Int. J. Found. Comput. Sci. 26(6), 709–731 (2015). https://doi.org/10.1142/S0129054115500409MathSciNetCrossRefMATH

14.

Madejski, G.: Jumping and pumping lemmas and their applications. In: Eighth Workshop on Non-classical Models of Automata and Applications (NCMA 2016) Short Papers, pp. 25–33 (2016)

15.

Mahalingam, K., Raghavan, R., Mishra, U.K.: Watson–Crick jumping finite automata. In: TAMC 2019, LNCS, vol. 11436, pp. 467–480. Springer (2019). https://doi.org/10.1007/978-3-030-14812-6_29

16.

Meduna, A.: Automata and Languages: Theory and Applications. Springer, London (2000)CrossRef

17.

Meduna, A., Soukup, O.: Jumping scattered context grammars. Fundam. Inf. 152(1), 51–86 (2017). https://doi.org/10.3233/FI-2017-1512MathSciNetCrossRefMATH

18.

Meduna, A., Soukup, O.: Modern Language Models and Computation: Theory with Applications. Springer, Berlin (2017). https://doi.org/10.1007/978-3-319-63100-4CrossRefMATH

19.

Meduna, A., Techet, J.: Scattered Context Grammars and Their Applications. WIT Press, Southampton (2010)MATH

20.

Meduna, A., Zemek, P.: Jumping finite automata. Int. J. Found. Comput. Sci. 23(7), 1555–1578 (2012). https://doi.org/10.1142/S0129054112500244MathSciNetCrossRefMATH

21.

Meduna, A., Zemek, P.: Regulated Grammars and Automata. Springer, Berlin (2014)CrossRef

22.

Nagy, B.: On \(5^{\prime }\rightarrow 3^{\prime }\) sensing Watson–Crick finite automata. In: The 13th International Meeting on DNA Computing (DNA13), pp. 327–336 (2007)

23.

Nagy, B.: On \(5^{\prime }\rightarrow 3^{\prime }\) sensing Watson–Crick finite automata. In: DNA 13, LNCS, vol. 4848, pp. 256–262 (2008). https://doi.org/10.1007/978-3-540-77962-9_27

24.

Nagy, B.: \(5^{\prime }\rightarrow 3^{\prime }\) sensing Watson–Crick finite automata. In: Fung, G. (ed.) Sequence and Genome Analysis II–Methods and Applications, pp. 39–56. iConcept Press, Hong Kong (2010)

25.

Nagy, B.: On a hierarchy of \(5^{\prime }\rightarrow 3^{\prime }\) sensing Watson–Crick finite automata languages. J. Log. Comput. 23(4), 855–872 (2013). https://doi.org/10.1093/logcom/exr049MathSciNetCrossRefMATH

26.

Nagy, B., Kovács, Z.: On simple \(5^{\prime }\rightarrow 3^{\prime }\) sensing Watson–Crick finite-state transducers. In: Eleventh Workshop on Non-classical Models of Automata and Applications (NCMA 2019), pp. 155–170 (2019)

27.

Nagy, B., Otto, F.: Two-head finite-state acceptors with translucent letters. In: SOFSEM 2019, LNCS, vol. 11376, pp. 406–418 (2019). https://doi.org/10.1007/978-3-030-10801-4_32

28.

Nagy, B., Otto, F.: Linear automata with translucent letters and linear context-free trace languages. RAIRO Theor. Informatics Appl. 54, 3 (2020). https://doi.org/10.1051/ita/2020002

29.

Nagy, B., Parchami, S.: On deterministic sensing \(5^{\prime }\rightarrow 3^{\prime }\) Watson–Crick finite automata: a full hierarchy in 2detLIN. Acta Inform. 58(3), 153–175 (2021). https://doi.org/10.1007/s00236-019-00362-6

30.

Nagy, B., Parchami, S., Mir-Mohammad-Sadeghi, H.: A new sensing \(5^{\prime }\rightarrow 3^{\prime }\) Watson–Crick automata concept. In: AFL 2017, EPTCS, vol. 252, pp. 195–204 (2017). https://doi.org/10.4204/EPTCS.252.19

31.

Parchami, S., Nagy, B.: Deterministic sensing \(5^{\prime }\rightarrow 3^{\prime }\) Watson–Crick automata without sensing parameter. In: UCNC 2018, LNCS, vol. 10876, pp. 173–187 (2018). https://doi.org/10.1007/978-3-319-92435-9_13

32.

Paun, G., Rozenberg, G., Salomaa, A.: DNA Computing: New Computing Paradigms. Springer, Berlin Heidelberg (1998)CrossRef

33.

Rozenberg, G., Salomaa, A.: Handbook of Formal Languages, Linear Modeling: Background and Application, vol. 2. Springer, Berlin (1997)CrossRef

34.

Vorel, V.: On basic properties of jumping finite automata. Int. J. Found. Comput. Sci. 29(1), 1–15 (2018). https://doi.org/10.1142/S0129054118500016MathSciNetCrossRefMATH

35.

Wood, D.: Theory of Computation: A Primer. Addison-Wesley, Boston (1987)

Title: A jumping Watson–Crick finite automata model
Authors: Radim Kocman
Zbyněk Křivka
Alexander Meduna
Benedek Nagy
Publication date: 24-01-2022
Publisher: Springer Berlin Heidelberg
Published in: Acta Informatica / Issue 5/2022
Print ISSN: 0001-5903
Electronic ISSN: 1432-0525
DOI: https://doi.org/10.1007/s00236-021-00413-x

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 5/2022

Improved complement for two-way alternating automata

Correction to: Reactive synthesis without regret

Index appearance record with preorders

Interface Automata for Shared Memory

Premium Partner