License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2022.37
URN: urn:nbn:de:0030-drops-168357
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16835/
Go to the corresponding LIPIcs Volume Portal

Colcombet, Thomas ; Jaquard, Arthur

A Complexity Approach to Tree Algebras: the Polynomial Case

pdf-format:
LIPIcs-MFCS-2022-37.pdf (0.8 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{colcombet_et_al:LIPIcs.MFCS.2022.37,
  author =	{Colcombet, Thomas and Jaquard, Arthur},
  title =	{{A Complexity Approach to Tree Algebras: the Polynomial Case}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{37:1--37:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16835},
  URN =		{urn:nbn:de:0030-drops-168357},
  doi =		{10.4230/LIPIcs.MFCS.2022.37},
  annote =	{Keywords: Tree algebra, nominal automata, language theory}
}

Keywords: Tree algebra, nominal automata, language theory
Collection: 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)
Issue Date: 2022
Date of publication: 22.08.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI