nach oben

Natural Computing

Erschienen in:

09.03.2021

The effect of jumping modes on various automata models

verfasst von: Szilárd Zsolt Fazekas, Kaito Hoshi, Akihiro Yamamura

Erschienen in: Natural Computing | Ausgabe 1/2022

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Recently, new types of non-sequential machine models have been introduced and studied, such as jumping automata and one-way jumping automata. We study the abilities and limitations of (finite, pushdown and linear bounded) automata with these 2 jumping modes of tape heads with respect to how they affect the class of accepted languages. We provide adapted versions of pumping lemmas and other methods to determine whether a language is accepted by a machine with jumping mode. Using these methods we establish the inclusion or incomparability relationships among the classes of languages defined by the new machines and their classical counterparts. We also study the closure properties of the resulting language classes and show that under most fundamental language operations, these classes are not closed.

Vorheriger Artikel Iterative arrays with finite inter-cell communication

Nächster Artikel On the minimal number of generators of endomorphism monoids of full shifts

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Beier S, Holzer M (2018) Decidability of right one-way jumping finite automata. In: Hoshi M, Seki S (eds.) Developments in Language Theory - 22nd International Conference, DLT 2018, Tokyo, Japan, September 10-14, 2018, Proceedings, Lecture Notes in Computer Science 11088: 109–120. Springer. https://doi.org/10.1007/978-3-319-98654-8_9

Beier S, Holzer M (2019) Nondeterministic right one-way jumping finite automata (extended abstract). In: Hospodár M, Jirásková G, Konstantinidis S (eds) Descriptional complexity of formal systems. Springer, Cham, pp 74–85CrossRef

Beier S, Holzer M (2019) Properties of right one-way jumping finite automata. Theor Comput Sci 798:78–94MathSciNetCrossRef

Beier S, Holzer M, Kutrib M (2017) Operational state complexity and decidability of jumping finite automata. In: É. Charlier, J. Leroy, M. Rigo (eds.) Developments in Language Theory - 21st International Conference, DLT 2017, Liège, Belgium, August 7-11, 2017, Proceedings, Lecture Notes in Computer Science, vol. 10396, pp. 96–108. Springer. https://doi.org/10.1007/978-3-319-62809-7_6

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

Fazekas SZ, Hoshi K, Yamamura A (2019) Enhancement of automata with jumping modes. In: Castillo-Ramirez A, de Oliveira PPB (eds) Cellular automata and discrete complex systems. Springer, Cham, pp 62–76CrossRef

Fazekas SZ, Hoshi K, Yamamura A (2020) Two-way jumping automata. In: M. Li (ed.) Frontiers in Algorithmics - 14th International Workshop, FAW 2020, Haikou, China, October 19-21, 2020, Proceedings, Lecture Notes in Computer Science, vol. 12340, pp. 108–120. Springer. https://doi.org/10.1007/978-3-030-59901-0_10

Fazekas SZ, Yamamura A (2016) On regular languages accepted by one-way jumping finite automata. In: 8th NCMA, Debrecen, Hungary, Short Papers, pp. 7–14. sterreichische Computer Gesellschaft

Fernau H, Paramasivan M, Schmid ML (2015) Jumping finite automata: Characterizations and complexity. In: Drewes F (ed.) Implementation and Application of Automata - 20th International Conference, CIAA 2015, Umeå, Sweden, August 18-21, 2015, Proceedings, Lecture Notes in Computer Science, vol. 9223, pp. 89–101. Springer (2015). https://doi.org/10.1007/978-3-319-22360-5_8

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

Hopcroft JE, Ullman JD (1979) Introduction to Automata Theory. Addison-Wesley, Languages and Computation

Kocman R, Meduna A (2016) On parallel versions of jumping finite automata. In: Janech J, Kostolny J, Gratkowski T (eds) Advances in Intelligent Systems and Computing, Springer, Berlin, pp. 142–149. https://doi.org/10.1007/978-3-319-46535-7_12

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

Latteux M (1979) Cônes rationnels commutatifs. J Comput Syst Sci 18(3):307–333. https://doi.org/10.1016/0022-0000(79)90039-4MathSciNetCrossRefMATH

Madejski G (2016) 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

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

Meduna A, Zemek P (2014) Regulated grammars and automata. Springer. https://doi.org/10.1007/978-1-4939-0369-6

Parikh R (1966) On context-free languages. J. ACM 13(4):570–581. https://doi.org/10.1145/321356.321364CrossRefMATH

Sipser M (2006) Introduction to the Theory of Computation, second edn. Course Technology

Yu S (1989) A pumping lemma for deterministic context-free languages. Inf Process Lett 31(1):47–51. https://doi.org/10.1016/0020-0190(89)90108-7MathSciNetCrossRefMATH

Titel: The effect of jumping modes on various automata models
verfasst von: Szilárd Zsolt Fazekas
Kaito Hoshi
Akihiro Yamamura
Publikationsdatum: 09.03.2021
Verlag: Springer Netherlands
Erschienen in: Natural Computing / Ausgabe 1/2022
Print ISSN: 1567-7818
Elektronische ISSN: 1572-9796
DOI: https://doi.org/10.1007/s11047-021-09844-4

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 1/2022

Computational graph pangenomics: a tutorial on data structures and their applications

Iterative arrays with self-verifying communication cell

On the minimal number of generators of endomorphism monoids of full shifts

Correction to: Complexity-theoretic aspects of expanding cellular automata

On the predictability of the abelian sandpile model

Complexity-theoretic aspects of expanding cellular automata