Geodesic
Multi-island finite automata and their even computation
Kybernetika, Tome 57 (2021) no. 5, pp. 856-877
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

This paper discusses $n$-island finite automata whose transition graphs can be expressed as $n$-member sequences of islands $i_1, i_2, \dots , i_n$, where there is a bridge leaving $i_j$ and entering $i_{j+1}$ for each $1 \leq j \leq n - 1$. It concentrates its attention on even computation defined as any sequence of moves during which these automata make the same number of moves in each of the islands. Under the assumption that these automata work only in an evenly computational way, the paper proves its main result stating that $n$-island finite automata and Rosebrugh-Wood $n$-parallel right-linear grammars are equivalent. Then, making use of this main result, it demonstrates that under this assumption, the language family defined by $n$-island finite automata is properly contained in that defined by $(n+1)$-island finite automata for all $n \geq 1$. The paper also points out that this infinite hierarchy occurs between the family of regular languages and that of context-sensitive languages. Open questions are formulated in the conclusion.
This paper discusses $n$-island finite automata whose transition graphs can be expressed as $n$-member sequences of islands $i_1, i_2, \dots , i_n$, where there is a bridge leaving $i_j$ and entering $i_{j+1}$ for each $1 \leq j \leq n - 1$. It concentrates its attention on even computation defined as any sequence of moves during which these automata make the same number of moves in each of the islands. Under the assumption that these automata work only in an evenly computational way, the paper proves its main result stating that $n$-island finite automata and Rosebrugh-Wood $n$-parallel right-linear grammars are equivalent. Then, making use of this main result, it demonstrates that under this assumption, the language family defined by $n$-island finite automata is properly contained in that defined by $(n+1)$-island finite automata for all $n \geq 1$. The paper also points out that this infinite hierarchy occurs between the family of regular languages and that of context-sensitive languages. Open questions are formulated in the conclusion.
DOI : 10.14736/kyb-2021-5-0856
Classification : 68Q10, 68Q42, 68Q45
Keywords: finite automata; graph-based decomposition; regulated computation; infinite hierarchies of language families 
@article{10_14736_kyb_2021_5_0856,
     author = {Kol\'a\v{r}, Du\v{s}an and Meduna, Alexander and Tomko, Martin},
     title = {Multi-island finite automata and their even computation},
     journal = {Kybernetika},
     pages = {856--877},
     year = {2021},
     volume = {57},
     number = {5},
     doi = {10.14736/kyb-2021-5-0856},
     mrnumber = {4363241},
     zbl = {07478644},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.14736/kyb-2021-5-0856/}
}
TY  - JOUR
AU  - Kolář, Dušan
AU  - Meduna, Alexander
AU  - Tomko, Martin
TI  - Multi-island finite automata and their even computation
JO  - Kybernetika
PY  - 2021
SP  - 856
EP  - 877
VL  - 57
IS  - 5
UR  - http://geodesic.mathdoc.fr/articles/10.14736/kyb-2021-5-0856/
DO  - 10.14736/kyb-2021-5-0856
LA  - en
ID  - 10_14736_kyb_2021_5_0856
ER  - 
%0 Journal Article
%A Kolář, Dušan
%A Meduna, Alexander
%A Tomko, Martin
%T Multi-island finite automata and their even computation
%J Kybernetika
%D 2021
%P 856-877
%V 57
%N 5
%U http://geodesic.mathdoc.fr/articles/10.14736/kyb-2021-5-0856/
%R 10.14736/kyb-2021-5-0856
%G en
%F 10_14736_kyb_2021_5_0856
Kolář, Dušan; Meduna, Alexander; Tomko, Martin. Multi-island finite automata and their even computation. Kybernetika, Tome 57 (2021) no. 5, pp. 856-877. doi: 10.14736/kyb-2021-5-0856

[1] Bavel, Z.: Structure and transition-preserving functions of finite automata. J. ACM 15 (1968), 1, 135-158. | DOI

[2] Han, X., Chen, Z., Liu, Z., Zhang, Q.: The detection and stabilisation of limit cycle for deterministic finite automata. Int. J. Control 91 (2018), 4, 874-886. | DOI

[3] Hopcroft, J. E., Ullman, J. D.: Introduction to Automata Theory, Languages and Computation. First edition. Addison-Wesley Publishing Company, 1979.

[4] Meduna, A.: Formal Languages and Computation: Models and Their Applications. First edition. Auerbach Publications, 2014.

[5] Meduna, A., Masopust, T.: Self-regulating finite automata. Acta Cybernetica 18 (2007), 1, 135-153.

[6] Meduna, A., Zemek, P.: Jumping finite automata. Int. J. Found. Comput. Sci. 23 (2012), 1555-1578. | DOI

[7] Meduna, A., Zemek, P.: Regulated Grammars and Automata. Springer, 2014.

[8] Rosebrugh, R. D., Wood, D.: Restricted parallelism and right linear grammars. Util. Math. 7 (1975), 151-186.

[9] Schönecker, R.: Automaty s několika čistými zásobníky. Master's Thesis, University of Technology, Faculty of Information Technology, Brno 2005.

[10] Sin'ya, R., Matsuzaki, K., Sassa, M.: Simultaneous finite automata: An efficient data-parallel model for regular expression matching. In: 42nd International Conference on Parallel Processing 2013, pp. 220-229.

[11] Skobelev, V. V., Skobelev, V. G.: Finite automata over algebraic structures: models and some methods of analysis. Computer Sci. J. Moldova 23 (2015).

[12] Verma, A., Loura, A.: A novel algorithm for the conversion of parallel regular expressions to non-deterministic finite automata. Appl. Math. Inform. Sci. 8 (2014), 95-105. | DOI

[13] Yli-Jyrä, A., Koskenniemi, K.: Compiling contextual restrictions on strings into finite-state automata. In: Proc, Eindhoven FASTAR Days 2004.

Cité par Sources :