Search results for "Data type"
showing 10 items of 1183 documents
A Loopless Generation of Bitstrings without p Consecutive Ones
2001
Let F n (p) be the set of all n-length bitstrings such that there are no p consecutive ls. F n (p) is counted with the pth order Fibonacci numbers and it may be regarded as the subsets of {1, 2,…, n} without p consecutive elements and bitstrings in F n (p) code a particular class of trees or compositions of an integer. In this paper we give a Gray code for F n (p) which can be implemented in a recursive generating algorithm, and finally in a loopless generating algorithm.
Orientation matters
2008
The optimal communication spanning tree (OCST) problem is a well known $\mathcal{NP}$-hard combinatorial optimization problem which seeks a spanning tree that satisfies all given communication requirements for minimal total costs. It has been shown that optimal solutions of OCST problems are biased towards the much simpler minimum spanning tree (MST) problem. Therefore, problem-specific representations for EAs like heuristic variants of edge-sets that are biased towards MSTs show high performance.In this paper, additional properties of optimal solutions for Euclidean variants of OCST problems are studied. Experimental results show that not only edges in optimal trees are biased towards low-…
Quantum Query Complexity for Some Graph Problems
2004
The paper [4] by H. Buhrman and R. de Wolf contains an impressive survey of solved and open problems in quantum query complexity, including many graph problems. We use recent results by A.Ambainis [1] to prove higher lower bounds for some of these problems. Some of our new lower bounds do not close the gap between the best upper and lower bounds. We prove in these cases that it is impossible to provide a better application of Ambainis’ technique for these problems.
Structured Frequency Algorithms
2015
B.A. Trakhtenbrot proved that in frequency computability (introduced by G. Rose) it is crucially important whether the frequency exceeds \(\frac{1}{2}\). If it does then only recursive sets are frequency-computable. If the frequency does not exceed \(\frac{1}{2}\) then a continuum of sets is frequency-computable. Similar results for finite automata were proved by E.B. Kinber and H. Austinat et al. We generalize the notion of frequency computability demanding a specific structure for the correct answers. We show that if this structure is described in terms of finite projective planes then even a frequency \(O(\frac{\sqrt{n}}{n})\) ensures recursivity of the computable set. We also show that …
CHARACTERS INDUCED FROM FULLY RAMIFIED SUBGROUPS
2001
Suppose that G is a finite π-separable group, let cf(G) be the space of complex class functions of G and let Irr(G) be the set of the irreducible complex characters of G. Let K be an arbitrary Hall...
The Structure Group and the Permutation Group of a Set-Theoretic Solution of the Quantum Yang–Baxter Equation
2021
We describe the left brace structure of the structure group and the permutation group associated to an involutive, non-degenerate set-theoretic solution of the quantum YangBaxter equation by using the Cayley graph of its permutation group with respect to its natural generating system. We use our descriptions of the additions in both braces to obtain new properties of the structure and the permutation groups and to recover some known properties of these groups in a more transparent way.
On periodic radical groups in which permutability is a transitive relation
2007
Abstract A group G is said to be a PT - group if permutability is a transitive relation in the set of all subgroups of G . Our purpose in this paper is to study PT -groups in the class of periodic radical groups satisfying min- p for all primes p .
On the Navarro–Willems conjecture for blocks of finite groups
2007
Abstract We prove that a set of characters of a finite group can only be the set of characters for principal blocks of the group at two different primes when the primes do not divide the group order. This confirms a conjecture of Navarro and Willems in the case of principal blocks.
A Criterion for Attaining the Welch Bounds with Applications for Mutually Unbiased Bases
2008
The paper gives a short introduction to mutually unbiased bases and the Welch bounds and demonstrates that the latter is a good technical tool to explore the former. In particular, a criterion for a system of vectors to satisfy the Welch bounds with equality is given and applied for the case of MUBs. This yields a necessary and sufficient condition on a set of orthonormal bases to form a complete system of MUBs. This condition takes an especially elegant form in the case of homogeneous systems of MUBs. We express some known constructions of MUBs in this form. Also it is shown how recently obtained results binding MUBs and some combinatorial structures (such as perfect nonlinear functions an…
Forbidden Factors and Fragment Assembly
2001
In this paper methods and results related to the notion of minimal forbidden words are applied to the fragment assembly problem. The fragment assembly problem can be formulated, in its simplest form, as follows: reconstruct a word w from a given set I of substrings (fragments ) of a word w . We introduce an hypothesis involving the set of fragments I and the maximal length m(w) of the minimal forbidden factors of w . Such hypothesis allows us to reconstruct uniquely the word w from the set I in linear time. We prove also that, if w is a word randomly generated by a memoryless source with identical symbol probabilities, m(w) is logarithmic with respect to the size of w . This result shows th…