Search results for "Abstract data type"
showing 10 items of 1140 documents
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…
ARITHMETICAL QUESTIONS IN π-SEPARABLE GROUPS
2005
If G is a finite π-separable group, π a set of primes und X is a π-suhgroup of G, let vπ(G, X) be the number of Hall π-suhgroups of G containing X. If K is a subgroup of G containing X, we prove that vπ(K,X) divides vπ(G).
Closedness properties in ex-identification
2001
In this paper we investigate in which cases unions of identifiable classes are also necessarily identifiable. We consider identification in the limit with bounds on mindchanges and anomalies. Though not closed under the set union, these identification types still have features resembling closedness. For each of them we and n such that (1) if every union of n − 1 classes out of U1, ... , Un is identifiable, so is the union of all n classes; (2) there are classes U1, ... ,Un−1 such that every union of n−2 classes out of them is identifiable, while the union of n − 1 classes is not. We show that by finding these n we can distinguish which requirements put on the identifiability of unions of cl…
On bijections vs. unary functions
1996
A set of finite structures is in Binary NP if it can be characterized by existential second order formulas in which second order quantification is over relations of arity 2. In [DLS95] subclasses of Binary NP were considered, in which the second order quantifiers range only over certain classes of relations. It was shown that many of these subclasses coincide and that all of them can be ordered in a three-level linear hierarchy, the levels of which are represented by bijections, successor relations and unary functions respectively.
Basic Definitions and Facts
2001
Symbol is treated here as a primitive entity as point or line in geometry. Let Con = {f α : α < β} be a well-ordered set of symbols called a language type. β is an ordinal number. The elements of the above set are called connectives. To each connective f α a natural number α(α) ∈ w called the rank of f α or the arity of f α is assigned. The arity α(α) defines the number of arguments of f α . Thus we speak of nullary, unary, or binary connectives, etc. In the sequel Con is assumed to be fixed but arbitrary.
O(n 2 log n) Time On-Line Construction of Two-Dimensional Suffix Trees
2005
The two-dimensional suffix tree of an n × n square matrix A is a compacted trie that represents all square submatrices of Ai¾?[9]. For the off-line case, i.e., A is given in advance to the algorithm, it is known how to build it in optimal time, for any type of alphabet sizei¾?[9,15]. Motivated by applications in Image Compressioni¾?[18], Giancarlo and Guaianai¾?[12] considered the on-line version of the two-dimensional suffix tree and presented an On2log2n-time algorithm, which we refer to as GG. That algorithm is a non-trivial generalization of Ukkonen's on-line algorithm for standard suffix trees [19]. The main contribution in this paper is an Olog n factor improvement in the time complex…