Search

We consider subsequences with gap constraints, i. e., length-k subsequences p that can be embedded into a string w such that the induced gaps (i. e., the factors of w between the positions to which p is mapped to) satisfy given gap constraints gc = (C_1, C_2, …, C_{k-1}); we call p a gc-subsequence of w. In the case where the gap constraints gc are defined by lower and upper length bounds C_i = (L^-_i, L^+_i) ∈ ℕ² and/or regular languages C_i ∈ REG, we prove tight (conditional on the orthogonal vectors (OV) hypothesis) complexity bounds for checking whether a given p is a gc-subsequence of a string w. We also consider the whole set of all gc-subsequences of a string, and investigate the complexity of the universality, equivalence and containment problems for these sets of gc-subsequences.

We consider the longest common subsequence problem in the context of subsequences with gap constraints. In particular, following Day et al. 2022, we consider the setting when the distance (i. e., the gap) between two consecutive symbols of the subsequence has to be between a lower and an upper bound (which may depend on the position of those symbols in the subsequence or on the symbols bordering the gap) as well as the case where the entire subsequence is found in a bounded range (defined by a single upper bound), considered by Kosche et al. 2022. In all these cases, we present effcient algorithms for determining the length of the longest common constrained subsequence between two given strings.

Simon’s congruence ∼_k is a relation on words defined by Imre Simon in the 1970s and intensely studied since then. This congruence was initially used in connection to piecewise testable languages, but also found many applications in, e.g., learning theory, databases theory, or linguistics. The ∼_k-relation is defined as follows: two words are ∼_k-congruent if they have the same set of subsequences of length at most k. A long standing open problem, stated already by Simon in his initial works on this topic, was to design an algorithm which computes, given two words s and t, the largest k for which s∼_k t. We propose the first algorithm solving this problem in linear time O(|s|+|t|) when the input words are over the integer alphabet {1,…,|s|+|t|} (or other alphabets which can be sorted in linear time). Our approach can be extended to an optimal algorithm in the case of general alphabets as well. To achieve these results, we introduce a novel data-structure, called Simon-Tree, which allows us to construct a natural representation of the equivalence classes induced by ∼_k on the set of suffixes of a word, for all k ≥ 1. We show that such a tree can be constructed for an input word in linear time. Then, when working with two words s and t, we compute their respective Simon-Trees and efficiently build a correspondence between the nodes of these trees. This correspondence, which can also be constructed in linear time O(|s|+|t|), allows us to retrieve the largest k for which s∼_k t.

In this paper we provide an overview of a series of recent results regarding algorithms for searching for subsequences in words or for the analysis of the sets of subsequences occurring in a word., Comment: This is a revised version of the paper with the same title which appeared in the Proceedings of NCMA 2022, EPTCS 367, 2022, pp. 11-27 (DOI: 10.4204/EPTCS.367.2). The revision consists in citing a series of relevant references which were not covered in the initial version, and commenting on how they relate to the results we survey. arXiv admin note: text overlap with arXiv:2206.13896

In this paper, we consider a variant of the classical algorithmic problem of checking whether a given word $v$ is a subsequence of another word $w$. More precisely, we consider the problem of deciding, given a number $p$ (defining a range-bound) and two words $v$ and $w$, whether there exists a factor $w[i:i+p-1]$ (or, in other words, a range of length $p$) of $w$ having $v$ as subsequence (i.\,e., $v$ occurs as a subsequence in the bounded range $w[i:i+p-1]$). We give matching upper and lower quadratic bounds for the time complexity of this problem. Further, we consider a series of algorithmic problems in this setting, in which, for given integers $k$, $p$ and a word $w$, we analyse the set $p$-Subseq$_{k}(w)$ of all words of length $k$ which occur as subsequence of some factor of length $p$ of $w$. Among these, we consider the $k$-universality problem, the $k$-equivalence problem, as well as problems related to absent subsequences. Surprisingly, unlike the case of the classical model of subsequences in words where such problems have efficient solutions in general, we show that most of these problems become intractable in the new setting when subsequences in bounded ranges are considered. Finally, we provide an example of how some of our results can be applied to subsequence matching problems for circular words., Comment: Extended version of a paper which will appear in the proceedings of the 16th International Conference on Reachability Problems, RP 2022

