Multi-Island Finite Automata and Their Even Computations

• https://www.kybernetika.cz/content/2021/5/856

finite automata, graph-based decomposition, regulated computation, infinite hierarchies of language families

Tento článek pojednává o n-ostrovních konečných automatech, jejichž přechodové grafy lze vyjádřit jako n-členné posloupnosti ostrovů i1, i2, ..., in, kde existuje most vystupující z ij a vstupující do i(j+1) pro každé 1 <= j <= n - 1. Svou pozornost soustřeďuje na vyrovnaný výpočet definovaný jako libovolná posloupnost tahů, během níž tyto automaty provedou stejný počet tahů v každém z ostrovů. Za předpokladu, že tyto automaty pracují pouze s vyrovnanými výpočty, dokazuje svůj hlavní výsledek, který říká, že n-ostrovní konečné automaty a Rosebrugh-Woodovy n-paralelní pravé lineární gramatiky jsou ekvivalentní. S využitím tohoto hlavního výsledku pak ukazuje, že za tohoto předpokladu je rodina jazyků definovaná n-ostrovními konečnými automaty ostrou podtřídou rodiny definované (n+1)-ostrovními konečnými automaty pro všechna n >= 1. Článek také poukazuje na to, že tato nekonečná hierarchie se vyskytuje mezi rodinou regulárních jazyků a rodinou kontextových jazyků. V závěru jsou formulovány otevřené otázky.