Skip to content
DraconiticResearch
Search Sources API
194,161 studies31 sourcesUpdated 23 min ago
PreprintarXiv licencearXiv

Tree Bricks and Finite Tree Automata

  • Annoy Sengupta
Open at sourcePDFDOICite

Abstract

Let Λ=KQ/I be a finite-dimensional zero-relation algebra. We encode Crawley--Boevey tree modules over Λ by finite rooted trees labelled by arrows of Q and their formal inverses, and construct a deterministic finite bottom-up tree automaton recognizing exactly these encodings. We define an accepted tree to be an automata-induced tree brick when it has no non-trivial factor--image self-overlap, and use Crawley--Boevey's graph-map basis to prove that this is equivalent to brickness of the associated tree module. We also introduce local colourings of Q1 and show that the arrow alphabet can be compressed without changing the tree data, graph maps, or brick property. The optimal number of colours for such a compression is the maximum of the in-degree and out-degree of Q. We conclude by asking whether the tree language consisting only of bricks is regular.

Related

  1. Addendum to: Mahler's method in several variables and finite automata
    Boris Adamczewski, Colin Faverjon
    Annals of MathematicsPeer-reviewedCC BY-NC-ND 4.0Full text1 citedAlgebra & number theoryCombinatorics & discrete mathematicsHAL
  2. Elementary cellular automata: spectral properties of Koopman operator for finite periodic realizations
    Qingying Zhu, Serge Richard
    arXivPreprintCC BY 4.0Full textAnalysis & PDEsarXiv
  3. Mahler's method in several variables and finite automata
    Boris Adamczewski, Colin Faverjon
    Annals of MathematicsPeer-reviewedCC BY 4.0Full text5 citedAlgebra & number theoryHAL
  4. Finite-ring obstructions for quadratic binary radius-two cellular automata
    Houqiao Fu
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsStatistical & nonlinear physicsarXiv
  5. Bricks in which every vertex is incident with a forcing edge
    Xinyu Dai, Fuliang Lu, Yaxian Zhang
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{sengupta2026tree,
  title = {{Tree Bricks and Finite Tree Automata}},
  author = {Annoy Sengupta},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.22406},
  eprint = {2609.22406},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.22406},
}
RIS
TY  - UNPB
TI  - Tree Bricks and Finite Tree Automata
AU  - Annoy Sengupta
PY  - 2026
DA  - 2026/09/18
PB  - arXiv
DO  - 10.48550/arxiv.2609.22406
UR  - https://arxiv.org/abs/2609.22406
AB  - Let Λ=KQ/I be a finite-dimensional zero-relation algebra. We encode Crawley--Boevey tree modules over Λ by finite rooted trees labelled by arrows of Q and their formal inverses, and construct a deterministic finite bottom-up tree automaton recognizing exactly these encodings. We define an accepted tree to be an automata-induced tree brick when it has no non-trivial factor--image self-overlap, and use Crawley--Boevey's graph-map basis to prove that this is equivalent to brickness of the associated tree module. We also introduce local colourings of Q_1 and show that the arrow alphabet can be compressed without changing the tree data, graph maps, or brick property. The optimal number of colours for such a compression is the maximum of the in-degree and out-degree of Q. We conclude by asking whether the tree language consisting only of bricks is regular.
ER  -