We consider subsequences with gap constraints, i.e., length-k subsequences p that can be embedded into a string w such that the induced gaps (i.e., the factors of w between the positions to which p is mapped to) satisfy given gap constraints $gc = (C_1, C_2, ..., C_{k-1})$; we call p a gc-subsequence of w. In the case where the gap constraints gc are defined by lower and upper length bounds $C_i = (L^-_i, L^+_i) \in \mathbb{N}^2$ and/or regular languages $C_i \in REG$, we prove tight (conditional on the orthogonal vectors (OV) hypothesis) complexity bounds for checking whether a given p is a gc-subsequence of a string w. We also consider the whole set of all gc-subsequences of a string, and investigate the complexity of the universality, equivalence and containment problems for these sets of gc-subsequences.

Immune checkpoint inhibitors are used to treat numerous malignancies but may be associated with severe adverse events. Bullous dermatoses, chiefly bullous pemphigoid (BP), are potentially progressive adverse events that cause blistering skin lesions and may involve a significant body surface area. Herein, we report an 87-year-old man with urothelial cell carcinoma undergoing atezolizumab treatment who presented with an acute-onset blistering eruption. Biopsy revealed a subepidermal bulla, direct immunofluorescence revealed linear IgG and C3 deposits at the dermal-epidermal junction, and serum studies revealed elevated levels of antibodies to BP180 and BP230. Anti-PD-L1-induced BP was diagnosed, immunotherapy was withheld, and he was treated with oral doxycycline with niacinamide and clobetasol ointment. He restarted atezolizumab and has successfully received four cycles (every 3 weeks) while continuing this BP treatment regimen. A literature review revealed eight other cases of anti-PD-L1-induced bullous disorders. The incidence of bullous dermatoses with anti-PD-1/anti-PD-L1 agents combined is 1%, whereas the reported incidence for anti-PD-L1 agents alone ranges from 1.3-5%, raising concerns for a higher overall risk. In addition to our case, only one other case reported successful resumption of immunotherapy. Early control and management of immunotherapy-induced BP may reduce complications and prevent treatment discontinuation.

Checkpoint inhibitor immunotherapy, including ipilimumab and nivolumab, is associated with numerous immune-related adverse events including dermatitis, pruritus, hepatitis, diarrhea, and hypophysitis. As the number of patients undergoing immunotherapy treatment increases, however, rare and unusual immune-related adverse events are observed. Many of these resemble known autoimmune phenomenon, such as subacute lupus erythematosus and myositis. Herein, we report a patient with metastatic serous ovarian carcinoma undergoing treatment with combination ipilimumab and nivolumab who developed subacute cutaneous lupus erythematosus (SCLE). Recent case reports have documented SCLE as a novel immune-related adverse event. In our case, she was able to successfully restart immunotherapy after a course of oral corticosteroids and maintenance oral hydroxychloroquine and topical corticosteroid therapy.

Immune checkpoint inhibitors are used to treat numerous malignancies but may be associated with severe adverse events. Bullous dermatoses, chiefly bullous pemphigoid (BP), are potentially progressive adverse events that cause blistering skin lesions and may involve a significant body surface area. Herein, we report an 87-year-old man with urothelial cell carcinoma undergoing atezolizumab treatment who presented with an acute-onset blistering eruption. Biopsy revealed a subepidermal bulla, direct immunofluorescence revealed linear IgG and C3 deposits at the dermal-epidermal junction, and serum studies revealed elevated levels of antibodies to BP180 and BP230. Anti-PD-L1-induced BP was diagnosed, immunotherapy was withheld, and he was treated with oral doxycycline with niacinamide and clobetasol ointment. He restarted atezolizumab and has successfully received four cycles (every 3 weeks) while continuing this BP treatment regimen. A literature review revealed eight other cases of anti-PD-L1-induced bullous disorders. The incidence of bullous dermatoses with anti-PD-1/anti-PD-L1 agents combined is 1%, whereas the reported incidence for anti-PD-L1 agents alone ranges from 1.3-5%, raising concerns for a higher overall risk. In addition to our case, only one other case reported successful resumption of immunotherapy. Early control and management of immunotherapy-induced BP may reduce complications and prevent treatment discontinuation.

