Search results for " Computer Science"
showing 10 items of 3983 documents
An efficient Gray code algorithm for generating all permutations with a given major index
2014
Abstract In Effler and Ruskey (2003) [1] the authors give an algorithm, which appears to be CAT, for generating permutations with a given major index. In the present paper we give a new algorithm for generating a Gray code for subexcedant sequences. We show that this algorithm is CAT and modify it into a CAT generating algorithm for a Gray code for permutations with a given major index.
On the type of partial t-spreads in finite projective spaces
1985
AbstractA partial t-spread in a projective space P is a set of mutually skew t-dimensional subspaces of P. In this paper, we deal with the question, how many elements of a partial spread L can be contained in a given d-dimensional subspace of P. Our main results run as follows. If any d-dimensional subspace of P contains at least one element of L, then the dimension of P has the upper bound d−1+(d/t). The same conclusion holds, if no d-dimensional subspace contains precisely one element of L. If any d-dimensional subspace has the same number m>0 of elements of L, then L is necessarily a total t-spread. Finally, the ‘type’ of the so-called geometric t-spreads is determined explicitely.
Kolmogorov numberings and minimal identification
1997
Abstract Identification of programs for computable functions from their graphs by algorithmic devices is a well studied problem in learning theory. Freivalds and Chen consider identification of ‘minimal’ and ‘nearly minimal’ programs for functions from their graphs. To address certain problems in minimal identification for Godel numberings, Freivalds later considered minimal identification in Kolmogorov numberings. Kolmogorov numberings are in some sense optimal numberings and have some nice properties. We prove certain separation results for minimal identification in every Kolmogorov numbering. In addition we also compare minimal identification in Godel numberings versus minimal identifica…
The minimum size of fully irregular oriented graphs
2001
Abstract Digraphs in which any two vertices have different pairs of semi-degrees are called fully irregular. For n-vertex fully irregular oriented graphs (i.e. digraphs without loops or 2-dicycles) the minimum size is presented.
A matrix of combinatorial numbers related to the symmetric groups
1979
For permutation groups G of finite degree we define numbers t"B(G)=|G|^-^[email protected]?"R"@?"[email protected]?"1(1a"1(g))^b^"^i, where B=(b"1,...,b"1) is a tuple of non-negative integers and a"1(g) denotes the number of i cycles in the element g. We show that t"B(G) is the number of orbits of G, acting on a set @D"B(G) of tuples of matrices. In the case G=S"n we get a natural interpretation for combinatorial numbers connected with the Stiring numbers of the second kind.
Degree sequences of highly irregular graphs
1997
AbstractWe call a simple graph highly irregular if each of its vertices is adjacent only to vertices with distinct degrees. In this paper we examine the degree sequences of highly irregular graphs. We give necessary and sufficient conditions for a sequence of positive integers to be the degree sequence of a highly irregular graph.
On the family ofr-regular graphs with Grundy numberr+1
2014
Abstract The Grundy number of a graph G , denoted by Γ ( G ) , is the largest k such that there exists a partition of V ( G ) , into k independent sets V 1 , … , V k and every vertex of V i is adjacent to at least one vertex in V j , for every j i . The objects which are studied in this article are families of r -regular graphs such that Γ ( G ) = r + 1 . Using the notion of independent module, a characterization of this family is given for r = 3 . Moreover, we determine classes of graphs in this family, in particular, the class of r -regular graphs without induced C 4 , for r ≤ 4 . Furthermore, our propositions imply results on the partial Grundy number.
Reordering Method and Hierarchies for Quantum and Classical Ordered Binary Decision Diagrams
2017
We consider Quantum OBDD model. It is restricted version of read-once Quantum Branching Programs, with respect to “width” complexity. It is known that maximal complexity gap between deterministic and quantum model is exponential. But there are few examples of such functions. We present method (called “reordering”), which allows to build Boolean function g from Boolean Function f, such that if for f we have gap between quantum and deterministic OBDD complexity for natural order of variables, then we have almost the same gap for function g, but for any order. Using it we construct the total function REQ which deterministic OBDD complexity is \(2^{\varOmega (n/log n)}\) and present quantum OBD…
Claws contained in all n-tournaments
1993
Abstract We prove that any claw of order n with degree d≤ 3 8 n is n-unavoidable, which means that any tournament of order n contains it as a subdigraph. A simple corollary is that any tournament has a directed Hamiltonian path.
On symmetric nonlocal games
2013
Abstract Nonlocal games are used to display differences between the classical and quantum world. In this paper, we study symmetric XOR games, which form an important subset of nonlocal games. We give simple methods for calculating the classical and the quantum values for symmetric XOR games with one-bit input per player. We illustrate those methods with two examples. One example is an N -player game (due to Ardehali (1992) [3] ) that provides the maximum quantum-over-classical advantage. The second example comes from generalization of CHSH game by letting the referee to choose arbitrary symmetric distribution of players’ inputs.