Multi-island finite automata and their even computation

Dušan Kolář; Alexander Meduna; Martin Tomko

Kybernetika (2021)

  • Volume: 57, Issue: 5, page 856-877
  • ISSN: 0023-5954

Abstract

top
This paper discusses n -island finite automata whose transition graphs can be expressed as n -member sequences of islands i 1 , i 2 , ⋯ , i n , where there is a bridge leaving i j and entering i j + 1 for each 1 ≤ j ≤ 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 ≥ 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.

How to cite

top

Kolář, Dušan, Meduna, Alexander, and Tomko, Martin. "Multi-island finite automata and their even computation." Kybernetika 57.5 (2021): 856-877. <http://eudml.org/doc/297518>.

@article{Kolář2021,
abstract = {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 \le j \le 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 \ge 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.},
author = {Kolář, Dušan, Meduna, Alexander, Tomko, Martin},
journal = {Kybernetika},
keywords = {finite automata; graph-based decomposition; regulated computation; infinite hierarchies of language families},
language = {eng},
number = {5},
pages = {856-877},
publisher = {Institute of Information Theory and Automation AS CR},
title = {Multi-island finite automata and their even computation},
url = {http://eudml.org/doc/297518},
volume = {57},
year = {2021},
}

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
PB - Institute of Information Theory and Automation AS CR
VL - 57
IS - 5
SP - 856
EP - 877
AB - 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 \le j \le 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 \ge 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.
LA - eng
KW - finite automata; graph-based decomposition; regulated computation; infinite hierarchies of language families
UR - http://eudml.org/doc/297518
ER -

References

top
  1. Bavel, Z., , J. ACM 15 (1968), 1, 135-158. DOI
  2. Han, X., Chen, Z., Liu, Z., Zhang, Q., , 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., , 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., , 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. 

NotesEmbed ?

top

You must be logged in to post comments.