Checkpoint inhibitor immunotherapy, including ipilimumab and nivolumab, is associated with numerous immune-related adverse events including dermatitis, pruritus, hepatitis, diarrhea, and hypophysitis. As the number of patients undergoing immunotherapy treatment increases, however, rare and unusual immune-related adverse events are observed. Many of these resemble known autoimmune phenomenon, such as subacute lupus erythematosus and myositis. Herein, we report a patient with metastatic serous ovarian carcinoma undergoing treatment with combination ipilimumab and nivolumab who developed subacute cutaneous lupus erythematosus (SCLE). Recent case reports have documented SCLE as a novel immune-related adverse event. In our case, she was able to successfully restart immunotherapy after a course of oral corticosteroids and maintenance oral hydroxychloroquine and topical corticosteroid therapy.

A word u is a subsequence of another word w if u can be obtained from w by deleting some of its letters. In the early 1970s, Imre Simon defined the relation ?_k (called now Simon-Congruence) as follows: two words having exactly the same set of subsequences of length at most k are ?_k-congruent. This relation was central in defining and analysing piecewise testable languages, but has found many applications in areas such as algorithmic learning theory, databases theory, or computational linguistics. Recently, it was shown that testing whether two words are ?_k-congruent can be done in optimal linear time. Thus, it is a natural next step to ask, for two words w and u which are not ?_k-equivalent, what is the minimal number of edit operations that we need to perform on w in order to obtain a word which is ?_k-equivalent to u. In this paper, we consider this problem in a setting which seems interesting: when u is a k-subsequence universal word. A word u with alph(u) = ? is called k-subsequence universal if the set of subsequences of length k of u contains all possible words of length k over ?. As such, our results are a series of efficient algorithms computing the edit distance from w to the language of k-subsequence universal words.

An absent factor of a string $w$ is a string $u$ which does not occur as a contiguous substring (a.k.a. factor) inside $w$. We extend this well-studied notion and define absent subsequences: a string $u$ is an absent subsequence of a string $w$ if $u$ does not occur as subsequence (a.k.a. scattered factor) inside $w$. Of particular interest to us are minimal absent subsequences, i.e., absent subsequences whose every subsequence is not absent, and shortest absent subsequences, i.e., absent subsequences of minimal length. We show a series of combinatorial and algorithmic results regarding these two notions. For instance: we give combinatorial characterisations of the sets of minimal and, respectively, shortest absent subsequences in a word, as well as compact representations of these sets; we show how we can test efficiently if a string is a shortest or minimal absent subsequence in a word, and we give efficient algorithms computing the lexicographically smallest absent subsequence of each kind; also, we show how a data structure for answering shortest absent subsequence-queries for the factors of a given string can be efficiently computed., Comment: An extended abstract appeared in the proceedings of the 15th International Conference on Reachability Problems RP2021

Semi-online algorithms that are allowed to perform a bounded amount of repacking achieve guaranteed good worst-case behaviour in a more realistic setting. Most of the previous works focused on minimization problems that aim to minimize some costs. In this work, we study maximization problems that aim to maximize their profit. We mostly focus on a class of problems that we call choosing problems, where a maximum profit subset of a set objects has to be maintained. Many known problems, such as Knapsack, MaximumIndependentSet and variations of these, are part of this class. We present a framework for choosing problems that allows us to transfer offline $\alpha$-approximation algorithms into $(\alpha-epsilon)$-competitive semi-online algorithms with amortized migration $O(1/\epsilon)$. Moreover we complement these positive results with lower bounds that show that our results are tight in the sense that no amortized migration of $o(1/\epsilon)$ is possible., Comment: CIE 2021

A word $u$ is a subsequence of another word $w$ if $u$ can be obtained from $w$ by deleting some of its letters. The word $w$ with alph$(w)=\Sigma$ is called $k$-subsequence universal if the set of subsequences of length $k$ of $w$ contains all possible words of length $k$ over $\Sigma$. We propose a series of efficient algorithms computing the minimal number of edit operations (insertion, deletion, substitution) one needs to apply to a given word in order to reach the set of $k$-subsequence universal words.

