arXiv Open Access 2025

A Unifying Approach to Picture Automata

Yvo Ad Meeres František Mráz

Lihat Sumber

Abstrak

A directed acyclic graph (DAG) can represent a two-dimensional string or picture. We propose recognizing picture languages using DAG automata by encoding 2D inputs into DAGs. An encoding can be input-agnostic (based on input size only) or input-driven (depending on symbols). Three distinct input-agnostic encodings characterize classes of picture languages accepted by returning finite automata, boustrophedon automata, and online tessellation automata. Encoding a string as a simple directed path limits recognition to regular languages. However, input-driven encodings allow DAG automata to recognize some context-sensitive string languages and outperform online tessellation automata in two dimensions.

Topik & Kata Kunci

cs.FL

Penulis (2)

Yvo Ad Meeres

František Mráz

Format Sitasi

APA MLA BibTeX

Meeres, Y.A., Mráz, F. (2025). A Unifying Approach to Picture Automata. https://arxiv.org/abs/2509.12077

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2025
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