Search results for "init"
showing 10 items of 6629 documents
Ambainis-Freivalds’ Algorithm for Measure-Once Automata
2001
An algorithm given by Ambainis and Freivalds [1] constructs a quantum finite automaton (QFA) with O(log p) states recognizing the language Lp = {ai| i is divisible by p} with probability 1 - Ɛ , for any Ɛ > 0 and arbitrary prime p. In [4] we gave examples showing that the algorithm is applicable also to quantum automata of very limited size. However, the Ambainis-Freivalds algoritm is tailored to constructing a measure-many QFA (defined by Kondacs andWatrous [2]), which cannot be implemented on existing quantum computers. In this paper we modify the algorithm to construct a measure-once QFA of Moore and Crutchfield [3] and give examples of parameters for this automaton. We show for the lang…
Improved Constructions of Quantum Automata
2008
We present a simple construction of quantum automata which achieve an exponential advantage over classical finite automata. Our automata use $\frac{4}{\epsilon} \log 2p + O(1)$ states to recognize a language that requires p states classically. The construction is both substantially simpler and achieves a better constant in the front of logp than the previously known construction of [2]. Similarly to [2], our construction is by a probabilistic argument. We consider the possibility to derandomize it and present some preliminary results in this direction.
Coding Partitions: Regularity, Maximality and Global Ambiguity
2007
The canonical coding partition of a set of words is the finest partition such that the words contained in at least two factorizations of a same sequence belong to a same class. In the case the set is not uniquely decipherable, it partitions the set into one unambiguous class and other parts that localize the ambiguities in the factorizations of finite sequences. We firstly prove that the canonical coding partition of a regular set contains a finite number of regular classes. We give an algorithm for computing this partition. We then investigate maximality conditions in a coding partition and we prove, in the regular case, the equivalence between two different notions of maximality. As an ap…
On extremal intersection numbers of a block design
1982
K.N. Majumdar has shown that for a 2-(v, k, @l) design D there are three numbers @a, @t, and @S such that each intersection number of D is not greater than @S and not less than max{@a, @t}. In this paper we investigate designs having one of these 'extremal' intersection numbers. Quasisymmetric designs with at least one extremal intersection number are characterized. Furthermore, we show that a smooth design D having the intersection number @S or @a>0 is isomorphic to the system of points and hyperplanes of a finite projective space. Using this theorem, we can characterize all smooth strongly resolvable designs.
Product of nilpotent subgroups
2000
We will say that a subgroup X of G satisfies property C in G if \({\rm C}_{G}(X\cap X^{{g}})\leqq X\cap X^{{g}}\) for all \({g}\in G\). We obtain that if X is a nilpotent subgroup satisfying property C in G, then XF(G) is nilpotent. As consequence it follows that if \(N\triangleleft G\) is nilpotent and X is a nilpotent subgroup of G then \(C_G(N\cap X)\leqq X\) implies that NX is nilpotent.¶We investigate the relationship between the maximal nilpotent subgroups satisfying property C and the nilpotent injectors in a finite group.
A simple proof of the polylog counting ability of first-order logic
2007
The counting ability of weak formalisms (e.g., determining the number of 1's in a string of length N ) is of interest as a measure of their expressive power, and also resorts to complexity-theoretic motivations: the more we can count the closer we get to real computing power. The question was investigated in several papers in complexity theory and in weak arithmetic around 1985. In each case, the considered formalism (AC 0 -circuits, first-order logic, Δ 0 ) was shown to be able to count up to a polylogarithmic number. An essential part of the proofs is the construction of a 1-1 mapping from a small subset of {0, ..., N - 1} into a small initial segment. In each case the expressibility of …
On partial CAP-subgroups of finite groups
2015
Abstract Given a chief factor H / K of a finite group G, we say that a subgroup A of G avoids H / K if H ∩ A = K ∩ A ; if H A = K A , then we say that A covers H / K . If A either covers or avoids the chief factors of some given chief series of G, we say that A is a partial CAP-subgroup of G. Assume that G has a Sylow p-subgroup of order exceeding p k . If every subgroup of order p k , where k ≥ 1 , and every subgroup of order 4 (when p k = 2 and the Sylow 2-subgroups are non-abelian) are partial CAP-subgroups of G, then G is p-soluble of p-length at most 1.
A NOTE ON THE ASYMPTOTIC PROBABILITIES OF EXISTENTIAL SECOND-ORDER MINIMAL GÖDEL SENTENCES WITH EQUALITY
1995
The minimal Gödel class is the class of first-order prenex sentences whose quantifier prefix consists of two universal quantifiers followed by just one existential quantifier. We prove that asymptotic probabilities of existential second-order sentences, whose first-order part is in the minimal Gödel class, form a dense subset of the unit interval.
The node-depth encoding
2008
The node-depth encoding has elements from direct and indirect encoding for trees which encodes trees by storing the depth of nodes in a list. Node-depth encoding applies specific search operators that is a typical characteristic for direct encodings. An investigation into the bias of the initialization process and the mutation operators of the node-depth encoding shows that the initialization process has a bias to solutions with small depths and diameters, and a bias towards stars. This investigation, also, shows that the mutation operators are unbiased. The performance of node-depth encoding is investigated for the bounded-diameter minimum spanning tree problem. The results are presented f…
On σ-subnormal closure
2020
Let σ={σi:i∈I} be a partition of the set P of all prime numbers. A subgroup A of a finite group G is called σ-subnormal in G if there is a chain of subgroups A=A0⊆A1⊆⋯⊆An=G with Ai−1 normal in Ai o...