@article{AllanWeisserFischeretal.2013, author = {Allan, Eric and Weisser, Wolfgang W. and Fischer, Markus and Schulze, Ernst-Detlef and Weigelt, Alexandra and Roscher, Christiane and Baade, Jussi and Barnard, Romain L. and Bessler, Holger and Buchmann, Nina and Ebeling, Anne and Eisenhauer, Nico and Engels, Christof and Fergus, Alexander J. F. and Gleixner, Gerd and Gubsch, Marlen and Halle, Stefan and Klein, Alexandra-Maria and Kertscher, Ilona and Kuu, Annely and Lange, Markus and Le Roux, Xavier and Meyer, Sebastian T. and Migunova, Varvara D. and Milcu, Alexandru and Niklaus, Pascal A. and Oelmann, Yvonne and Pasalic, Esther and Petermann, Jana S. and Poly, Franck and Rottstock, Tanja and Sabais, Alexander C. W. and Scherber, Christoph and Scherer-Lorenzen, Michael and Scheu, Stefan and Steinbeiss, Sibylle and Schwichtenberg, Guido and Temperton, Vicky and Tscharntke, Teja and Voigt, Winfried and Wilcke, Wolfgang and Wirth, Christian and Schmid, Bernhard}, title = {A comparison of the strength of biodiversity effects across multiple functions}, series = {Oecologia}, volume = {173}, journal = {Oecologia}, number = {1}, publisher = {Springer}, address = {New York}, issn = {0029-8549}, doi = {10.1007/s00442-012-2589-0}, pages = {223 -- 237}, year = {2013}, abstract = {In order to predict which ecosystem functions are most at risk from biodiversity loss, meta-analyses have generalised results from biodiversity experiments over different sites and ecosystem types. In contrast, comparing the strength of biodiversity effects across a large number of ecosystem processes measured in a single experiment permits more direct comparisons. Here, we present an analysis of 418 separate measures of 38 ecosystem processes. Overall, 45 \% of processes were significantly affected by plant species richness, suggesting that, while diversity affects a large number of processes not all respond to biodiversity. We therefore compared the strength of plant diversity effects between different categories of ecosystem processes, grouping processes according to the year of measurement, their biogeochemical cycle, trophic level and compartment (above- or belowground) and according to whether they were measures of biodiversity or other ecosystem processes, biotic or abiotic and static or dynamic. Overall, and for several individual processes, we found that biodiversity effects became stronger over time. Measures of the carbon cycle were also affected more strongly by plant species richness than were the measures associated with the nitrogen cycle. Further, we found greater plant species richness effects on measures of biodiversity than on other processes. The differential effects of plant diversity on the various types of ecosystem processes indicate that future research and political effort should shift from a general debate about whether biodiversity loss impairs ecosystem functions to focussing on the specific functions of interest and ways to preserve them individually or in combination.}, language = {en} } @article{CaselFernauGaspersetal.2020, author = {Casel, Katrin and Fernau, Henning and Gaspers, Serge and Gras, Benjamin and Schmid, Markus L.}, title = {On the complexity of the smallest grammar problem over fixed alphabets}, series = {Theory of computing systems}, volume = {65}, journal = {Theory of computing systems}, number = {2}, publisher = {Springer}, address = {New York}, issn = {1432-4350}, doi = {10.1007/s00224-020-10013-w}, pages = {344 -- 409}, year = {2020}, abstract = {In the smallest grammar problem, we are given a word w and we want to compute a preferably small context-free grammar G for the singleton language {w} (where the size of a grammar is the sum of the sizes of its rules, and the size of a rule is measured by the length of its right side). It is known that, for unbounded alphabets, the decision variant of this problem is NP-hard and the optimisation variant does not allow a polynomial-time approximation scheme, unless P = NP. We settle the long-standing open problem whether these hardness results also hold for the more realistic case of a constant-size alphabet. More precisely, it is shown that the smallest grammar problem remains NP-complete (and its optimisation version is APX-hard), even if the alphabet is fixed and has size of at least 17. The corresponding reduction is robust in the sense that it also works for an alternative size-measure of grammars that is commonly used in the literature (i. e., a size measure also taking the number of rules into account), and it also allows to conclude that even computing the number of rules required by a smallest grammar is a hard problem. On the other hand, if the number of nonterminals (or, equivalently, the number of rules) is bounded by a constant, then the smallest grammar problem can be solved in polynomial time, which is shown by encoding it as a problem on graphs with interval structure. However, treating the number of rules as a parameter (in terms of parameterised complexity) yields W[1]-hardness. Furthermore, we present an O(3(vertical bar w vertical bar)) exact exponential-time algorithm, based on dynamic programming. These three main questions are also investigated for 1-level grammars, i. e., grammars for which only the start rule contains nonterminals on the right side; thus, investigating the impact of the "hierarchical depth" of grammars on the complexity of the smallest grammar problem. In this regard, we obtain for 1-level grammars similar, but slightly stronger results.}, language = {en} } @article{CaselDreierFernauetal.2020, author = {Casel, Katrin and Dreier, Jan and Fernau, Henning and Gobbert, Moritz and Kuinke, Philipp and Villaamil, Fernando S{\´a}nchez and Schmid, Markus L. and van Leeuwen, Erik Jan}, title = {Complexity of independency and cliquy trees}, series = {Discrete applied mathematics}, volume = {272}, journal = {Discrete applied mathematics}, publisher = {Elsevier}, address = {Amsterdam [u.a.]}, issn = {0166-218X}, doi = {10.1016/j.dam.2018.08.011}, pages = {2 -- 15}, year = {2020}, abstract = {An independency (cliquy) tree of an n-vertex graph G is a spanning tree of G in which the set of leaves induces an independent set (clique). We study the problems of minimizing or maximizing the number of leaves of such trees, and fully characterize their parameterized complexity. We show that all four variants of deciding if an independency/cliquy tree with at least/most l leaves exists parameterized by l are either Para-NP- or W[1]-hard. We prove that minimizing the number of leaves of a cliquy tree parameterized by the number of internal vertices is Para-NP-hard too. However, we show that minimizing the number of leaves of an independency tree parameterized by the number k of internal vertices has an O*(4(k))-time algorithm and a 2k vertex kernel. Moreover, we prove that maximizing the number of leaves of an independency/cliquy tree parameterized by the number k of internal vertices both have an O*(18(k))-time algorithm and an O(k 2(k)) vertex kernel, but no polynomial kernel unless the polynomial hierarchy collapses to the third level. Finally, we present an O(3(n) . f(n))-time algorithm to find a spanning tree where the leaf set has a property that can be decided in f (n) time and has minimum or maximum size.}, language = {en} } @article{HofmannZuefleShimizuetal.2019, author = {Hofmann, Alexander J. L. and Z{\"u}fle, Simon and Shimizu, Kohei and Schmid, Markus and Wessels, Vivien and J{\"a}ger, Lars and Altazin, Stephane and Ikegami, Keitaro and Khan, Motiur Rahman and Neher, Dieter and Ishii, Hisao and Ruhstaller, Beat and Br{\"u}tting, Wolfgang}, title = {Dipolar Doping of Organic Semiconductors to Enhance Carrier Injection}, series = {Physical review applied}, volume = {12}, journal = {Physical review applied}, number = {6}, publisher = {American Physical Society}, address = {College Park}, issn = {2331-7019}, doi = {10.1103/PhysRevApplied.12.064052}, pages = {11}, year = {2019}, abstract = {If not oriented perfectly isotropically, the strong dipole moment of polar organic semiconductor materials such as tris-(8-hydroxyquinolate)aluminum (Alq3) will lead to the buildup of a giant surface potential (GSP) and thus to a macroscopic dielectric polarization of the organic film. Despite this having been a known fact for years, the implications of such high potentials within an organic layer stack have only been studied recently. In this work, the influence of the GSP on hole injection into organic layers is investigated. Therefore, we apply a concept called dipolar doping to devices consisting of the prototypical organic materials N,N′-Di(1-naphthyl)-N,N′-diphenyl-(1,1′-biphenyl)-4,4′-diamine (NPB) as nonpolar host and Alq3 as dipolar dopant with different mixing ratios to tune the GSP. The mixtures are investigated in single-layer monopolar devices as well as bilayer metal/insulator/semiconductor structures. Characterization is done electrically using current-voltage (I-V) characteristics, impedance spectroscopy, and charge extraction by linearly increasing voltage and time of flight, as well as with ultraviolet photoelectron spectroscopy. We find a maximum in device performance for moderate to low doping concentrations of the polar species in the host. The observed behavior can be described on the basis of the Schottky effect for image-force barrier lowering, if the changes in the interface dipole, the carrier mobility, and the GSP induced by dipolar doping are taken into account.}, language = {en} }