DROPS

Document

DOI: 10.4230/LIPIcs.LICS.2026.70

Differential Tree Automata

Authors: Rida Ait El Manssour, Vincent Cheval, Mahsa Shirmohammadi, and James Worrell

Published in: LIPIcs, Volume 380, 41st Annual Symposium on Logic in Computer Science (LICS 2026)

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.

Cite as

Rida Ait El Manssour, Vincent Cheval, Mahsa Shirmohammadi, and James Worrell. Differential Tree Automata. In 41st Annual Symposium on Logic in Computer Science (LICS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 380, pp. 70:1-70:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{aitelmanssour_et_al:LIPIcs.LICS.2026.70,
  author =	{Ait El Manssour, Rida and Cheval, Vincent and Shirmohammadi, Mahsa and Worrell, James},
  title =	{{Differential Tree Automata}},
  booktitle =	{41st Annual Symposium on Logic in Computer Science (LICS 2026)},
  pages =	{70:1--70:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-434-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{380},
  editor =	{Faggian, Claudia and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.LICS.2026.70},
  URN =		{urn:nbn:de:0030-drops-268570},
  doi =		{10.4230/LIPIcs.LICS.2026.70},
  annote =	{Keywords: Combinatorial species, Differentially algebraic series, Weighted automata}
}

Document

Track B: Automata, Logic, Semantics, and Theory of Programming

DOI: 10.4230/LIPIcs.ICALP.2026.158

Revisiting Finiteness of Matrix Monoids

Authors: Rida Ait El Manssour, Roland Guttenberg, Nathan Lhote, Mahsa Shirmohammadi, and James Ben Worrell

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract

This paper concerns decision problems related to finite monoids of rational matrices. We show that determining finiteness of a given finitely presented monoid is in PSpace, improving the known coNExp^NP bound. We also show that the membership problem for finite matrix monoids is PSpace-complete, improving the known NExp-upper bound. Our two complexity results are corollaries of a new polynomial bit-size bound on matrix entries in finite monoids. This is obtained by reduction to the case of matrix groups, using the structure theory of noncommutative algebras and of matrix monoids. Our techniques also give us a polynomial-time algorithm for deciding whether a monoid of rational matrices is conjugate to a monoid of integer matrices.

Cite as

Rida Ait El Manssour, Roland Guttenberg, Nathan Lhote, Mahsa Shirmohammadi, and James Ben Worrell. Revisiting Finiteness of Matrix Monoids. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 158:1-158:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{aitelmanssour_et_al:LIPIcs.ICALP.2026.158,
  author =	{Ait El Manssour, Rida and Guttenberg, Roland and Lhote, Nathan and Shirmohammadi, Mahsa and Worrell, James Ben},
  title =	{{Revisiting Finiteness of Matrix Monoids}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{158:1--158:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.158},
  URN =		{urn:nbn:de:0030-drops-265745},
  doi =		{10.4230/LIPIcs.ICALP.2026.158},
  annote =	{Keywords: Matrix Semigroups, Finiteness, Integrality, Bitsize Bound}
}

Search Results

Documents authored by Ait El Manssour, Rida

Differential Tree Automata

Abstract

Cite as

Revisiting Finiteness of Matrix Monoids

Abstract

Cite as

Thanks for your feedback!

Could not send message