2026-07-23T08:19:29Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16835 2024-03-06T10:58:27Z ddc:004 open_access

A Complexity Approach to Tree Algebras: the Polynomial Case Colcombet, Thomas Jaquard, Arthur Tree algebra nominal automata language theory In this paper, we consider infinitely sorted tree algebras recognising regular language of finite trees. We pursue their analysis under the angle of their asymptotic complexity, i.e. the asymptotic size of the sorts as a function of the number of variables involved. Our main result establishes an equivalence between the languages recognised by algebras of polynomial complexity and the languages that can be described by nominal word automata that parse linearisation of the trees. On the way, we show that for such algebras, having polynomial complexity corresponds to having uniformly boundedly many orbits under permutation of the variables, or having a notion of bounded support (in a sense similar to the one in nominal sets). We also show that being recognisable by an algebra of polynomial complexity is a decidable property for a regular language of trees. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Thomas Colcombet and Arthur Jaquard 2022 Is Part Of LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2022.37 urn:nbn:de:0030-drops-168357 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.37 eng https://creativecommons.org/licenses/by/4.0/legalcode