Paper: Differential Tree Automata (at LICS 2026)
Open access: https://doi.org/10.4230/LIPIcs.LICS.2026.70
Abstract
In this paper we introduce the notion of a differential tree automaton. Differential tree automata generalise weighted tree automata (over a field) by allowing the transition weights to be rational functions of the tree size. Whereas the class of generating functions of weighted tree automata coincides with the class of algebraic power series, our main result is that the class of generating functions of differential tree automata coincides with the class of differentially algebraic power series. As a corollary, we obtain a decision procedure for determining equivalence of differential tree automata. In the course of proving our main result we identify a class of recurrences that characterises the sequence of coefficients of a differentially algebraic power series, generalising Reutenauer’s matrix representation of polynomially recursive sequences. We further identify a natural syntactic subset of differential tree automata whose generating functions are given by rational dynamical systems, that is, as components of the solution of a system of differential equations y' = F(y), where F is a vector of rational functions that is defined at y(0). We further show that this class of power series can be characterised in terms of the classical notion of weighted tree automata by using a labelled generating function on trees.
BibTeX
@InProceedings{AitElManssourCheval-DifferentialTreeAut,
author = {Rida Ait El Manssour and Vincent Cheval and Mahsa Shirmohammadi and James Worrell},
title = {Differential Tree Automata},
booktitle = {Proceedings of the Forty-First Annual Symposium on Logic in Computer Science (LICS 2026)},
year = {2026},
month = {July},
pages = {70:1--70:22},
location = {Lisbon, Portugal},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum für Informatik},
doi = {10.4230/LIPIcs.LICS.2026.70}
}