Simon's congruence $\sim_k$ is defined as follows: two words are $\sim_k$-equivalent if they have the same set of subsequences of length at most $k$. We propose an algorithm which computes, given two words $s$ and $t$, the largest $k$ for which $s\sim_k t$. Our algorithm runs in linear time $O(|s|+|t|)$ when the input words are over the integer alphabet $\{1,\ldots,|s|+|t|\}$ (or other alphabets which can be sorted in linear time). This approach leads to an optimal algorithm in the case of general alphabets as well. Our results are based on a novel combinatorial approach and a series of efficient data structures.

We consider the relaxed online strip packing problem, where rectangular items arrive online and have to be packed into a strip of fixed width such that the packing height is minimized. Thereby, repacking of previously packed items is allowed. The amount of repacking is measured by the migration factor, defined as the total size of repacked items divided by the size of the arriving item. First, we show that no algorithm with constant migration factor can produce solutions with asymptotic ratio better than 4/3. Against this background, we allow amortized migration, i.e. to save migration for a later time step. As a main result, we present an AFPTAS with asymptotic ratio 1 + O(epsilon) for any epsilon > 0 and amortized migration factor polynomial in 1/epsilon. To our best knowledge, this is the first algorithm for online strip packing considered in a repacking model.

We consider the relaxed online strip packing problem, where rectangular items arrive online and have to be packed into a strip of fixed width such that the packing height is minimized. Thereby, repacking of previously packed items is allowed. The amount of repacking is measured by the migration factor, defined as the total size of repacked items divided by the size of the arriving item. First, we show that no algorithm with constant migration factor can produce solutions with asymptotic ratio better than 4/3. Against this background, we allow amortized migration, i.e. to save migration for a later time step. As a main result, we present an AFPTAS with asymptotic ratio 1 + O(epsilon) for any epsilon > 0 and amortized migration factor polynomial in 1/epsilon. To our best knowledge, this is the first algorithm for online strip packing considered in a repacking model.

We consider the relaxed online strip packing problem: Rectangular items arrive online and have to be packed without rotations into a strip of fixed width such that the packing height is minimized. Thereby, repacking of previously packed items is allowed. The amount of repacking is measured by the migration factor, defined as the total size of repacked items divided by the size of the arriving item. First, we show that no algorithm with constant migration factor can produce solutions with asymptotic ratio better than 4/3. Against this background, we allow amortized migration, i.e. to save migration for a later time step. As a main result, we present an AFPTAS with asymptotic ratio $1 + \mathcal{O}(\epsilon)$ for any $\epsilon > 0$ and amortized migration factor polynomial in $1 / \epsilon$. To our best knowledge, this is the first algorithm for online strip packing considered in a repacking model., Comment: An extended abstract of the paper has been published in APPROX 2017

BACKGROUND: There is evidence that selenium levels are relatively low in Europe and may be falling. Low levels of selenium or low activity of some of the enzymes dependent on selenium have been associated with asthma. METHODS: The GA(2)LEN network has organized a multicentre case-control study in Europe to assess the relation of plasma selenium to asthma. The network compared 569 cases in 14 European centres with a diagnosis of asthma and reporting asthma symptoms in the last 12 months with 576 controls from the same centres with no diagnosis of asthma and no asthmatic symptoms in the last 12 months. RESULTS: All cases and controls were selected from the same population defined by age and place of residence. Mean plasma selenium concentrations among the controls ranged from 116.3 microg/l in Palermo to 67.7 microg/l in Vienna and 56.1 microg/l among the children in Oslo. Random effects meta-analysis of the results from the centres showed no overall association between asthma and plasma selenium [odds ratio (OR)/10 microg/l increase in plasma selenium: 1.04; 95% confidence interval (CI): 0.89-1.21] though there was a significantly protective effect in Lodz (OR: 0.48; 95% CI: 0.29-0.78) and a marginally significant adverse effect in Amsterdam (OR: 1.68; 95% CI: 0.98-2.90) and Ghent (OR: 1.35; 95% CI: 1.03-1.77). CONCLUSION: This study does not support a role for selenium in protection against asthma, but effect modification and confounding cannot be ruled out.

NV 20160209

