Search

This paper studies wave localisation in chains of finitely many resonators. There is an extensive theory predicting the existence of localised modes induced by defects in infinitely periodic systems. This work extends these principles to finite-sized systems. We consider finite systems of subwavelength resonators arranged in dimers that have a geometric defect in the structure. This is a classical wave analogue of the Su-Schrieffer-Heeger model. We prove the existence of a spectral gap for defectless finite dimer structures and find a direct relationship between eigenvalues being within the spectral gap and the localisation of their associated eigenmode. Then we show the existence and uniqueness of an eigenvalue in the gap in the defect structure, proving the existence of a unique localised interface mode. To the best of our knowledge, our method, based on Chebyshev polynomials, is the first to characterise quantitatively the localised interface modes in systems of finitely many resonators., Comment: 21 pages

The aim of this article is to advance the field of metamaterials by proposing formulas for the design of high-contrast metamaterials with prescribed subwavelength defect mode eigenfrequencies. This is achieved in two settings: (i) design of non-hermitian static materials and (ii) design of instantly changing non-hermitian time-dependent materials. The design of static materials is achieved via characterizing equations for the defect mode eigenfrequencies in the setting of a defected dimer material. These characterizing equations are the basis for obtaining formulas for the material parameters of the defect which admit given defect mode eigenfrequencies. Explicit formulas are provided in the setting of one and two given defect mode eigenfrequencies in the setting of a defected chain of dimers. In the time-dependent case, we first analyze the influence of time-boundaries on the subwavelength solutions. We find that subwavelength solutions are preserved if and only if the material parameters satisfy a temporal Snell's law across the time boundary. The same result also identifies the change of the time-frequencies uniquely. Combining this result with those on the design of static materials, we obtain an explicit formula for the material design of instantly changing defected dimer materials which admit subwavelength modes with prescribed time-dependent defect mode eigenfrequency. Finally, we use this formula to create materials which admit spatio-temporally localized defect modes., Comment: v.2: Corrected metadata

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.

We dedicate this paper to the topological analysis of subwavelength solutions in Floquet metamaterials. This work should be considered as a basis for further investigation on whether topological properties of the bulk materials are linked to the occurrence of edge modes. The subwavelength solutions being described by a periodically parameterized time-periodic linear ordinary differential equation $\left\{\frac{d}{dt}X = A_\alpha(t)X\right\}_{\alpha \in \mathbb{T}^d}$, we put ourselves in the general setting of periodically parameterized time-periodic linear ordinary differential equations and introduce a way to (topologically) classify a Floquet normal form $F,~P$ of the associated fundamental solution $\left\{X_\alpha(t) = P(\alpha,t)\exp(tF_\alpha)\right\}_{\alpha \in \mathbb{T}^d}$. This is achieved by analysing the topological properties of the eigenvalues and eigenvectors of the monodromy matrix $X_\alpha(T)$ and the Lyapunov transformation $P(\alpha,t)$. The corresponding topological invariants can then be applied to the setting of Floquet metamaterials. In this paper these general results are considered in the case of honeycomb Floquet metamaterials. We provide two interesting examples of topologically non-trivial time-modulated honeycomb structures.

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.

Our aim in this paper is twofold. Firstly, we develop a new asymptotic theory for Floquet exponents. We consider a linear system of differential equations with a time-periodic coefficient matrix. Assuming that the coefficient matrix depends analytically on a small parameter, we derive a full asymptotic expansion of its Floquet exponents. Based on this, we prove that only the constant order Floquet exponents of multiplicity higher than one will be perturbed linearly. The required multiplicity can be achieved via folding of the system through certain choices of the periodicity of the coefficient matrix. Secondly, we apply such an asymptotic theory for the analysis of Floquet metamaterials. We provide a characterization of asymptotic exceptional points for a pair of subwavelength resonators with time-dependent material parameters. We prove that asymptotic exceptional points are obtained if the frequency components of the perturbations fulfill a certain ratio, which is determined by the geometry of the dimer of subwavelength resonators.

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: 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