DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2022.37

A Complexity Approach to Tree Algebras: the Polynomial Case

Authors: Thomas Colcombet and Arthur Jaquard

Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)

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.

Cite as

Thomas Colcombet and Arthur Jaquard. A Complexity Approach to Tree Algebras: the Polynomial Case. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 37:1-37:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@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/entities/document/10.4230/LIPIcs.MFCS.2022.37},
  URN =		{urn:nbn:de:0030-drops-168357},
  doi =		{10.4230/LIPIcs.MFCS.2022.37},
  annote =	{Keywords: Tree algebra, nominal automata, language theory}
}

Document

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

DOI: 10.4230/LIPIcs.ICALP.2021.127

A Complexity Approach to Tree Algebras: the Bounded Case

Authors: Thomas Colcombet and Arthur Jaquard

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract

In this paper, we initiate a study of the expressive power of tree algebras, and more generally infinitely sorted algebras, based on their asymptotic complexity. We provide a characterization of the expressiveness of tree algebras of bounded complexity. Tree algebras in many of their forms, such as clones, hyperclones, operads, etc, as well as other kind of algebras, are infinitely sorted: the carrier is a multi sorted set indexed by a parameter that can be interpreted as the number of variables or hole types. Finite such algebras - meaning when all sorts are finite - can be classified depending on the asymptotic size of the carrier sets as a function of the parameter, that we call the complexity of the algebra. This naturally defines the notions of algebras of bounded, linear, polynomial, exponential or doubly exponential complexity... We initiate in this work a program of analysis of the complexity of infinitely sorted algebras. Our main result precisely characterizes the tree algebras of bounded complexity based on the languages that they recognize as Boolean closures of simple languages. Along the way, we prove that such algebras that are syntactic (minimal for a language) are exactly those in which, as soon as there are sufficiently many variables, the elements are invariant under permutation of the variables.

Cite as

Thomas Colcombet and Arthur Jaquard. A Complexity Approach to Tree Algebras: the Bounded Case. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 127:1-127:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{colcombet_et_al:LIPIcs.ICALP.2021.127,
  author =	{Colcombet, Thomas and Jaquard, Arthur},
  title =	{{A Complexity Approach to Tree Algebras: the Bounded Case}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{127:1--127:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.127},
  URN =		{urn:nbn:de:0030-drops-141966},
  doi =		{10.4230/LIPIcs.ICALP.2021.127},
  annote =	{Keywords: Tree algebra, infinite tree, language theory}
}

Search Results

Documents authored by Jaquard, Arthur

A Complexity Approach to Tree Algebras: the Polynomial Case

Abstract

Cite as

A Complexity Approach to Tree Algebras: the Bounded Case

Abstract

Cite as

Thanks for your feedback!

Could not send message