DROPS

Document

DOI: 10.4230/LIPIcs.CONCUR.2026.9

A Factorization Theorem for Forest Algebras

Authors: Shaull Almagor, Michaël Cadilhac, and Asaf Shoham

Published in: LIPIcs, Volume 391, 37th International Conference on Concurrency Theory (CONCUR 2026)

Abstract

Simon’s factorization theorem is a celebrated tool in algebraic automata theory, providing bounded-depth decompositions of words with respect to morphisms into finite semigroups. We develop an analogue of Simon’s theorem for forests in the setting of forest algebras. In contrast with words, this presents a basic difficulty: recursively factoring a forest requires keeping track of where each subforest "fits". This difficulty ripples throughout the proof, and we overcome it by augmenting the free forest algebra and by developing a framework that supports recursive factorization of forests, along with its semantic implications. Our main result identifies a new semantic restriction on morphisms (called R-alignment) which intuitively ensures that different ways of cutting a forest remain compatible (in a certain sense) at the semigroup level. Under this condition, we prove that every morphism admits decompositions of bounded depth. We also prove that without this restriction, there are morphisms for which no bounded-depth decomposition exists (under our notion of decomposition).

Cite as

Shaull Almagor, Michaël Cadilhac, and Asaf Shoham. A Factorization Theorem for Forest Algebras. In 37th International Conference on Concurrency Theory (CONCUR 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 391, pp. 9:1-9:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{almagor_et_al:LIPIcs.CONCUR.2026.9,
  author =	{Almagor, Shaull and Cadilhac, Micha\"{e}l and Shoham, Asaf},
  title =	{{A Factorization Theorem for Forest Algebras}},
  booktitle =	{37th International Conference on Concurrency Theory (CONCUR 2026)},
  pages =	{9:1--9:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-447-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{391},
  editor =	{Sokolova, Ana and Totzke, Patrick},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2026.9},
  URN =		{urn:nbn:de:0030-drops-273403},
  doi =		{10.4230/LIPIcs.CONCUR.2026.9},
  annote =	{Keywords: Factorization Forest, Semigroup, Forest Algebra, Green’s relations, Tree Languages}
}

Search Results

Documents authored by Shoham, Asaf

A Factorization Theorem for Forest Algebras

Abstract

Cite as

Thanks for your feedback!

Could not send message