pith. sign in

arxiv: 2606.26680 · v1 · pith:FOUPM4XYnew · submitted 2026-06-25 · 💻 cs.FL

2-Head 2D Returning Finite Automata

Henning Fernau (Universit\"at Trier , Germany) , Benedek Nagy (Eszterhazy Karoly Catholic University , Eger , Hungary) , R. Jennifer Rose (Madras Christian College) , Robinson Thamburaj (Madras Christian College) , D. Gnanaraj Thomas (Madras Christian College) This is my paper

Pith reviewed 2026-06-26 02:06 UTC · model grok-4.3

classification 💻 cs.FL
keywords two-head finite automatapicture languagesreturning automatacontext-free matrix grammarsreturning pushdown automatatwo-dimensional languagesautomata hierarchyclosure properties
0
0 comments X

The pith

Two-head returning finite automata accept picture languages incomparable to context-free matrix grammars but properly contained in those of returning pushdown automata.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper defines two-head returning finite automata that scan rectangular arrays with the two heads moving in opposite directions and returning to start positions after each sweep. It proves that the resulting class of picture languages is incomparable with the languages generated by context-free matrix grammars yet forms a proper subset of the languages accepted by returning pushdown automata. A synchronized variant is introduced in which both heads advance in lockstep, and this variant is shown to sit strictly between ordinary returning finite automata and the unrestricted two-head model. Closure properties under several array operations are also established for both new families.

Core claim

The authors introduce 2-HRFA in which two heads move oppositely across rectangular arrays and return after each pass; they establish that the accepted languages are incomparable with CFMG languages while forming a proper subset of RPDA languages. They further define B2-HRFA with synchronized stepwise head motion and prove the chain RFA ⊂ B2-HRFA ⊂ 2-HRFA, together with selected closure properties.

What carries the argument

Two-head returning finite automata (2-HRFA) whose heads traverse rectangular arrays in opposite directions and return after each sweep, together with the synchronized B2-HRFA restriction.

If this is right

  • The languages accepted by 2-HRFA properly contain those of B2-HRFA, which properly contain those of ordinary returning finite automata.
  • The 2-HRFA class is strictly weaker than returning pushdown automata on rectangular arrays.
  • There exist picture languages accepted by 2-HRFA that are not generated by any context-free matrix grammar, and vice versa.
  • Both 2-HRFA and B2-HRFA families are closed under certain array operations whose exact list is determined by the paper's constructions.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The opposite-head movement may capture bilateral or mirror patterns more directly than single-head models.
  • The synchronization constraint in B2-HRFA offers a tunable parameter for trading expressive power against implementation simplicity.
  • The established hierarchy could be used to classify additional two-dimensional language families by inserting them between the known levels.

Load-bearing premise

The formal definitions of head movement, returning behavior, and acceptance conditions, together with the constructions used in the inclusion and incomparability proofs, are correct and complete.

What would settle it

A single rectangular array language that is accepted by some 2-HRFA yet rejected by every returning pushdown automaton, or a language generated by some context-free matrix grammar that is neither contained in nor contains the 2-HRFA class.

Figures

Figures reproduced from arXiv: 2606.26680 by Benedek Nagy (Eszterhazy Karoly Catholic University, D. Gnanaraj Thomas (Madras Christian College), Eger, Germany), Henning Fernau (Universit\"at Trier, Hungary), R. Jennifer Rose (Madras Christian College), Robinson Thamburaj (Madras Christian College).

Figure 1
Figure 1. Figure 1: A 2-head finite automaton that accepts the language [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Explaining two concatenations of P = [ai, j ]m,n and Q = [bi, j ]m′ ,n ′ [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Some geometric unary operations applied to [PITH_FULL_IMAGE:figures/full_fig_p004_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: RFA processing an input Definition 2.4. A Returning Pushdown Automaton (RPDA) is defined as a 7-tuple M = (Q,Σ,Γ,δ,q0, ◁,#,□) where Q is the finite set of states, Σ is the input alphabet with # ∈/ Σ, Γ is the pushdown alphabet, δ : Q×(Σ∪ {#, ε})×Γ → 2 Q×Γ ∗ is the transition function, q0 ∈ Q is the initial state and ◁ ∈ Γ is the start symbol of the pushdown store. An RPDA also processes the input picture r… view at source ↗
Figure 5
Figure 5. Figure 5: 2-HRFA processing an input of size 5×5. In the following cases, when the heads read # symbol, then in fact only its row is changing in the configuration, the picture with letters and squares does not change. • End of row and one-head moves – Let (q,P□,µ,µ ′ ) and (p,P□,µ +1,µ ′ ) be valid configurations with µ < µ ′ and p ∈ δ(q,#, ε), then (q,P□,µ,µ ′ ) ⊢M (p,P□,µ +1,µ ′ ) if aµ, j = # is scanned by the fi… view at source ↗
Figure 6
Figure 6. Figure 6: 2-HRFA Mrev that recognizes the language Lrev. s s1 s2 s3 s4 (X,X) (•,•) (•,•) (X,X) (#,#) (#,#) (X,X) (X, ε) [PITH_FULL_IMAGE:figures/full_fig_p008_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: A 2-head returning finite automaton MH that accepts the language LH. i.e.,LH =    X • X X X X X • X , X • • X X X X X X • • X , X • • • X X X X X X X • • • X , X • • • X X • • • X X X X X X X • • • X X • • • X ,...    can be accepted by a 2-HRFA, MH (see [PITH_FULL_IMAGE:figures/full_fig_p008_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: 2-HRFA M010 that recognizes the language L010. s p q r (a, ε) (#, ε) (a, ε) (#, ε) (a, ε) (#, ε) (ε,b) (ε,#) [PITH_FULL_IMAGE:figures/full_fig_p009_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: 2-HRFA Ma 3kb k that recognizes the language La 3kb k . Example 3.5. The language Lsquares of unary squares is accepted by the 2-HRFA Msquares = ({s,q, f },{a}, δ,s,{ f },#,□) where q = δ(s,a, ε), q = δ(q, ε,a), s = δ(q, ε,#), f = δ(s,#, ε). For each step of the first head, the second head reads a full row, in this way, while the first head counts the columns of the input, the second head counts the rows. … view at source ↗
Figure 10
Figure 10. Figure 10: B2-HRFA M′ L constructed by Theorem 4.1 recognizing the language LL (from Example 2.3) with only useful states; we sent the transitions with (•, ε)1 not to f but to (s1,s1) to simplify the drawing. Theorem 4.2. L (B2-HRFA) = L (B2-HRDFA) Proof. The proof is based on the subset construction similar to the models RFA for arrays [6] and both￾head stepping two-head automata defined for strings [15]. Theorem 4… view at source ↗
Figure 11
Figure 11. Figure 11: B2-HRFA M′ E that accepts LEV R . both ends after digesting the border symbol(s). (b) If the input array has more than one row, it will first guess the state that M would enter after processing the first and last rows and then also perform reading the first pair of symbols. Again, this is very similar to what happens after digesting the border symbol(s) and then start processing the next pair of rows late… view at source ↗
Figure 12
Figure 12. Figure 12: Hierarchy among classes of array languages recognized by two-dimensional automaton mod [PITH_FULL_IMAGE:figures/full_fig_p015_12.png] view at source ↗
read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 1 minor

Summary. The paper introduces 2-head returning finite automata (2-HRFA) operating on rectangular arrays where both heads move in opposite directions. It claims that the class of picture languages accepted by 2-HRFA is incomparable with those generated by context-free matrix grammars (CFMG) and forms a proper subset of those accepted by returning pushdown automata (RPDA). A constrained variant B2-HRFA is defined with synchronized stepwise head movement, and the paper proves the hierarchy RFA ⊂ B2-HRFA ⊂ 2-HRFA along with closure properties for both families.

Significance. If the constructions and proofs hold, the work contributes to the theory of two-dimensional languages by establishing new automata models, their position relative to CFMG and RPDA, and a strict hierarchy among returning finite automata variants. The explicit constructions for incomparability and proper inclusions would be a strength, as would the investigation of closure properties.

minor comments (1)
  1. The abstract and reader's summary reference specific constructions for the incomparability with CFMG and the inclusions with RPDA, but without section numbers or explicit definitions of acceptance conditions and head movements in the provided text, it is not possible to verify edge cases or completeness of the proofs.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their summary of the manuscript. No specific major comments were provided in the report, so we are unable to address particular points of concern regarding the constructions, proofs, or results. We remain available to respond to any detailed feedback on the incomparability with CFMG, the inclusions with RPDA and RFA, the B2-HRFA variant, or the closure properties.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper introduces new models (2-HRFA and B2-HRFA) via explicit definitions of head movement and acceptance, then establishes relations to prior independent classes (CFMG, RPDA, RFA) through constructions and proofs of inclusion/incomparability. No equations, parameters, or self-referential reductions appear; all steps rely on standard automata-theoretic arguments against externally defined models with no load-bearing self-citation chains or fitted inputs renamed as predictions. The derivation chain is self-contained.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 2 invented entities

The paper's contribution rests on the new automata definitions themselves; all other elements are standard background from automata theory.

axioms (1)
  • standard math Standard definitions of finite automata, picture languages over rectangular arrays, and returning behavior from prior literature.
    Invoked implicitly when defining 2-HRFA and when comparing to CFMG and RPDA.
invented entities (2)
  • 2-HRFA no independent evidence
    purpose: Two-head returning finite automaton with opposite-direction head movement for picture acceptance.
    New model introduced to study picture languages.
  • B2-HRFA no independent evidence
    purpose: Synchronized stepwise variant of 2-HRFA.
    Constrained model introduced to refine the hierarchy.

pith-pipeline@v0.9.1-grok · 5767 in / 1321 out tokens · 31983 ms · 2026-06-26T02:06:30.566366+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

21 extracted references · 17 canonical work pages

  1. [1]

    Amar & G

    V . Amar & G. Putzolu (1964): On a family of linear grammars . Information and Control 7, pp. 283–291, doi:10.1016/S0019-9958(64)90294-3

    work page doi:10.1016/s0019-9958(64)90294-3 1964

  2. [2]

    Blum & C

    M. Blum & C. Hewitt (1967): Automata on a 2-dimensional Tape . In: Proceedings of the 8th Annual Symposium on Switching and Automata Theory (SW AT), IEEE, pp. 155–160, doi:10.1109/FOCS.1967.6

    work page doi:10.1109/focs.1967.6 1967

  3. [3]

    Fernau, R

    H. Fernau, R. Freund & M. Holzer (1998): Character recognition with k-head finite array automata . In A. Amin, D. Dori, P. Pudil & H. Freeman, editors:Advances in Pattern Recognition, Joint IAPR International Workshops SSPR ’98 and SPR ’98, LNCS 1451, Springer, pp. 282–291, doi:10.1007/BFb0033246

    work page doi:10.1007/bfb0033246 1998

  4. [4]

    Fernau, R

    H. Fernau, R. Freund & M. Holzer (1999): Regulated array grammars of finite index . In Gh. P ˘aun & A. Salomaa, editors: Grammatical Models of Multi-Agent Systems, London: Gordon and Breach, pp. 157– 181 (Part I) and 284–296 (Part II)

    1999

  5. [5]

    Novel Pathways ink-Contact Geometry

    H. Fernau, R. J.Rose, R.Thamburaj & D. G.Thomas (2026): Boustrophedon pushdown automata for two- dimensional picture languages. In P. Balázs, R. P. Barneva, V . E. Brimkov & A. Nagy, editors:Combinato- rial Image Analysis, LNCS 15985, Springer Nature Switzerland, Cham, pp. 35–50, doi:10.1007/978-3-032- 19347-6_3

    work page doi:10.1007/978-3-032- 2026

  6. [6]

    Fernau, M

    H. Fernau, M. Paramasivan, M. L. Schmid & D. G. Thomas (2018): Simple picture processing based on finite automata and regular grammars . Journal of Computer and System Sciences 95, pp. 232–258, doi:10.1016/j.jcss.2017.07.011

    work page doi:10.1016/j.jcss.2017.07.011 2018

  7. [7]

    Fernau, M

    H. Fernau, M. Paramasivan & D. G. Thomas (2018): Picture Scanning Automata and Group Actions on Pictures. Romanian Journal of Information Science and Technology 21(3), pp. 238–248. 52 2-Head 2D Returning Finite Automata

    2018

  8. [8]

    Fernau & J

    H. Fernau & J. M. Sempere (2000): Permutations and control sets for learning non-regular language families. In A. L. Oliveira, editor:Grammatical Inference: Algorithms and Applications, 5th International Colloquium ICGI 2000, LNCS/LNAI 1891, Springer, pp. 75–88, doi:10.1007/978-3-540-45257-7_7

    work page doi:10.1007/978-3-540-45257-7_7 2000

  9. [9]

    In: Handbook of formal lan- guages: volume 3 beyond words , Springer, pp

    D. Giammarresi & A. Restivo (1997): Two-dimensional languages. In G. Rozenberg & A. Salomaa, editors: Handbook of Formal Languages, 3, Springer, Berlin, pp. 215–267, doi:10.1007/978-3-642-59126-6_4

    work page doi:10.1007/978-3-642-59126-6_4 1997

  10. [10]

    Ginsburg & E

    S. Ginsburg & E. H. Spanier (1966): Finite-turn pushdown automata. SIAM Journal of Control 4(3), pp. 429–453, doi:10.1137/0304034

    work page doi:10.1137/0304034 1966

  11. [11]

    J. E. Hopcroft & J. D. Ullman (1979): Introduction to Automata Theory, Languages, and Computation . Reading (MA): Addison-Wesley

    1979

  12. [12]

    Hromkovic (1985): On one-way two-head deterministic finite state automata

    J. Hromkovic (1985): On one-way two-head deterministic finite state automata . Computers and Artificial Intelligence 4(6), pp. 503–526, doi:10.5555/1787385.1787418

    work page doi:10.5555/1787385.1787418 1985

  13. [13]

    Krithivasan & R

    K. Krithivasan & R. Siromoney (1974): Characterizations of regular and context-free matrices. International Journal of Computer Mathematics 4(A), pp. 229–245, doi:10.1080/00207167408803090

    work page doi:10.1080/00207167408803090 1974

  14. [14]

    Bourbaki, Lie Groups and Lie Algebras, Chapters 4–6, Elements of Mathematics, Springer-Verlag, Berlin, 2002

    R. Loukanova (2007): Linear context-free languages. In C. B. Jones, Z. Liu & J. Woodcock, editors: The- oretical Aspects of Computing – ICTAC 2007, LNCS 4711, Springer, pp. 351–365, doi:10.1007/978-3-540- 75292-9_24

    work page doi:10.1007/978-3-540- 2007

  15. [15]

    Nagy (2010): 5 ′ → 3′ Sensing Watson-Crick Finite Automata

    B. Nagy (2010): 5 ′ → 3′ Sensing Watson-Crick Finite Automata . In G. P. C. Fung, editor: Sequence and Genome Analysis II – Methods and Applications, iConcept Press, pp. 39–56

    2010

  16. [16]

    Nagy (2012): A class of 2-head finite automata for linear languages

    B. Nagy (2012): A class of 2-head finite automata for linear languages . Triangle 8, pp. 89–99, doi:10.17345/triangle8.89-99

    work page doi:10.17345/triangle8.89-99 2012

  17. [17]

    Nagy & S

    B. Nagy & S. Parchami (2021): On deterministic sensing 5′ → 3′ Watson–Crick finite automata: a full hierarchy in 2detLIN. Acta Informatica 58(3), pp. 153–175, doi:10.1007/s00236-019-00362-6

    work page doi:10.1007/s00236-019-00362-6 2021

  18. [18]

    B. Nagy, S. Parchami & H. Mir-Mohammad-Sadeghi (2017): A New Sensing 5′ → 3′ Watson-Crick Automata Concept. In E. Csuhaj-Varjú, P. Dömösi & Gy. Vaszil, editors:Proc. 15th Int. Conf. on Automata and Formal Languages, AFL 2017, Debrecen, Hungary, 2017, EPTCS 252, pp. 195–204, doi:10.4204/EPTCS.252.19

    work page doi:10.4204/eptcs.252.19 2017

  19. [19]

    A. L. Rosenberg (1966): On multi-head finite automata. IBM Journal of Research and Development 10(5), pp. 388–394, doi:10.1147/rd.105.0388

    work page doi:10.1147/rd.105.0388 1966

  20. [20]

    J. M. Sempere & P. García (1994): A characterization of even linear languages and its application to the learning problem. In R. C. Carrasco & J. Oncina, editors: Proc. Second Int. Colloquium on Grammati- cal Inference (ICGI-94): Grammatical Inference and Applications , LNCS/LNAI 862, Springer, pp. 38–44, doi:10.1007/3-540-58473-0_135

    work page doi:10.1007/3-540-58473-0_135 1994

  21. [21]

    Siromoney, R

    G. Siromoney, R. Siromoney & K. Krithivasan (1972): Abstract families of matrices and picture languages. Computer Graphics and Image Processing 1, pp. 284–307, doi:10.1016/S0146-664X(72)80019-4

    work page doi:10.1016/s0146-664x(72)80019-4 1972