The present paper modifies and studies jumping finite automata so they always perform two simultaneous jumps according to the same rule. For either of the two simultaneous jumps, it considers three natural directions – (1) to the left, (2) to the right, and (3) in either direction. According to this jumping-direction three-part classification, the paper investigates the mutual relation between the language families resulting from jumping finite automata performing the jumps in these ways and the families of regular, linear, context-free, and context-sensitive languages. It demonstrates that most of these language families are pairwise incomparable. In addition, many closure and non-closure properties of the resulting language families are established.
DOI : 10.1051/ita/2018013
Mots clés : Discontinuous and parallel tape reading, general jumping finite automata, even-length languages, left and right jumps
@article{ITA_2018__52_2-3-4_185_0,
author = {Kocman, Radim and K\v{r}ivka, Zbyn\v{e}k and Meduna, Alexander},
editor = {Bordihn, Henning and Nagy, Benedek and Vaszil, Gy\"orgy},
title = {On double-jumping finite automata and their closure properties},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {185--199},
publisher = {EDP-Sciences},
volume = {52},
number = {2-3-4},
year = {2018},
doi = {10.1051/ita/2018013},
mrnumber = {3915307},
zbl = {1423.68258},
language = {en},
url = {http://archive.numdam.org/articles/10.1051/ita/2018013/}
}
TY - JOUR AU - Kocman, Radim AU - Křivka, Zbyněk AU - Meduna, Alexander ED - Bordihn, Henning ED - Nagy, Benedek ED - Vaszil, György TI - On double-jumping finite automata and their closure properties JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2018 SP - 185 EP - 199 VL - 52 IS - 2-3-4 PB - EDP-Sciences UR - http://archive.numdam.org/articles/10.1051/ita/2018013/ DO - 10.1051/ita/2018013 LA - en ID - ITA_2018__52_2-3-4_185_0 ER -
%0 Journal Article %A Kocman, Radim %A Křivka, Zbyněk %A Meduna, Alexander %E Bordihn, Henning %E Nagy, Benedek %E Vaszil, György %T On double-jumping finite automata and their closure properties %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2018 %P 185-199 %V 52 %N 2-3-4 %I EDP-Sciences %U http://archive.numdam.org/articles/10.1051/ita/2018013/ %R 10.1051/ita/2018013 %G en %F ITA_2018__52_2-3-4_185_0
Kocman, Radim; Křivka, Zbyněk; Meduna, Alexander. On double-jumping finite automata and their closure properties. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 52 (2018) no. 2-3-4, pp. 185-199. doi : 10.1051/ita/2018013. http://archive.numdam.org/articles/10.1051/ita/2018013/
[1] , and , One-way jumping finite automata, in The 77th Nat. Convention of IPSJ. (2015) | MR
[2] , , and , Characterization and complexity results on jumping finite automata. Theor. Comput. Sci. 679 (2017) 31–52 | DOI | MR | Zbl
[3] and , On parallel versions of jumping finite automata, in Proc. ofthe 2015 Federated Conference on Software Development and Object Technologies (SDOT 2015). Vol. 511 of Advances in Intelligent Systems and Computing. Springer, Cham 2016 142–149
[4] , , and , A jumping 5′→ 3′ watson-crick finite automata model, in 10th Workshop on Non-Classical Models of Automata and Applications (NCMA 2018), vol. 332. OCG books@ocg.at (2018) 117–132
[5] and , Jumping grammars. Int. J. Found. Comput. Sci. 26 (2015) 709–731 | DOI | MR | Zbl
[6] , Automata and Languages: Theory and Applications Springer, London (2000) | DOI | MR | Zbl
[7] and , Jumping scattered context grammars. Fundam. Inf. 152 (2017) 51–86 | MR | Zbl
[8] and , Jumping finite automata. Int. J. Found. Comput. Sci. 23 (2012) 1555–1578 | DOI | MR | Zbl
[9] , On 5′→ 3′ sensing watson-crick finite automata, in DNA Computing: 13th International Meeting on DNA Computing (DNA13). Vol. 4848 of Lect. Notes Sci. Springer, Berlin, Heidelberg (2008) 256–262 | DOI | Zbl
[10] , 5′→ 3′ sensing watson-crick finite automata, in Sequence and Genome Analysis II – Methods and Applications, edited by . iConcept
[11] , A class of 2-head finite automata for linear languages. Triangle 8 (Lang.: Math. Approaches) (2012) 89–99
[12] , On a hierarchy of 5′→ 3′ sensing watson-crick finite automata languages. J. Logic Comput. 23 (2013) 855–872 | DOI | MR | Zbl
[13] and , Handbook of Formal Languages. Vol. 2 of Linear Modeling: Background and Application. Springer-Verlag, Berlin, Heidelberg (1997) | MR | Zbl
[14] , Two results on discontinuous input processing, in Descriptional Complexity of Formal Systems (DCFS 2016). Vol. 9777of Lect. Notes Sci. Springer, Cham (2016) 205–216 | DOI | MR
[15] , On basic properties of jumping finite automata. Int. J. Found. Comput. Sci. 29 (2018) 1–15 | DOI | MR | Zbl
[16] , Theory of Computation: A Primer. Addison-Wesley, Boston (1987) | Zbl
Cité par Sources :
