Article
Full entry |
PDF
(0.4 MB)
Feedback
PDF
(0.4 MB)
Feedback
Keywords:
finite automata; graph-based decomposition; regulated computation; infinite hierarchies of language families
finite automata; graph-based decomposition; regulated computation; infinite hierarchies of language families
Summary:
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.
References:
[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.
Search
Partner of
