Document Open Access Logo

A Complexity Approach to Tree Algebras: the Polynomial Case

Authors Thomas Colcombet , Arthur Jaquard

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2022.37.pdf
  • Filesize: 0.82 MB
  • 14 pages

Document Identifiers

Author Details

Thomas Colcombet
  • Université Paris Cité, CNRS, IRIF, F-75013, Paris, France
Arthur Jaquard
  • Université Paris Cité, CNRS, IRIF, F-75013, Paris, France

Funding

  • Colcombet, Thomas: Supported by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No.670624) and the DeLTA ANR project (ANR-16-CE40-0007).

Cite As Get BibTex

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) https://doi.org/10.4230/LIPIcs.MFCS.2022.37

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Tree languages
  • Theory of computation → Regular languages
Keywords
  • Tree algebra
  • nominal automata
  • language theory

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Achim Blumensath. Recognisability for algebras of infinite trees. Theoretical Computer Science, 412(29):3463-3486, 2011. URL: https://doi.org/10.1016/j.tcs.2011.02.037.
  2. Achim Blumensath. Regular Tree Algebras. Logical Methods in Computer Science, Volume 16, Issue 1, February 2020. URL: https://doi.org/10.23638/LMCS-16(1:16)2020.
  3. Mikołaj Bojanczyk. Slightly infinite sets, 2016. A draft of a book available at URL: https://www.mimuw.edu.pl/~bojan/paper/atom-book.
  4. Mikolaj Bojanczyk and Michal Pilipczuk. Definability equals recognizability for graphs of bounded treewidth. In Martin Grohe, Eric Koskinen, and Natarajan Shankar, editors, Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, LICS'16, New York, NY, USA, July 5-8, 2016, pages 407-416. ACM, 2016. URL: https://doi.org/10.1145/2933575.2934508.
  5. 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). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2021. Google Scholar
  6. Thomas Colcombet and Christof Löding. Regular cost functions over finite trees. In Proceedings of the 25th Annual IEEE Symposium on Logic in Computer Science, LICS 2010, 11-14 July 2010, Edinburgh, United Kingdom, pages 70-79. IEEE Computer Society, 2010. URL: https://doi.org/10.1109/LICS.2010.36.
  7. Bruno Courcelle and Joost Engelfriet. Graph structure and monadic second-order logic: a language-theoretic approach, volume 138. Cambridge University Press, 2012. Google Scholar
  8. Zoltán Ésik and Pascal Weil. Algebraic recognizability of regular tree languages. Theor. Comput. Sci., 340(1):291-321, 2005. URL: https://doi.org/10.1016/j.tcs.2005.03.038.
  9. Zoltán Ésik and Pascal Weil. Algebraic characterization of logically defined tree languages. Int. J. Algebra Comput., 20(2):195-239, 2010. URL: https://doi.org/10.1142/S0218196710005595.
  10. Sławomir Lasota, Bartek Klin, and Mikołaj Bojańczyk. Automata theory in nominal sets. Logical Methods in Computer Science, 10, 2014. Google Scholar
  11. Marcel-Paul Schützenberger. On finite monoids having only trivial subgroups. Information and Control, 8:190-194, 1965. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact