Search results for "combinatoric"
showing 10 items of 1776 documents
Computation of Yvon-Villarceau circles on Dupin cyclides and construction of circular edge right triangles on tori and Dupin cyclides
2014
Ring Dupin cyclides are non-spherical algebraic surfaces of degree four that can be defined as the image by inversion of a ring torus. They are interesting in geometric modeling because: (1) they have several families of circles embedded on them: parallel, meridian, and Yvon-Villarceau circles, and (2) they are characterized by one parametric equation and two equivalent implicit ones, allowing for better flexibility and easiness of use by adopting one representation or the other, according to the best suitability for a particular application. These facts motivate the construction of circular edge triangles lying on Dupin cyclides and exhibiting the aforementioned properties. Our first contr…
Descriptive Complexity, Lower Bounds and Linear Time
1999
This paper surveys two related lines of research: Logical characterizations of (non-deterministic) linear time complexity classes, and non-expressibility results concerning sublogics of existential second-order logic. Starting from Fagin’s fundamental work there has been steady progress in both fields with the effect that the weakest logics that are used in characterizations of linear time complexity classes are closely related to the strongest logics for which inexpressibility proofs for concrete problems have been obtained. The paper sketches these developments and highlights their connections as well as the obstacles that prevent us from closing the remaining gap between both kinds of lo…
How Low Can Approximate Degree and Quantum Query Complexity Be for Total Boolean Functions?
2012
It has long been known that any Boolean function that depends on n input variables has both degree and exact quantum query complexity of Omega(log n), and that this bound is achieved for some functions. In this paper we study the case of approximate degree and bounded-error quantum query complexity. We show that for these measures the correct lower bound is Omega(log n / loglog n), and we exhibit quantum algorithms for two functions where this bound is achieved.
Equivalence closure in the two-variable guarded fragment
2015
We consider the satisfiability and finite satisfiability problems for the extension of the two-variable guarded fragment in which an equivalence closure operator can be applied to two distinguished binary predicates. We show that the satisfiability and finite satisfiability problems for this logic are 2-ExpTime-complete. This contrasts with an earlier result that the corresponding problems for the full two-variable logic with equivalence closures of two binary predicates are 2-NExpTime-complete.
Gray visiting Motzkins
2002
We present the first Gray code for Motzkin words and their generalizations: k colored Motzkin words and Schroder words. The construction of these Gray codes is based on the observation that a k colored Motzkin word is the shuffle of a Dyck word by a k-ary variation on a trajectory which is a combination. In the final part of the paper we give some algorithmic considerations and other possible applications of the techniques introduced here.
Rational irreducible characters and rational conjugacy classes in finite groups
2007
We prove that a finite group G G has two rational-valued irreducible characters if and only if it has two rational conjugacy classes, and determine the structure of any such group. Along the way we also prove a conjecture of Gow stating that any finite group of even order has a non-trivial rational-valued irreducible character of odd degree.
Complex group algebras of finite groups: Brauer’s Problem 1
2005
Brauer’s Problem 1 asks the following: what are the possible complex group algebras of finite groups? It seems that with the present knowledge of representation theory it is not possible to settle this question. The goal of this paper is to announce a partial solution to this problem. We conjecture that if the complex group algebra of a finite group does not have more than a fixed number m m of isomorphic summands, then its dimension is bounded in terms of m m . We prove that this is true for every finite group if it is true for the symmetric groups.
The absolute center of a unicyclic network
1989
Abstract A unicyclic network is one generalization of a tree network. In this paper we examine the problem of finding an absolute center of a unicyclic network. We show that this problem can be solved in linear time with respect to the number of vertices in the network.
Some subgroup embeddings in finite groups: A mini review
2015
[EN] In this survey paper several subgroup embedding properties related to some types of permutability are introduced and studied. ª 2014 Production and hosting by Elsevier B.V. on behalf of Cairo University
Protein data condensation for effective quaternary structure classification
2007
Many proteins are composed of two or more subunits, each associated with different polypeptide chains. The number and the arrangement of subunits forming a protein are referred to as quaternary structure. The quaternary structure of a protein is important, since it characterizes the biological function of the protein when it is involved in specific biological processes. Unfortunately, quaternary structures are not trivially deducible from protein amino acid sequences. In this work, we propose a protein quaternary structure classification method exploiting the functional domain composition of proteins. It is based on a nearest neighbor condensation technique in order to reduce both the porti…