2-Head 2D Returning Finite Automata
Henning Fernau, Benedek Nagy, R. Jennifer Rose, Robinson Thamburaj, D. Gnanaraj Thomas · 2026
Read 2-Head 2D Returning Finite Automata by Henning Fernau, Benedek Nagy, R. Jennifer Rose, Robinson Thamburaj, D. Gnanaraj Thomas (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-26680.txt.
Introduction
Henning Fernau, Benedek Nagy, R. Jennifer Rose, Robinson Thamburaj, and D. Gnanaraj Thomas introduce two-head returning finite automata for picture languages. A picture language is a set of rectangular symbol arrays, like tiny images. A returning automaton rescans its input repeatedly. This family has two reading heads moving in opposite directions across the array.
The authors map where this family sits among known language classes. Its languages are incomparable with those of context-free matrix grammars, meaning neither family contains the other. They form a proper subset of the languages of returning pushdown automata, which have extra memory. A constrained variant forces both heads to step in synchrony. Its class sits strictly between ordinary returning automata and the two-head family. Closure properties for both families are also established.
Catalog record
| CREATOR | Henning Fernau, Benedek Nagy, R. Jennifer Rose, Robinson Thamburaj, D. Gnanaraj Thomas |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 53 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.26680
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
2-Head 2D Returning Finite Automata Henning Fernau, Benedek Nagy, R. Jennifer Rose, Robinson Thamburaj, D. Gnanaraj Thomas Abstract We introduce and study a family of two‑head finite automata called two‑head returning finite automata (2‑HRFA) operating on rectangular arrays of picture languages, in which both heads move in opposite directions. We show that the class of picture languages accepted by 2‑HRFA is incomparable with the class of languages generated by context‑free matrix grammars (CFMG), while it forms a proper subset of the class of languages accepted by returning pushdown automata (RPDA). In addition, we define a constrained variant, both‑head stepping two‑head returning finite automata (B2-HRFA), in which both heads are required to move in a synchronized, stepwise fashion. We prove that the class of languages accepted by returning finite automata (RFA) is a proper subset of the class of languages accepted by B2-HRFA, which in turn is a proper subset of the class of languages accepted by 2‑HRFA. Closure properties for both the families of languages accepted by 2‑HRFA and B2-HRFA are also investigated. 1 Introduction The study of multi-head automata has played an important role in the theory of computation for understanding the computing capabilities of finite state devices. The multi-head automata introduced by Rosenberg [ 20 ] extend the classical one-head model by equipping the automaton with several reading heads where each reading head can move only left to right and is independent of each other, resulting in a strict hierarchy of language classes. Two-head automata represent an important subclass of multi-head machines. Hromkovic studied two-head deterministic finite state automata [ 13 ] , establishing the fundamental results on their computational complexity and demonstrating that one-way two-head automata can recognize languages that are not recognized by single-head machines. 2-head models were studied by Loukonova [ 15 ] and by Nagy [ 16 ] for accepting the linear context-free languages. Deterministic variants accept a language class referred as 2detLIN, which is properly between the classes REG of regular and LIN of linear languages [ 18 ] . Here we consider these automata for processing 2-dimensional rectangular inputs. The theory of string recognizability by automata is generalized to two dimensions in [ 3 , 10 ] . For recognizing rectangular-shaped pictures (or arrays), returning finite automata (RFA) were introduced by Fernau et al. [ 7 ] as simpler finite-state devices, scanning rectangular pictures row by row, each row always from left to right. It was shown that the class of languages recognized by RFA is precisely the transpose of the class of languages generated by regular matrix grammars (RMG) introduced by Siromoney et al. much earlier [ 22 ] . Recently, Fernau et al. [ 6 ] introduced and studied returning pushdown automata (RPDA) which extend the model of returning finite automata by equipping them with a pushdown store. This combination of returning behavior and pushdown store increases the expressive power beyond that of RFA and also beyond transposes of context-free matrix languages as defined in [ 22 ] . In this paper, we introduce two‑head returning finite automata (2‑HRFA) for recognizing picture languages, in which the two heads scan a rectangular picture from opposite ends. 1 1 1 These automata are essentially different from the model introduced and studied in [ 4 , 5 ] , as the notion of an array differs. Specifically, the first head reads the picture from the top, moving left to right on each row, while the second head reads the picture from the bottom, moving right to left on each row and the automaton accepts the picture when the two heads meet. We compare the language‑theoretic properties of the classes of 2‑HRFA with returning finite automata (RFA), regular matrix grammars (RMG), context-free matrix grammars (CFMG), returning pushdown automata (RPDA), and the constrained variant of both‑head stepping two‑head returning finite automata (B2-HRFA). We show that 2‑HRFA recognizes a strictly larger class of languages than RFA and that the class of languages accepted by 2‑HRFA is incomparable with the classes generated by RMG and CFMG. Furthermore, we establish that the class of languages recognized by 2‑HRFA lies strictly within the class of languages accepted by RPDA, while the class of languages accepted by B2-HRFA forms an intermediate level between the classes of languages accepted by RFA and 2‑HRFA, thereby refining the hierarchy among the families of returning finite‑state and stack‑based models. 2 Preliminaries In this section, we recall some definitions related to picture languages, matrix grammars and two-head automata, returning finite automata and returning pushdown automata [ 6 , 7 , 10 , 11 , 14 , 17 ] . Let \Sigma be a finite alphabet. A string or a word over \Sigma is a finite sequence of symbols from \Sigma . The set of all non-empty strings over \Sigma is denoted by \Sigma^{+} and the empty string is \varepsilon ; \Sigma^{*}=\Sigma^{+}\cup\{\varepsilon\} . Further, let \mathbb{N} denote the set of positive integers. Definition 2.1 . A 2-Head Finite Automaton (2-HFA) in which the two heads read a word in opposite directions is defined as A=(Q,\Sigma,\delta,s,F) where Q is the finite set of states, \Sigma is the input alphabet, \delta:Q\times(\Sigma\cup\{\varepsilon\})\times(\Sigma\cup\{\varepsilon\})\rightarrow 2^{Q} is the transition function, s\in Q is the start state, F\subseteq Q specifies the final states. Suppose a_{1}a_{2}\cdots a_{n} is an input word. The 2-HFA starts the computation in the initial state s reading either a pair of symbols (a_{1},a_{n}) where the first head reads the symbol a_{1} from the left end and the second head reads the symbol a_{n} from right end and enters the next state according to the transition function \delta or reading the pair (a_{1},\varepsilon) when only the first head moves or the pair (\varepsilon,a_{n}) when only the second head moves. (We do not allow transitions by the pair (\varepsilon,\varepsilon) as such transitions can be eliminated without affecting the class of accepted languages.) The 2-HFA continues to read the remaining symbols of the input in a similar manner. An input word is accepted by a 2-HFA if every letter of the word is read by one of the heads (i.e., the heads meet) and the automaton is in a final state. In transitions, a pair of symbols (a,b)\in\Sigma^{2} is assigned to the arrows between two states which means that when moving from one state to another one, the first head reads the symbol a , the second head reads b and both heads step forward. Example 2.1 . The language L=\{a^{n}b^{n}\mid n>1\} is recognized by the 2-HFA given in Figure 1 . Here, the two heads meet at s_{2} to accept a word of the form a^{n}b^{n} . s s_{1} s_{2} (a,b) (a,b) (a,b) Figure 1 : A 2-head finite automaton that accepts the language a^{n}b^{n} with n>1 . It is well-known that linear languages can be characterized by linear context-free grammars as well as by pushdown automata whose pushdown store makes only one turn, i.e., it only once switches between a pushing and a popping phase. Theorem 2.1 . A language is linear if and only if it is accepted by a 2-head finite automaton if and only if it is accepted by a one-turn pushdown automaton. The deterministic version of a 2-HFA is weaker than the non-deterministic version as can