Preface

Complexities of One-way Jumping Finite Automata

Words are an integral part of computer science, and their classical sequential processing is reflected by machines accepting various classes of languages of the Chomsky hierarchy. However, since already the 70's there has been keen interest, when considering words or languages of words, on presentations of these sequences in the form of nonconsecutive symbols, i.e., [17],[13]. Within last thirty years, non-classical models of automata have captured more and more attention, with the introduction of several such models, i.e., restarting automata [11], jumping automata [14], input revolving automata [4] and automata with translucent letters [16].

One-way jumping finite automata (OWJFA) were introduced [5] as a non-sequential processing model of deterministic finite automata (DFA) that is more restrictive, with respect to the extra operations, than the general jumping automata introduced in [14]. The former two coincide in fact in the case of complete DFAs, since the extra capabilities of the OWJFA stem precisely from the missing transitions on any state in the classical DFA. At the same time, due to their restrictive definition of `jumping' that is only possible in the previously described case of a sequential read, they represent a natural restriction of the model defined in [14]. To this end, they also represent a restriction of the (right) revolving automata [4], where the revolving operation maintains the state it starts in (see [5]).

In a nutshell, OWJFAs are specified in exactly the same way as DFAs while allowing partial transition functions, see Fig.1. The only behavioural difference is when arriving at a tape symbol for which the current state has no defined outgoing transition. In the classical case such inputs are rejected, in the jumping mode these are irrelevant since we can jump anywhere on the tape, while in the revolving case the only possibility is for a revolving operation to be applied, should one such operation be specified for the current state and symbol. In the one-way jumping mode these symbols are skipped temporarily, but must be processed later, i.e., the relative order of the skipped symbols is maintained, with the automaton moving back to the beginning after each pass (called sweeps, see Fig.2), and seeing only the symbols previously skipped. Therefore one can also view this model as a type of DFA with a circular input tape, always jumping clockwise, reading and consuming the nearest letter for which it has a defined transition from the current state.

While [5], [1] investigate various properties of the accepted language class, the decidability questions that arise from these have been settled [2]. Considering the one-way jumping processing mode, authors also investigated more powerful machines corresponding to the classical models, i.e., nondeterministic finite automata [3], [6], two-way finite automata [7], pushdown automata and linear bounded automata [6]. While the language classes defined by the models have no nontrivial closure properties under usual language operations, the accepting power and decidability issues raised some intriguing problems.

The above machine models are more powerful when the one-way jumping mode is present in all cases, except for linear bounded automata. While this is rather natural and showing it follows classical techniques, the challenge was to figure just how powerful the new processing mode is, even in the simplest of cases, when DFAs are considered. Since a complete transition function renders a DFA, i.e., no symbols are skipped, the class of languages accepted by DFA in one-way jumping mode trivially includes all regular languages. The language class defined by OWJFAs is incomparable with the context-free class, but included in the context-sensitive class and in DTIME($n^2$) [1]. The separation results make use of combinations of a handful of regular languages together with a very simple type of non-regular languages which contain words having letter counts in a certain ratio, e.g., the frequently used $ L_{ab} = \{ w \in \{a,b\}^* \mid w $ contains as many $ a $'s as $ b $'s$ \} $ accepted by the machine $ \mathcal{A} $ in Fig.1. While this was enough to establish virtually all separations of interest, it left a significant gap in our understanding of the model when it comes to acceptance of non-regular languages that do not establish linear relationships among letter counts.

Moreover, of high interest, in most cases, is the study of the effect that the non-sequential way of processing inputs has on the various complexity aspects. In terms of computation complexity theory, [9] considers the impact of the needed jumps or sweeps when looking at the computation of a machine. The aim was to arrive at a decision procedure on whether a given machine accepts a regular language. Part of this is the introduction of sweep complexity, a measure for the number of times, in the worst case, that such machines have to return to the beginning of their input after having skipped some of the symbols. The consideration was that sweep count can represent a measure of non-regular resources used by a machine, posing the natural question of how much of this resource is needed to be able to accept non-regular languages? The idea of sweep complexity appears in other contexts, too, and an interesting and thorough investigation of a similar flavour established infinite hierarchies in terms of sweep count for iterated uniform finite transducers [12]. Even more recently, the notion of jump complexity appears in the context of automata with translucent letters [15].

It was known that constant sweep complexity does not increase the accepting power of the machines [10], and in [8] the authors refute the conjecture that, in fact, any automaton with higher than constant sweep complexity accepts a non-regular language. Moreover, the same work shows that, in general, the sweep complexity of an automaton does not distinguish between accepting regular and non-regular languages, and provides a separation result for asymptotic classes defined by this complexity measure. Thus language classes defined through asymptotic complexity form a true hierarchy, i.e., there are languages which can be accepted by a machine with $ \mathcal{O} (f(n)) $ sweep complexity but not by any with $ o(f(n)) $ sweep complexity, for various functions $ f(n) $.

One of the main benefits that OWJFAs seem to exhibit, in comparison with similar classical ones, is the size of the machine when considering the accepted languages. While already from [5] it was established that there is no unique minimal machine describing a certain language, when talking about regular languages, we were able to show some descriptional complexity results with respect to these machines. In particular, we showed that while there might still be a, tight, exponential blow-up in the number of states needed to represent an NFA with the help of an OWJFA, contrary to the classical case, there are situations where such an exponential blow-up exists in the other direction as well, even for 3-letter alphabets. For the deterministic machines, since OWJFAs are presented in the form of DFAs, only one direction is meaningful, and we were able to show that we get an exponential blow-up when for a regular language accepted by OWJFAs we want a description in the form of a DFA.

Based on all of the previous discussion there are several questions that arise when considering models with such operations. These range from the analysis of the hierarchy in the case of computational complexity with respect to the number of sweeps that words from a language require, to the a descriptional complexity analysis in the case of nondeteministic machines.

References

1. Simon Beier & Markus Holzer (2019): Properties of right one-way jumping finite automata. Theoretical Computer Science, doi:10.1016/j.tcs.2019.03.044.
2. Simon Beier & Markus Holzer (2020): Decidability of Right One-Way Jumping Finite Automata. International Journal of Foundations of Computer Science 31(06), pp. 805–825, doi:10.1142/S0129054120410063.
3. Simon Beier & Markus Holzer (2022): Nondeterministic right one-way jumping finite automata. Information and Computation 284, p. 104687, doi:10.1016/j.ic.2021.104687.
4. Henning Bordihn & Markus Holzer & Martin Kutrib (2005): Revolving-Input Finite Automata. In DLT 2005. LNCS 3572, pp. 168–179 doi:10.1007/11505877\_15.
5. Hiroyuki Chigahara & Szilard Zsolt Fazekas & Akihiro Yamamura (2016): One-Way Jumping Finite Automata. International Journal of Foundations of Computer Science 27(3), pp. 391–405, doi:10.1142/S0129054116400165.
6. Szilard Zsolt Fazekas & Kaito Hoshi & Akihiro Yamamura (2021): The effect of jumping modes on various automata models. Natural Computing, doi:10.1007/s11047-021-09844-4.
7. Szilard Zsolt Fazekas & Kaito Hoshi & Akihiro Yamamura (2021): Two-way deterministic automata with jumping mode. Theoretical Computer Science 864, pp. 92–102, doi:10.1016/j.tcs.2021.02.030.
8. Szilard Zsolt Fazekas & Robert Mercas (2023): Sweep Complexity Revisited. In CIAA 2023, LNCS 14151 pp. 116–127, doi:10.1007/978-3-031-40247-0_8.
9. Szilard Zsolt Fazekas & Robert Mercas & Olivia Wu (2022): Complexities for Jumps and Sweeps. Journal of Automata, Languages and Combinatorics 27(1-3), pp. 131–149, doi:10.25596/jalc-2022-131.
10. Szilard Zsolt Fazekas & Akihiro Yamamura (2016): On regular languages accepted by one-way jumping finite automata. In: NCMA 2016 (short papers), pp. 7–14.
11. Petr Jancar & Frantisek Mraz & Martin Platek & Jorg Vogel (1995): Restarting automata. In Fundamentals of Computation Theory, pp. 283–292, doi:10.1007/3-540-60249-6_60.
12. Martin Kutrib & Andreas Malcher & Carlo Mereghetti & Beatrice Palano (2022): Descriptional complexity of iterated uniform finite-state transducers. Information and Computation 284, p. 104691, doi:10.1016/j.ic.2021.104691.
13. David Maier (1978): The Complexity of Some Problems on Subsequences and Supersequences. Journal of the ACM 25(2), pp. 322–336, doi:10.1145/322063.322075.
14. Alexander Meduna & Petr Zemek (2012): Jumping Finite Automata. International Journal of Foundations of Computer Science 23(7), pp. 1555–1578, doi:10.1142/S0129054112500244.
15. Victor Mitrana & Andrei Paun & Mihaela Paun & Jose-Ramon Sanchez-Couso (2024): Jump complexity of finite automata with translucent letters. Theoretical Computer Science 992, p. 114450, doi:10.1016/J.TCS.2024.114450.
16. Benedek Nagy & Friedrich Otto (2011): Finite-state acceptors with translucent letters. In ICAART 2011, pp. 3–13.
17. Imre Simon (1972): Hierarchies of events with dot-depth one Ph.D. thesis, University of Waterloo.

---

Fig. 1: OWJFA $ \mathcal{A} $ accepting the language $ L ( \mathcal{A} ) = \{ w \in \{ a, b \}^* \mid |w|_a = |w|_b \}$

Fig. 2: Computation for $ aaaabbabbb $ by OWJFA $\mathcal{A}$