Search results for "combinatoric"
showing 10 items of 1776 documents
Mixed intersections of non quasi-analytic classes
2008
Given two semi-regular matrices M and M' and two open subsets O and O' [resp. two compact subsets K and K'] of Rr and Rs respectively, we introduce the spaces E(M×M')(O × O') and D(M×M')(O × O') [resp. D(M×M')(K × K')]. In this paper we study their locally convex properties and the structure of their elements. This leads in [10] to tensor product representations of these spaces and to some kernel theorems.
Über die Schnittzahlen mehrfach balancierter blockpläne
1991
Abstract For a finite incidence structure D with a set X of blocks let [ X ] be the number of points common with all blocks contained in X . We define the functions M(t)(B1,…; B1)=ΣB [B1, B]…[B1,B], and, for every partition ϖ = ϖ1,…,ϖ1) of t, the function Mϖ(B1,…,B1) = Σ Πm [Bi | i ϵ Rm], sum over all decompositions {l, …, t} = R1, ⊃ … ⊃ Rl, |Rm| = ϖm. We show: If D is t-fold balanced, then M(t) = Σϖ cϖMϖ, where the, coefficients cϖ are linear combinations of the parameters b1,…,bt, the constant numbers of blocks through any l,…, t distinct points. Conversely, if the rank of the b × b-matrix ([B, B∗])B,B∗ is equal to the number ν of points and M(t) is a rational linear combination of the fu…
SUBGROUPS OF FINITE GROUPS WITH A STRONG COVER-AVOIDANCE PROPERTY
2009
AbstractA subgroup A of a group G has the strong cover-avoidance property in G, or A is a strong CAP-subgroup of G, if A either covers or avoids every chief factor of every subgroup of G containing A. The main aim of the present paper is to analyse the impact of the strong cover and avoidance property of the members of some relevant families of subgroups on the structure of a group.
Quantum Finite State Automata over Infinite Words
2010
The study of finite state automata working on infinite words was initiated by Buchi [1]. Buchi discovered connection between formulas of the monadic second order logic of infinite sequences (S1S) and ω-regular languages, the class of languages over infinite words accepted by finite state automata. Few years later, Muller proposed an alternative definition of finite automata on infinite words [4]. McNaughton proved that with Muller’s definition, deterministic automata recognize all ω-regular languages [2]. Later, Rabin extended decidability result of Buchi for S1S to the monadic second order of the infinite binary tree (S2S) [5]. Rabin theorem can be used to settle a number of decision probl…
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.
Chromatic Sums for Colorings Avoiding Monochromatic Subgraphs
2013
Abstract Given graphs G and H, a vertex coloring c : V ( G ) → N is an H-free coloring of G if no color class contains a subgraph isomorphic to H. The H-free chromatic number of G, χ ( H , G ) , is the minimum number of colors in an H-free coloring of G. The H-free chromatic sum of G , Σ ( H , G ) , is the minimum value achieved by summing the vertex colors of each H-free coloring of G. We provide a general bound for Σ ( H , G ) , discuss the computational complexity of finding this parameter for different choices of H, and prove an exact formulas for some graphs G. For every integer k and for every graph H, we construct families of graphs, G k with the property that k more colors than χ ( …
Products of locally finite groups with min-p
1986
AbstractThe paper is devoted to showing that if the factorized group G = AB is almost solvable, if A and B are π-subgroups with min-p for some prime p in π and also if the hypercenter factor group A/H(A) or B/H(B) has min p for the prime p. then G is a π-group with min-p for the prime p.
Archimedean actions on median pretrees
2001
In this paper we consider group actions on generalized treelike structures (termed ‘pretrees’) defined simply in terms of betweenness relations. Using a result of Levitt, we show that if a countable group admits an archimedean action on a median pretree, then it admits an action by isometries on an [open face R]-tree. Thus the theory of isometric actions on [open face R]-trees may be extended to a more general setting where it merges naturally with the theory of right-orderable groups. This approach has application also to the study of convergence group actions on continua.
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…