Search results for "102"
showing 10 items of 2892 documents
Neighbor-Distinguishing k-tuple Edge-Colorings of Graphs
2009
AbstractThis paper studies proper k-tuple edge-colorings of graphs that distinguish neighboring vertices by their sets of colors. Minimum numbers of colors for such colorings are determined for cycles, complete graphs and complete bipartite graphs. A variation in which the color sets assigned to edges have to form cyclic intervals is also studied and similar results are given.
Elements of Language Theory
1988
In this chapter we shall review the mathematical and computer science background on which the presentation in this book is based. We shall discuss the elements of discrete mathematics and formal language theory, emphasizing those issues that are of importance from the point of view of context-free parsing. We shall devote a considerable part of this chapter to matters such as random access machines and computational complexity. These will be relevant later when we derive efficient algorithms for parsing theoretic problems or prove lower bounds for the complexity of these problems. In this chapter we shall also discuss a general class of formal language descriptors called “rewriting systems”…
Debates with Small Transparent Quantum Verifiers
2014
We study a model where two opposing provers debate over the membership status of a given string in a language, trying to convince a weak verifier whose coins are visible to all. We show that the incorporation of just two qubits to an otherwise classical constant-space verifier raises the class of debatable languages from at most NP to the collection of all Turing-decidable languages (recursive languages). When the verifier is further constrained to make the correct decision with probability 1, the corresponding class goes up from the regular languages up to at least E.
PT Symmetry and Weyl Asymptotics
2012
For a class of PT-symmetric operators with small random perturbations, the eigenvalues obey Weyl asymptotics with probability close to 1. Consequently, when the principal symbol is nonreal, there are many nonreal eigenvalues.
Permutability of injectors with a central socle in a finite solvable group
2017
In response to an Open Question of Doerk and Hawkes [5, IX Section 3, page 615], we shall show that if Zπ is the Fitting class formed by the finite solvable groups whose π-socle is central (where π is a set of prime numbers), then the Zπ-injectors of a finite solvable group G permute with the members of a Sylow basis in G. The proof depends on the properties of certain extraspecial groups [4].
Overlapping self-affine sets of Kakeya type
2009
We compute the Minkowski dimension for a family of self-affine sets on the plane. Our result holds for every (rather than generic) set in the class. Moreover, we exhibit explicit open subsets of this class where we allow overlapping, and do not impose any conditions on the norms of the linear maps. The family under consideration was inspired by the theory of Kakeya sets.
Radial symmetry of minimizers to the weighted Dirichlet energy
2020
AbstractWe consider the problem of minimizing the weighted Dirichlet energy between homeomorphisms of planar annuli. A known challenge lies in the case when the weight λ depends on the independent variable z. We prove that for an increasing radial weight λ(z) the infimal energy within the class of all Sobolev homeomorphisms is the same as in the class of radially symmetric maps. For a general radial weight λ(z) we establish the same result in the case when the target is conformally thin compared to the domain. Fixing the admissible homeomorphisms on the outer boundary we establish the radial symmetry for every such weight.
The expressive power of the shuffle product
2010
International audience; There is an increasing interest in the shuffle product on formal languages, mainly because it is a standard tool for modeling process algebras. It still remains a mysterious operation on regular languages.Antonio Restivo proposed as a challenge to characterize the smallest class of languages containing the singletons and closed under Boolean operations, product and shuffle. This problem is still widely open, but we present some partial results on it. We also study some other smaller classes, including the smallest class containing the languages composed of a single word of length 2 which is closed under Boolean operations and shuffle by a letter (resp. shuffle by a l…
Fast Matrix Multiplication
2015
Until a few years ago, the fastest known matrix multiplication algorithm, due to Coppersmith and Winograd (1990), ran in time O(n2.3755). Recently, a surge of activity by Stothers, Vassilevska-Williams, and Le~Gall has led to an improved algorithm running in time O(n2.3729). These algorithms are obtained by analyzing higher and higher tensor powers of a certain identity of Coppersmith and Winograd. We show that this exact approach cannot result in an algorithm with running time O(n2.3725), and identify a wide class of variants of this approach which cannot result in an algorithm with running time $O(n^{2.3078}); in particular, this approach cannot prove the conjecture that for every e > 0, …
Duality theory for multi-marginal optimal transport with repulsive costs in metric spaces
2018
In this paper we extend the duality theory of the multi-marginal optimal transport problem for cost functions depending on a decreasing function of the distance (not necessarily bounded). This class of cost functions appears in the context of SCE Density Functional Theory introduced in "Strong-interaction limit of density-functional theory" by M. Seidl.