Search results for "combinatoric"
showing 10 items of 1776 documents
A General Framework for the One Center Location Problem
1992
This paper deals with an optimization problem where the objective function F is defined on a real vector space X by F(x) = γ(w 1║x - a 1║1, ⋯, w n ║x - a n║ n ), a formula in which a 1, ⋯, a n are n given points in X, ║∙║1, ⋯, ║∙║ n n norms on X, w 1, ⋯, w n positive numbers and γ a monotone norm on ℝ n . A geometric description of the set of optimal solutions to the problem min F(x) is given, illustrated by some examples. When all norms ║∙║i are equal, and γ being successively the l 1 , l ∞ and l 2-norm, a particular study is made, which shows the peculiar role played by the l 1-norm.
An algorithm for the solution of tree equations
1997
We consider the problem of solving equations over k-ary trees. Here an equation is a pair of labeled α-ary trees, where α is a function associating an arity to each label. A solution to an equation is a morphism from α-ary trees to k-ary trees that maps the left and right hand side of the equation to the same k-ary tree.
A Note on a Conjecture of Duval and Sturmian Words
2002
We prove a long standing conjecture of Duval in the special case of Sturmian words. Mathematics Subject Classication. ??????????????. Let U be a nonempty word on a nite alphabet A: A nonempty word B dierent from U is called a border of U if B is both a prex and sux of U: We say U is bordered if U admits a border, otherwise U is said to be unbordered. For example, U = 011001011 is bordered by the factor 011; while 00010001001 is unbordered. An integer 1 k n is a period of a word U = U1 :::U n if and only if for all 1 i n k we have Ui = Ui+k. It is easy to see that k is a period of U if and only if the prex B of U of length n k is a border of U or is empty. Let (U) denote the smallest period …
Coding with traces
1994
We prove that the existence of a coding between two trace monoids is decidable for some families of trace monoids. Decidability heavily depends on the structure of the dependence graphs. The concept of coding is based on the new notion of strong morphism between trace monoids.
Extension of a Schur theorem to groups with a central factor with a bounded section rank
2013
Abstract A well-known result reported by Schur states that the derived subgroup of a group is finite provided its central factor is finite. Here we show that if the p-section rank of the central factor of a locally generalized radical group is bounded, then so is the p-section rank of its derived subgroup. We also give an explicit expression for this bound.
On the identities of the Grassmann algebras in characteristicp>0
2001
In this note we exhibit bases of the polynomial identities satisfied by the Grassmann algebras over a field of positive characteristic. This allows us to answer the following question of Kemer: Does the infinite dimensional Grassmann algebra with 1, over an infinite fieldK of characteristic 3, satisfy all identities of the algebraM 2(K) of all 2×2 matrices overK? We give a negative answer to this question. Further, we show that certain finite dimensional Grassmann algebras do give a positive answer to Kemer's question. All this allows us to obtain some information about the identities satisfied by the algebraM 2(K) over an infinite fieldK of positive odd characteristic, and to conjecture ba…
Running time to recognize nonregular languages by 2-way probabilistic automata
1991
R. Freivalds proved that the language {0m1m} can be recognized by 2-way probabilistic finite automata (2pfa) with arbitrarily high probability 1-ɛ. A.G.Greenberg and A.Weiss proved that no 2pfa can recognize this language in expected time \(T(n) = c^\circ{(n)}\). For arbitrary languages C.Dwork and L.Stockmeyer showed somewhat less: if a language L is recognized by a 2pfa in expected time \(T(n) = c^{n^\circ{(1)} }\), then L is regular. First, we improve this theorem replacing the expected time by the time with probability 1-ɛ. On the other hand, time bound by C.Dwork and L.Stockmeyer cannot be improved: for arbitrary k≥2 we exhibit a specific nonregular language that can be recognized by 2…
Permutable products of supersoluble groups
2004
We investigate the structure of finite groups that are the mutually permutable product of two supersoluble groups. We show that the supersoluble residual is nilpotent and the Fitting quotient group is metabelian. These results are consequences of our main theorem, which states that such a product is supersoluble when the intersection of the two factors is core-free in the group.
On the number of conjugacy classes of zeros of characters
2004
Letm be a fixed non-negative integer. In this work we try to answer the following question: What can be said about a (finite) groupG if all of its irreducible (complex) characters vanish on at mostm conjugacy classes? The classical result of Burnside about zeros of characters says thatG is abelian ifm=0, so it is reasonable to expect that the structure ofG will somehow reflect the fact that the irreducible characters vanish on a bounded number of classes. The same question can also be posed under the weaker hypothesis thatsome irreducible character ofG hasm classes of zeros. For nilpotent groups we shall prove that the order is bounded by a function ofm in the first case but only the derive…
Periodic and Nil Polynomials in Rings
1980
Let R be an associative ring and f(x1,…, xd) a polynomial in noncommuting variables. We say that f is periodic or nil in R if for all r1,…, rd ∈ R we have that f(r1,…, rd) is periodic, respectively nilpotent (recall that a ∈ R is periodic if for some integer ).