| 1. |
- Kattge, Jens, et al.
(författare)
-
TRY plant trait database - enhanced coverage and open access
- 2020
-
Ingår i: Global Change Biology. - : Wiley-Blackwell. - 1354-1013 .- 1365-2486. ; 26:1, s. 119-188
-
Tidskriftsartikel (refereegranskat)abstract
- Plant traits-the morphological, anatomical, physiological, biochemical and phenological characteristics of plants-determine how plants respond to environmental factors, affect other trophic levels, and influence ecosystem properties and their benefits and detriments to people. Plant trait data thus represent the basis for a vast area of research spanning from evolutionary biology, community and functional ecology, to biodiversity conservation, ecosystem and landscape management, restoration, biogeography and earth system modelling. Since its foundation in 2007, the TRY database of plant traits has grown continuously. It now provides unprecedented data coverage under an open access data policy and is the main plant trait database used by the research community worldwide. Increasingly, the TRY database also supports new frontiers of trait-based plant research, including the identification of data gaps and the subsequent mobilization or measurement of new data. To support this development, in this article we evaluate the extent of the trait data compiled in TRY and analyse emerging patterns of data coverage and representativeness. Best species coverage is achieved for categorical traits-almost complete coverage for 'plant growth form'. However, most traits relevant for ecology and vegetation modelling are characterized by continuous intraspecific variation and trait-environmental relationships. These traits have to be measured on individual plants in their respective environment. Despite unprecedented data coverage, we observe a humbling lack of completeness and representativeness of these continuous traits in many aspects. We, therefore, conclude that reducing data gaps and biases in the TRY database remains a key challenge and requires a coordinated approach to data mobilization and trait measurements. This can only be achieved in collaboration with other initiatives.
|
|
| 2. |
- Arrighi, Emmanuel, et al.
(författare)
-
Synchronization and Diversity of Solutions
- 2023
-
Ingår i: Thirty-Seventh AAAI Conference on Artificial Intelligence. - 9781577358800 ; , s. 11516-11524
-
Konferensbidrag (refereegranskat)abstract
- A central computational problem in the realm of automata theory is the problem of determining whether a finite automaton A has a synchronizing word. This problem has found applications in a variety of subfields of artificial intelligence, including planning, robotics, and multi-agent systems. In this work, we study this problem within the framework of diversity of solutions, an up-and-coming trend in the field of artificial intelligence where the goal is to compute a set of solutions that are sufficiently distinct from one another. We define a notion of diversity of solutions that is suitable for contexts were solutions are strings that may have distinct lengths. Using our notion of diversity, we show that for each fixed r ∈ N, each fixed finite automaton A, and each finite automaton B given at the input, the problem of determining the existence of a diverse set {w1,w2, . . . ,wr} ⊆ L(B) of words that are synchronizing for A can be solved in polynomial time. Finally, we generalize this result to the realm of conformant planning, where the goal is to devise plans that achieve a goal irrespectively of initial conditions and of nondeterminism that may occur during their execution.
|
|
| 3. |
- De Oliveira Oliveira, Mateus
(författare)
-
Canonizable partial order generators
- 2012
-
Ingår i: Language and Automata Theory and Applications. - Berlin, Heidelberg : Springer Berlin/Heidelberg. - 9783642283314 ; , s. 445-457
-
Konferensbidrag (refereegranskat)abstract
- In a previous work we introduced slice graphs as a way to specify both infinite languages of directed acyclic graphs (DAGs) and infinite languages of partial orders. Therein we focused on the study of Hasse diagram generators, i.e., slice graphs that generate only transitive reduced DAGs. In the present work we show that any slice graph can be transitive reduced into a Hasse diagram generator representing the same set of partial orders. This result allow us to establish unknown connections between the true concurrent behavior of bounded p/t-nets and traditional approaches for representing infinite families of partial orders, such as Mazurkiewicz trace languages and Message Sequence Chart (MSC) languages. Going further, we identify the family of weakly saturated slice graphs. The class of partial order languages which can be represented by weakly saturated slice graphs is closed under union, intersection and a suitable notion of complementation (bounded cut-width complementation). The partial order languages in this class also admit canonical representatives in terms of Hasse diagram generators, and have decidable inclusion and emptiness of intersection. Our transitive reduction algorithm plays a fundamental role in these decidability results.
|
|
| 4. |
- de Oliveira Oliveira, Mateus, 1982-
(författare)
-
Combinatorial Slice Theory
- 2013
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Slices are digraphs that can be composed together to form larger digraphs.In this thesis we introduce the foundations of a theory whose aim is to provide ways of defining and manipulating infinite families of combinatorial objects such as graphs, partial orders, logical equations etc. We give special attentionto objects that can be represented as sequences of slices. We have successfully applied our theory to obtain novel results in three fields: concurrency theory,combinatorics and logic. Some notable results are:Concurrency Theory:We prove that inclusion and emptiness of intersection of the causalbehavior of bounded Petri nets are decidable. These problems had been open for almost two decades.We introduce an algorithm to transitively reduce infinite familiesof DAGs. This algorithm allows us to operate with partial order languages defined via distinct formalisms, such as, Mazurkiewicztrace languages and message sequence chart languages.Combinatorics:For each constant z ∈ N, we define the notion of z-topological or-der for digraphs, and use it as a point of connection between the monadic second order logic of graphs and directed width measures, such as directed path-width and cycle-rank. Through this connection we establish the polynomial time solvability of a large numberof natural counting problems on digraphs admitting z-topological orderings.Logic:We introduce an ordered version of equational logic. We show thatthe validity problem for this logic is fixed parameter tractable withrespect to the depth of the proof DAG, and solvable in polynomial time with respect to several notions of width of the equations being proved. In this way we establish the polynomial time provability of equations that can be out of reach of techniques based on completion and heuristic search.
|
|
| 5. |
- De Oliveira Oliveira, Mateus, et al.
(författare)
-
From Width-Based Model Checking to Width-Based Automated Theorem Proving
- 2023
-
Ingår i: Proceedings of the AAAI Conference on Artificial Intelligence. - : AAAI Press. - 9781577358800 ; , s. 6297-6304
-
Konferensbidrag (refereegranskat)abstract
- In the field of parameterized complexity theory, the study of graph width measures has been intimately connected with the development of width-based model checking algorithms for combinatorial properties on graphs. In this work, we introduce a general framework to convert a large class of width-based model-checking algorithms into algorithms that can be used to test the validity of graph-theoretic conjectures on classes of graphs of bounded width. Our framework is modular and can be applied with respect to several well-studied width measures for graphs, including treewidth and cliquewidth. As a quantitative application of our framework, we prove analytically that for several long-standing graph-theoretic conjectures, there exists an algorithm that takes a number k as input and correctly determines in time double-exponential in a polynomial of k whether the conjecture is valid on all graphs of treewidth at most k. These upper bounds, which may be regarded as upper-bounds on the size of proofs/disproofs for these conjectures on the class of graphs of treewidth at most k, improve significantly on theoretical upper bounds obtained using previously available techniques.
|
|
| 6. |
- De Oliveira Oliveira, Mateus
(författare)
-
Subgraphs satisfying MSO properties on z-topologically orderable digraphs
- 2013
-
Ingår i: Parameterized and Exact Computation. - Cham : Springer. - 9783319038971 ; , s. 123-136
-
Konferensbidrag (refereegranskat)abstract
- We introduce the notion of z-topological orderings for digraphs. We prove that given a digraph G on n vertices admitting a z-topological ordering, together with such an ordering, one may count the number of subgraphs of G that at the same time satisfy a monadic second order formula φ and are the union of k directed paths, in time f(φ,k,z)·nO(k·z). Our result implies the polynomial time solvability of many natural counting problems on digraphs admitting z-topological orderings for constant values of z and k. Concerning the relationship between z-topological orderability and other digraph width measures, we observe that any digraph of directed path-width d has a z-topological ordering for z ≤ 2d + 1. On the other hand, there are digraphs on n vertices admitting a z-topological order for z = 2, but whose directed path-width is Θ(log n). Since graphs of bounded directed path-width can have both arbitrarily large undirected tree-width and arbitrarily large clique width, our result provides for the first time a suitable way of partially transposing metatheorems developed in the context of the monadic second order logic of graphs of constant undirected tree-width and constant clique width to the realm of digraph width measures that are closed under taking subgraphs and whose constant levels incorporate families of graphs of arbitrarily large undirected tree-width and arbitrarily large clique width.
|
|
| 7. |
- Diaz Andino, Fidel Ernesto, et al.
(författare)
-
Unitary Branching Programs: Learnability and Lower Bounds
- 2021
-
Ingår i: Proceedings of Machine Learning Research. - 2640-3498. ; 139, s. 297 -306
-
Konferensbidrag (refereegranskat)abstract
- Bounded width branching programs are a formalism that can be used to capture the notion of non-uniform constant-space computation. In this work, we study a generalized version of bounded width branching programs where instructions are defined by unitary matrices of bounded dimension. We introduce a new learning framework for these branching programs that leverages on a combination of local search techniques with gradient descent over Riemannian manifolds. We also show that gapped, read-once branching programs of bounded dimension can be learned with a polynomial number of queries in the presence of a teacher. Finally, we provide explicit near-quadratic size lower-bounds for bounded-dimension unitary branching programs, and exponential size lower-bounds for bounded-dimension read-once gapped unitary branching programs. The first lower bound is proven using a combination Neeiporuk's lower bound technique with classic results from algebraic geometry. The second lower bound is proven within the framework of communication complexity theory.
|
|
| 8. |
- Lingg, Jonas, et al.
(författare)
-
Learning from positive and negative examples : New proof for binary alphabets
- 2024
-
Ingår i: Information Processing Letters. - 0020-0190 .- 1872-6119. ; 183
-
Tidskriftsartikel (refereegranskat)abstract
- One of the most fundamental problems in computational learning theory is the problem of learning a finite automaton A consistent with a finite set P of positive examples and with a finite set N of negative examples. By consistency, we mean that A accepts all strings in P and rejects all strings in N. It is well known that this problem is NP-complete. In the literature, it is stated that NP-hardness holds even in the case of a binary alphabet. As a standard reference for this theorem, the work of Gold from 1978 is either cited or adapted. Nevertheless, the results in Gold's work are stated in terms of Mealy machines, and not in terms of deterministic finite automata (DFAs) as most commonly defined. As Mealy machines are equipped with an output function, they can be more compact than DFAs which accept the same language. We show that the adaptations of Gold's construction for Mealy machines stated in the literature have some issues, and provide a correct proof for the fact that the DFA-consistency problem for binary alphabets is NP-complete.
|
|
| 9. |
- Arrighi, Emmanuel, et al.
(författare)
-
Order Reconfiguration under Width Constraints
- 2023
-
Ingår i: Journal of Graph Algorithms and Applications. - 1526-1719. ; 27:6, s. 409-431
-
Tidskriftsartikel (refereegranskat)abstract
- In this work, we consider the following order reconfiguration problem: Given a graph G together with linear orders ω and ω′ of the vertices of G, can one transform ω into ω′ by a sequence of swaps of adjacent elements in such a way that, at each time step, the resulting linear order has cutwidth (pathwidth) at most k? We show that this problem always has an affirmative answer when the input linear orders ω and ω′ have cutwidth (pathwidth) of at most k/2. This result also holds in a weighted setting. Using this result, we establish a connection between two apparently unrelated problems: the reachability problem for two-letter string rewriting systems and the graph isomorphism problem for graphs of bounded cutwidth. This opens an avenue for the study of the famous graph isomorphism problem using techniques from term rewriting theory.
|
|
| 10. |
- Pelicer, Mateus Reinke, et al.
(författare)
-
Exclusive heavy quark-pair production in ultraperipheral collisions
- 2019
-
Ingår i: Physical Review D. - 2470-0010. ; 99:3
-
Tidskriftsartikel (refereegranskat)abstract
- In this article, we study the fully differential observables of the exclusive production of heavy (charm and bottom) quark pairs in high-energy ultraperipheral pA and AA collisions. In these processes, the nucleus A serves as an efficient source of the photon flux, while the QCD interaction of the produced heavy-quark pair with the target (p or A) proceeds via an exchange of gluons in a color singlet state, described by the gluon Wigner distribution. The corresponding predictions for differential cross sections were obtained by using the dipole S matrix in the McLerran-Venugopalan saturation model with impact parameter dependence for the nucleus target, and its recent generalization, for the proton target. Prospects of experimental constraints on the gluon Wigner distribution in this class of reactions are discussed.
|
|