Suelos. El orden Alfisol en la isla Gran Canaria, por J. Sánchez Días, A . Guerra Delgado y E. Fernández Caldas.-- Estudio edáfico del sector J abalcuz-Los Villares. li. Estudio mineralógico de la fracción arena gruesa (2-0,2 mm.) por C. Dorronsoro, J. Aguilar y C. Antolín.-- Estudio edáfico del sector Jabalcuz-Los Villares. III. Estudio micromorfologico, por J . Aguilar, C. Dorronsoro y C. Antolin.-- Suelos fersialíticos sobre lapillis basálticos. II. Características micromorfológicas. Interpretación y clasificación, por A. Rodríguez Rodríguez, M. L. Tejedor Salguero y E. Fernández Caldas.-- Suelos volcánicos españoles. VIII. Campo de Calatrava (Ciudad Real). Mineralogía de las fracciones arena y limo, por C. Vizcayno M., T. Alei.randre y A. Pinilla. Estudio de la fracción arcilla de un Paleargid xerálfico del campo de Cartagena, por L. J. Alías, R. Ortiz y J. Albaladejo.-- Nuevos datos sobre la influencia de la vegetación en la formación del suelo en Galicia.III. Aportes por hojarasca, pérdidas por drenaje y escorrentía. Balance del agua y los elementos a través del suelo, por R. Mª Calvo de Anta, A. Paz González y F. Díaz-Fierros Viqueira.-- Caracterización de las sustancias húmicas en la fracción humina de los suelos, por G. Almendros, A. Polo y E. Dorado. Estudio de un suelo pseudogley de la provincia de Burgos. Distribución de ácidos húmicos en las diferentes fracciones físicas, por S . González G. y S . Bruckert. An approach to the clas-sification of agricultura! and nonagricultural soil evaluation systems, por D. de la Rosa and V . W. Carlise.-- Sobre la coexistencia de los procesos edáficos y geomorfológicos , por E. Barahona Fernández y J. Linares González.-- Estudio de la textura superficial de granos de cuarzo procedentes de granito por medio del micrnscopio electrónico de barrido, por M. T. Martín Patino, J. Casas Sáinz de Aja y J. A. Medina.-- Sorción interlaminar de aminas alifáticas en minerales interestratificados mica-montmorillonita por A. Ruiz Am

Vorlageform des Erscheinungsvermerks: Lauban, Gedruckt mit Scharfischen Schriften.

For this doctorate study several experiments with seagrasses were planned and conducted on the German North Sea island Sylt from 2002 till 2004. The results show that seedlings from both seagrass species grew better at weaker current velocities than at stronger velocities, with Zostera noltii being able to withstand higher velocities longer than Z. marina. The lugworm Arenicola marina negatively influenced Z. noltii, but did not influence Z. marina. The combination of higher current velocities and lugworm presence was particularly bad for Z. noltii. Both seagrass species grew better in the upper eulittoral compared with the lower eulittoral. In the donor population, Z. marina seedlings emerged 3-4 weeks earlier at the sediment surface than Z. noltii seedlings. Despite this Z. noltii seedlings had nearly the same shoot length by late June 2004. Neither seagrass species transferred carbon or nitrogen from the leaves to the roots/rhizomes with the onset of winter. The phosphate concentration in the porewater of the seagrass meadows might be limiting seagrass growth but ammonium and silicate concentrations are not limiting.

For this doctorate study several experiments with seagrasses were planned and conducted on the German North Sea island Sylt from 2002 till 2004. The results show that seedlings from both seagrass species grew better at weaker current velocities than at stronger velocities, with Zostera noltii being able to withstand higher velocities longer than Z. marina. The lugworm Arenicola marina negatively influenced Z. noltii, but did not influence Z. marina. The combination of higher current velocities and lugworm presence was particularly bad for Z. noltii. Both seagrass species grew better in the upper eulittoral compared with the lower eulittoral. In the donor population, Z. marina seedlings emerged 3-4 weeks earlier at the sediment surface than Z. noltii seedlings. Despite this Z. noltii seedlings had nearly the same shoot length by late June 2004. Neither seagrass species transferred carbon or nitrogen from the leaves to the roots/rhizomes with the onset of winter. The phosphate concentration in the porewater of the seagrass meadows might be limiting seagrass growth but ammonium and silicate concentrations are not limiting.

Vorlageform des Erscheinungsvermerks: Lauban, Gedruckt mit Scharfischen Schriften.