Overview
This research introduces a new family of two-head finite automata, termed two-head returning finite automata (2-HRFA), designed for operations on rectangular arrays of picture languages. A variation of this model, the both head stepping two-head returning finite automata (B2-HRFA), is also defined. The study focuses on characterizing the classes of picture languages accepted by 2-HRFA and B2-HRFA, and investigating their relationships with established automata models and language classes, including context-free matrix grammars (CFMG) and returning pushdown automata (RPDA). Additionally, the closure properties for the language families accepted by both 2-HRFA and B2-HRFA are examined.
Research Context
The work positions itself within the field of automata theory, specifically concerning models for processing array-based inputs, or 'picture languages'. The exploration of multi-head finite automata, particularly with specific constraints on head movement, contributes to the understanding of computational power and expressive capabilities for recognizing these types of languages. The comparison with CFMG and RPDA situates 2-HRFA and B2-HRFA within an existing hierarchy of language recognizers.
Approach
The research defines the 2-HRFA model, characterized by two heads operating in opposite directions on rectangular arrays. A constrained variant, the B2-HRFA, is also introduced, where both heads are required to move in a synchronized, stepwise manner. The study then proceeds to establish relationships between the language classes accepted by these new automata and existing models. Specifically, it investigates the proper subset and incomparability relationships between the classes of languages accepted by 2-HRFA, B2-HRFA, returning finite automata (RFA), context-free matrix grammars (CFMG), and returning pushdown automata (RPDA). The methodology involves proving these relationships, as well as analyzing the closure properties for the language families accepted by both 2-HRFA and B2-HRFA.
Findings
- The class of picture languages accepted by 2-HRFA is incomparable with the class of languages generated by context-free matrix grammars (CFMG).
- The class of picture languages accepted by 2-HRFA forms a proper subset of the class of languages accepted by returning pushdown automata (RPDA).
- The class of languages accepted by returning finite automata (RFA) is a proper subset of the class of languages accepted by B2-HRFA.
- The class of languages accepted by B2-HRFA 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 were investigated.