A Complexity Approach to Tree Algebras: the Bounded Case
| Autor: | Colcombet, Thomas, Jaquard, Arthur |
|---|---|
| Přispěvatelé: | Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Centre National de la Recherche Scientifique (CNRS)-Université de Paris (UP), Centre National de la Recherche Scientifique (CNRS), Université de Paris (UP), Bansal, Nikhil, Merelli, Emanuela, Worrell, James, Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité), Université Paris Cité (UPCité), ANR-16-CE40-0007,DELTA,DÉfis pour la Logique, les Transducteurs et les Automates(2016), European Project: 670624,H2020,ERC-2014-ADG,DuaLL(2015) |
| Jazyk: | angličtina |
| Rok vydání: | 2021 |
| Předmět: |
2012 ACM Subject Classification Theory of computation → Tree languages
Logic language theory [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO] language theory Digital Object Identifier 10.4230/LIPIcs.ICALP.2021.127 Category Track B: Automata Theory of computation → Tree languages Theory of computation → Regular languages phrases Tree algebra Theory of computation → Regular languages Semantics ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION [INFO]Computer Science [cs] Tree algebra infinite tree and Theory of Programming |
| Zdroj: | 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), Jul 2021, Glasgow, United Kingdom. ⟨10.4230/LIPIcs.ICALP.2021.127⟩ Nikhil Bansal, Emanuela Merelli, and James Worrell, editors, 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021 International Colloquium on Automata, Languages, and Programming, ICALP International Colloquium on Automata, Languages, and Programming, ICALP, 2021, Glasgow, United Kingdom. ⟨10.4230/LIPIcs.ICALP.2021.127⟩ International Colloquium on Automata, Languages, and Programming, ICALP, 2021, Glasgow, United Kingdom. pp.123:1-123:14, ⟨10.4230/LIPIcs.ICALP.2021.127⟩ |
| DOI: | 10.4230/LIPIcs.ICALP.2021.127⟩ |
| Popis: | 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. LIPIcs, Vol. 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), pages 127:1-127:13 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|