A Unifying Approach to Picture Automata
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866913158525878272 |
|---|---|
| author | Meeres, Yvo Ad Mráz, František |
| author_facet | Meeres, Yvo Ad Mráz, František |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_12077 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Unifying Approach to Picture Automata Meeres, Yvo Ad Mráz, František Formal Languages and Automata Theory 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. |
| title | A Unifying Approach to Picture Automata |
| topic | Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2509.12077 |