Search results for "Combinatorics"
showing 10 items of 1770 documents
Generating restricted classes of involutions, Bell and Stirling permutations
2010
AbstractWe present a recursive generating algorithm for unrestricted permutations which is based on both the decomposition of a permutation as a product of transpositions and that as a union of disjoint cycles. It generates permutations at each recursive step and slight modifications of it produce generating algorithms for Bell permutations and involutions. Further refinements yield algorithms for these classes of permutations subject to additional restrictions: a given number of cycles or/and fixed points. We obtain, as particular cases, generating algorithms for permutations counted by the Stirling numbers of the first and second kind, even permutations, fixed-point-free involutions and d…
Nondeterministic Unitary OBDDs
2017
We investigate the width complexity of nondeterministic unitary OBDDs (NUOBDDs). Firstly, we present a generic lower bound on their widths based on the size of strong 1-fooling sets. Then, we present classically “cheap” functions that are “expensive” for NUOBDDs and vice versa by improving the previous gap. We also present a function for which neither classical nor unitary nondeterminism does help. Moreover, based on our results, we present a width hierarchy for NUOBDDs. Lastly, we provide the bounds on the widths of NUOBDDs for the basic Boolean operations negation, union, and intersection.
Irreducible components of Hurwitz spaces parameterizing Galois coverings of curves of positive genus
2014
Let Y be a smooth, projective, irreducible complex curve. A G-covering p : C → Y is a Galois covering, where C is a smooth, projective, irreducible curve and an isomorphism G ∼ −→ Aut(C/Y ) is fixed. Two G-coverings are equivalent if there is a G-equivariant isomorphism between them. We are concerned with the Hurwitz spaces H n (Y ) and H G n (Y, y0). The first one parameterizes Gequivalence classes of G-coverings of Y branched in n points. The second one, given a point y0 ∈ Y , parameterizes G-equivalence classes of pairs [p : C → Y, z0], where p : C → Y is a G-covering unramified at y0 and z0 ∈ p (y0). When G = Sd one can equivalently consider coverings f : X → Y of degree d with full mon…
Very Narrow Quantum OBDDs and Width Hierarchies for Classical OBDDs
2014
In the paper we investigate a model for computing of Boolean functions – Ordered Binary Decision Diagrams (OBDDs), which is a restricted version of Branching Programs. We present several results on the comparative complexity for several variants of OBDD models. We present some results on the comparative complexity of classical and quantum OBDDs. We consider a partial function depending on a parameter k such that for any k > 0 this function is computed by an exact quantum OBDD of width 2, but any classical OBDD (deterministic or stable bounded-error probabilistic) needs width 2 k + 1. We consider quantum and classical nondeterminism. We show that quantum nondeterminism can be more efficient …
Fixed point theory in partial metric spaces via φ-fixed point’s concept in metric spaces
2014
Abstract Let X be a non-empty set. We say that an element x ∈ X is a φ-fixed point of T, where φ : X → [ 0 , ∞ ) and T : X → X , if x is a fixed point of T and φ ( x ) = 0 . In this paper, we establish some existence results of φ-fixed points for various classes of operators in the case, where X is endowed with a metric d. The obtained results are used to deduce some fixed point theorems in the case where X is endowed with a partial metric p. MSC:54H25, 47H10.
An integral representation for decomposable measures of measurable functions
1994
We start with a measurem on a measurable space (Ω,A), decomposable with respect to an Archimedeant-conorm ⊥ on a real interval [0,M], which generalizes an additive measure. Using the integral introduced by the second author, a Radon-Nikodym type theorem, needed in what follows, is given.
Intersection subgroups of complex hyperplane arrangements
2000
Abstract Let A be a central arrangement of hyperplanes in C n , let M( A ) be the complement of A , and let L ( A ) be the intersection lattice of A . For X in L ( A ) we set A X ={H∈ A : H⫆X} , and A /X={H/X: H∈ A X } , and A X ={H∩X: H∈ A \ A X } . We exhibit natural embeddings of M( A X ) in M( A ) that give rise to monomorphisms from π 1 (M( A X )) to π 1 (M( A )) . We call the images of these monomorphisms intersection subgroups of type X and prove that they form a conjugacy class of subgroups of π 1 (M( A )) . Recall that X in L ( A ) is modular if X+Y is an element of L ( A ) for all Y in L ( A ) . We call X in L ( A ) supersolvable if there exists a chain 0⫅X 1 ⫅⋯⫅X d =X in L ( A ) …
On the low-dimensional Steiner minimum tree problem in Hamming metric
2013
While it is known that the d-dimensional Steiner minimum tree problem in Hamming metric is NP-complete if d is part of the input, it is an open question whether this also holds for fixed dimensions. In this paper, this question is answered by showing that the Steiner minimum tree problem in Hamming metric is already NP-complete in 3 dimensions. Furthermore, we show that, the minimum spanning tree gives a 2-2d approximation on the Steiner minimum tree for d>=2. Using this result, we analyse the so-called k-LCA and A"k approximation algorithms and show improved approximation guarantees for low dimensions.
Symmetric (79, 27, 9)-designs Admitting a Faithful Action of a Frobenius Group of Order 39
1997
AbstractIn this paper we present the classification of symmetric designs with parameters (79, 27, 9) on which a non-abelian group of order 39 acts faithfully. In particular, we show that such a group acts semi-standardly with 7 orbits. Using the method of tactical decompositions, we are able to construct exactly 1320 non-isomorphic designs. The orders of the full automorphism groups of these designs all divide 8 · 3 · 13.
Automata and differentiable words
2011
We exhibit the construction of a deterministic automaton that, given k > 0, recognizes the (regular) language of k-differentiable words. Our approach follows a scheme of Crochemore et al. based on minimal forbidden words. We extend this construction to the case of C\infinity-words, i.e., words differentiable arbitrary many times. We thus obtain an infinite automaton for representing the set of C\infinity-words. We derive a classification of C\infinity-words induced by the structure of the automaton. Then, we introduce a new framework for dealing with \infinity-words, based on a three letter alphabet. This allows us to define a compacted version of the automaton, that we use to prove that ev…