Search results for "lemma"

Combinatorial proofs of two theorems of Lutz and Stull

2021

Recently, Lutz and Stull used methods from algorithmic information theory to prove two new Marstrand-type projection theorems, concerning subsets of Euclidean space which are not assumed to be Borel, or even analytic. One of the theorems states that if $K \subset \mathbb{R}^{n}$ is any set with equal Hausdorff and packing dimensions, then $$ \dim_{\mathrm{H}} π_{e}(K) = \min\{\dim_{\mathrm{H}} K,1\} $$ for almost every $e \in S^{n - 1}$. Here $π_{e}$ stands for orthogonal projection to $\mathrm{span}(e)$. The primary purpose of this paper is to present proofs for Lutz and Stull's projection theorems which do not refer to information theoretic concepts. Instead, they will rely on combinatori…

Algorithms for Anti-Powers in Strings

2018

Abstract A string S [ 1 , n ] is a power (or tandem repeat) of order k and period n / k if it can be decomposed into k consecutive equal-length blocks of letters. Powers and periods are fundamental to string processing, and algorithms for their efficient computation have wide application and are heavily studied. Recently, Fici et al. (Proc. ICALP 2016) defined an anti-power of order k to be a string composed of k pairwise-distinct blocks of the same length ( n / k , called anti-period). Anti-powers are a natural converse to powers, and are objects of combinatorial interest in their own right. In this paper we initiate the algorithmic study of anti-powers. Given a string S, we describe an op…

Facilitating terminology translation with target lemma annotations

2021

Most of the recent work on terminology integration in machine translation has assumed that terminology translations are given already inflected in forms that are suitable for the target language sentence. In day-to-day work of professional translators, however, it is seldom the case as translators work with bilingual glossaries where terms are given in their dictionary forms; finding the right target language form is part of the translation process. We argue that the requirement for apriori specified target language forms is unrealistic and impedes the practical applicability of previous work. In this work, we propose to train machine translation systems using a source-side data augmentatio…

A Quantum Lovasz Local Lemma

2012

The Lovasz Local Lemma (LLL) is a powerful tool in probability theory to show the existence of combinatorial objects meeting a prescribed collection of "weakly dependent" criteria. We show that the LLL extends to a much more general geometric setting, where events are replaced with subspaces and probability is replaced with relative dimension, which allows to lower bound the dimension of the intersection of vector spaces under certain independence conditions. Our result immediately applies to the k-QSAT problem: For instance we show that any collection of rank 1 projectors with the property that each qubit appears in at most $2^k/(e \cdot k)$ of them, has a joint satisfiable state. We then …

A Freely Available Morphological Analyzer, Disambiguator and Context Sensitive Lemmatizer for German

1998

In this paper we present Morphy, an integrated tool for German morphology, part-of-speech tagging and context-sensitive lemmatization. Its large lexicon of more than 320,000 word forms plus its ability to process German compound nouns guarantee a wide morphological coverage. Syntactic ambiguities can be resolved with a standard statistical part-of-speech tagger. By using the output of the tagger, the lemmatizer can determine the correct root even for ambiguous word forms. The complete package is freely available and can be downloaded from the World Wide Web.

Robust H;<inf>∞</inf> filtering for 2-D FM systems: A finite frequency approach

2012

This paper investigates the problem of robust H; ∞ filtering for uncertain two-dimensional (2-D) discrete systems in the Fornasini-Marchesini local state-space (FM LSS) model with polytopic uncertain parameters. The goal of the paper is to design filters such that the finite frequency (FF) H; ∞ norm of the filtering error system has a specified upper bound for all uncertainties. A generalized bounded real lemma (BRL) is first derived for FF H; ∞ performance analysis of nominal 2-D FM LSS systems, and then a method, in terms of solving optimization problems with LMI constraints, is presented for robust FF H; ∞ filter analysis and design. An illustrative example is given to show the improveme…

Caveolin 3, flotillin 1 and influenza virus hemagglutinin reside in distinct domains on the sarcolemma of skeletal myofibers.

2011

We examined the distribution of selected raft proteins on the sarcolemma of skeletal myofibers and the role of cholesterol environment in the distribution. Immunofluorescence staining showed that flotillin-1 and influenza hemagglutinin exhibited rafts that located in the domains deficient of the dystrophin glycoprotein complex, but the distribution patterns of the two proteins were different. Cholesterol depletion from the sarcolemma by means of methyl-β-cyclodextrin resulted in distorted caveolar morphology and redistribution of the caveolin 3 protein. Concomitantly, the water permeability of the sarcolemma increased significantly. However, cholesterol depletion did not reshuffle flotillin…

The forager's dilemma: food sharing and food defense as risk-sensitive foraging options.

2003

Although many variants of the hawk-dove game predict the frequency at which group foraging animals should compete aggressively, none of them can explain why a large number of group foraging animals share food clumps without any overt aggression. One reason for this shortcoming is that hawk-dove games typically consider only a single contest, while most group foraging situations involve opponents that interact repeatedly over discovered food clumps. The present iterated hawk-dove game predicts that in situations that are analogous to a prisoner's dilemma, animals should share the resources without aggression, provided that the number of simultaneously available food clumps is sufficiently la…

Cancellation, pumping and permutation in formal languages

1984

True V or not True V, That is the Question

2016

In this paper we intend to argue that: (1) the question `True V or not True V' is central to both the philosophical and mathematical investigations of the foundations of mathematics; (2) when posed within a framework in which set theory is seen as a science of objects, the question `True V or not True V' generates a dilemma each horn of which turns out to be unacceptable; (3) a plausible way out of the dilemma mentioned at (2) is provided by an approach to set theory according to which this is considered to be a science of structures.