共查询到20条相似文献,搜索用时 0 毫秒
1.
We introduce two new types of Dehn functions of group presentations which seem more suitable (than the standard Dehn function)
for infinite group presentations and prove the fundamental equivalence between the solvability of the word problem for a group
presentation defined by a decidable set of defining words and the property of being computable for one of the newly introduced
functions (this equivalence fails for the standard Dehn function). Elaborating on this equivalence and making use of this
function, we obtain a characterization of finitely generated groups for which the word problem can be solved in nondeterministic
polynomial time.
We also give upper bounds for these functions, as well as for the standard Dehn function, for two well-known periodic groups.
In particular, we prove that the (standard) Dehn function of a 2-group Γ of intermediate growth, defined by a system of defining
relators due to Lysenok, is bounded from above by C1x2 log2 x, where C1 > 1 is a constant. We also show that the (standard) Dehn function of a free m-generator Burnside group B(m, n) of exponent n ≥ 248, where n is either odd or divisible by 29, defined by a minimal system of defining relators, is bounded from above by the subquadratic function x19/12.
Received: September 2007, Revision: March 2008, Accepted: March 2008 相似文献
2.
A pseudo-natural algorithm for the word problem of a finitely presented group is an algorithm which not only tells us whether or not a word w equals 1 in the group but also gives a derivation of 1 from w when w equals 1. In [13], [14] Madlener and Otto show that, if we measure complexity of a primitive recursive algorithm by its level in the Grzegorczyk hierarchy, there are groups in which a pseudo-natural algorithm is arbitrarily more complicated than an algorithm which simply solves the word problem. In a given group the lowest degree of complexity that can be realised by a pseudo-natural algorithm is essentially the derivational complexity of that group. Thus the result separates the derivational complexity of the word problem of a finitely presented group from its intrinsic complexity. The proof given in [13] involves the construction of a finitely presented group G from a Turing machine T such that the intrinsic complexity of the word problem for G reflects the complexity of the halting problem of T, while the derivational complexity of the word problem for G reflects the runtime complexity of T. The proof of one of the crucial lemmas in [13] is only sketched, and part of the purpose of this paper is to give the full details of this proof. We will also obtain a variant of their proof, using modular machines rather than Turing machines. As for several other results, this simplifies the proofs considerably. MSC: 03D40, 20F10. 相似文献
3.
In this paper, we study the word problem for automaton semigroups and automaton groups from a complexity point of view. As an intermediate concept between automaton semigroups and automaton groups, we introduce automaton-inverse semigroups, which are generated by partial, yet invertible automata. We show that there is an automaton-inverse semigroup and, thus, an automaton semigroup with a PSpace-complete word problem. We also show that there is an automaton group for which the word problem with a single rational constraint is PSpace-complete. Additionally, we provide simpler constructions for the uniform word problems of these classes. For the uniform word problem for automaton groups (without rational constraints), we show NL-hardness. Finally, we investigate a question asked by Cain about a better upper bound for the length of a word on which two distinct elements of an automaton semigroup must act differently.A detailed listing of the contributions of this paper can be found at the end of this paper. 相似文献
4.
We investigate the fundamental group of Griffiths? space, and the first singular homology group of this space and of the Hawaiian Earring by using (countable) reduced tame words. We prove that two such words represent the same element in the corresponding group if and only if they can be carried to the same tame word by a finite number of word transformations from a given list. This enables us to construct elements with special properties in these groups. By applying this method we prove that the two homology groups contain uncountably many different elements that can be represented by infinite concatenations of countably many commutators of loops. As another application we give a short proof that these homology groups contain the direct sum of ℵ02 copies of Q. Finally, we show that the fundamental group of Griffiths? space contains Q. 相似文献
5.
A Dehn twist automorphism of a group G is an automorphism which can be given (as specified below) in terms of a graph-of-groups decomposition of G with infinite cyclic edge groups. The classic example is that of an automorphism of the fundamental group of a surface which
is induced by a Dehn twist homeomorphism of the surface. For , a non-abelian free group of finite rank n, a normal form for Dehn twist is developed, and it is shown that this can be used to solve the conjugacy problem for Dehn
twist automorphisms of .
Received: February 12, 1996. 相似文献
6.
Marcel Herzog 《Journal of Combinatorial Theory, Series A》2008,115(7):1235-1245
Given integers k,l?2, where either l is odd or k is even, we denote by n=n(k,l) the largest integer such that each element of An is a product of k cycles of length l. For an odd l, k is the diameter of the undirected Cayley graph Cay(An,Cl), where Cl is the set of all l-cycles in An. We prove that if k?2 and l?9 is odd and divisible by 3, then . This extends earlier results by Bertram [E. Bertram, Even permutations as a product of two conjugate cycles, J. Combin. Theory 12 (1972) 368-380] and Bertram and Herzog [E. Bertram, M. Herzog, Powers of cycle-classes in symmetric groups, J. Combin. Theory Ser. A 94 (2001) 87-99]. 相似文献
7.
Riddhi Shah 《Proceedings Mathematical Sciences》2001,111(1):49-63
On a locally compact group G, if
, for some probability measuresv
n and μ onG, then a sufficient condition is obtained for the set
to be relatively compact; this in turn implies the embeddability of a shift of μ. The condition turns out to be also necessary
when G is totally disconnected. In particular, it is shown that ifG is a discrete linear group over R then a shift of the limit μ is embeddable. It is also shown that any infinitesimally divisible
measure on a connected nilpotent real algebraic group is embeddable. 相似文献
8.
M. I. Anokhin 《Mathematical Notes》1997,61(1):3-8
LetF be a free group with at most countable system
of free generators, letR be its normal subgroup recursively enumerable with respect to
, and let
be a variety of groups that differs from
and for which the corresponding verbal subgroupV of the free group of countable rank is recursive. It is proved that the word problem inF/V(R) is solvable if and only if this problem is solvable inF/R, and if
, then there exists anR such, that the conjugacy problem inF/R is solvable, but this problem is unsolvable inF/V(R) for any Abelian variety
(all algorithmic problems are regarded with respect to the images of
under the corresponding natural epimorphisms).
Translated fromMatematicheskie Zametki, Vol. 61, No. 1, pp. 3–9, January, 1997.
Translated by M. I. Anokhin 相似文献
9.
The cycling operation is a special kind of conjugation that can be applied to elements in Artin’s braid groups, in order to reduce their length. It is a key ingredient of the usual solutions to the conjugacy problem in braid groups. In their seminal paper on braid-cryptography, Ko, Lee et al. proposed the cycling problem as a hard problem in braid groups that could be interesting for cryptography. In this paper we give a polynomial solution to that problem, mainly by showing that cycling is surjective, and using a result by Maffre which shows that pre-images under cycling can be computed fast. This result also holds in every Artin-Tits group of spherical type, endowed with the Artin Garside structure.On the other hand, the conjugacy search problem in braid groups is usually solved by computing some finite sets called (left) ultra summit sets (left-USSs), using left normal forms of braids. But one can equally use right normal forms and compute right-USSs. Hard instances of the conjugacy search problem correspond to elements having big (left and right) USSs. One may think that even if some element has a big left-USS, it could possibly have a small right-USS. We show that this is not the case in the important particular case of rigid braids. More precisely, we show that the left-USS and the right-USS of a given rigid braid determine isomorphic graphs, with the arrows reversed, the isomorphism being defined using iterated cycling. We conjecture that the same is true for every element, not necessarily rigid, in braid groups and Artin-Tits groups of spherical type. 相似文献
10.
This study examines service systems with transfers of customers in an alternating environment. We model the service system as a two-server two-parallel queue (primary and auxiliary queues), that has various applications especially in manufacturing and healthcare systems. We establish a sufficient stability condition, and based on the censoring technique, we provide sufficient conditions under which the stationary distribution possesses an exactly geometric tail along the direction of the queue length in the primary queue. 相似文献
11.
Volodymyr Nekrashevych 《Geometriae Dedicata》2007,124(1):153-190
We construct and study a family of 3-generated groups parametrized by infinite binary sequences w. We show that two groups of the family are isomorphic if and only if the sequences are cofinal and that two groups cannot
be distinguished by finite sets of relations. We show a connection of the family with 2-dimensional holomorphic dynamics.
相似文献
12.
A well-known result for Vilenkin systems is the fact that for all 1 p ∞ the n-th partial sums of Fourier series of all functions in the space Lpconverge to the function in Lp-norm.This statement can not be generalized to any representative product system on the complete product of finite non-abelian groups,but even then it is true for the complete product of quaternion groups with bounded orders and monomial representative product system ordered in a specific way. 相似文献
13.
Sheng Gao 《中国科学 数学(英文版)》2012,55(6):1179-1188
The author carries out a detailed study of p-blocks with normal metacyclic defect groups provided that p is odd and the defect groups are splitting and nonabelian.In particular,the author constructs all the irreducible ordinary and modular characters in this type of blocks.As a by-product,k(B) and l(B) are obtained. 相似文献
14.
In this paper we show that a complete characterization of the controllability property for linear control system on three-dimensional solvable nonnilpotent Lie groups is possible by the LARC and the knowledge of the eigenvalues of the derivation associated with the drift of the system. 相似文献
15.
16.
This note is a follow-up on the paper [A. Borel, G. Harder, Existence of discrete cocompact subgroups of reductive groups over local fields, J. Reine Angew. Math. 298 (1978) 53-64] of A. Borel and G. Harder in which they proved the existence of a cocompact lattice in the group of rational points of a connected semi-simple algebraic group over a local field of characteristic zero by constructing an appropriate form of the semi-simple group over a number field and considering a suitable S-arithmetic subgroup. Some years ago A. Lubotzky initiated a program to study the subgroup growth of arithmetic subgroups, the current stage of which focuses on “counting” (more precisely, determining the asymptotics of) the number of lattices of bounded covolume (the finiteness of this number was established in [A. Borel, G. Prasad, Finiteness theorems for discrete subgroups of bounded covolume in semi-simple groups, Publ. Math. Inst. Hautes Études Sci. 69 (1989) 119-171; Addendum: Publ. Math. Inst. Hautes Études Sci. 71 (1990) 173-177] using the formula for the covolume developed in [G. Prasad, Volumes of S-arithmetic quotients of semi-simple groups, Publ. Math. Inst. Hautes Études Sci. 69 (1989) 91-117]). Work on this program led M. Belolipetsky and A. Lubotzky to ask questions about the existence of isotropic forms of semi-simple groups over number fields with prescribed local behavior. In this paper we will answer these questions. A question of similar nature also arose in the work [D. Morris, Real representations of semisimple Lie algebras have Q-forms, in: Proc. Internat. Conf. on Algebraic Groups and Arithmetic, December 17-22, 2001, TIFR, Mumbai, 2001, pp. 469-490] of D. Morris (Witte) on a completely different topic. We will answer that question too. 相似文献
17.
The existence of cycles of the second kind was considered for uncertain pendulum-like systems with several nonlinearities. On the basis of the Kalman–Yakubovich–Popov (KYP) lemma, linear matrix inequality (LMI) conditions guaranteeing the existence of cycles of the second kind for such nonlinear systems under parameter uncertainties are established. By virtue of these results, an interesting conclusion is reached: that the synthesis problem ensuring the existence of cycles of the second kind for such an uncertain nonlinear system can be converted into a synthesis problem for a system without uncertainties. A concrete application to a synchronous machine demonstrates the validity of the proposed approach. 相似文献
18.
An algorithm of sequential systems of linear equations for nonlinear optimization problems with arbitrary initial point 总被引:6,自引:0,他引:6
For current sequential quadratic programming (SQP) type algorithms, there exist two problems: (i) in order to obtain a search
direction, one must solve one or more quadratic programming subproblems per iteration, and the computation amount of this
algorithm is very large. So they are not suitable for the large-scale problems; (ii) the SQP algorithms require that the related
quadratic programming subproblems be solvable per iteration, but it is difficult to be satisfied. By using ε-active set procedure
with a special penalty function as the merit function, a new algorithm of sequential systems of linear equations for general
nonlinear optimization problems with arbitrary initial point is presented. This new algorithm only needs to solve three systems
of linear equations having the same coefficient matrix per iteration, and has global convergence and local superlinear convergence.
To some extent, the new algorithm can overcome the shortcomings of the SQP algorithms mentioned above.
Project partly supported by the National Natural Science Foundation of China and Tianyuan Foundation of China. 相似文献
19.
We investigate well posedness of the Cauchy problem for SG hyperbolic systems with non-smooth coefficients with respect to time. By assuming the coefficients to be Hölder continuous we show that this low regularity has a considerable influence on the behavior at infinity of the solution as well as on its regularity. This leads to well posedness in suitable Gelfand-Shilov classes of functions on Rn. A simple example shows the sharpness of our results. 相似文献
20.
A. I. Dolgarev 《Russian Mathematics (Iz VUZ)》2008,52(12):13-22
We describe the mentioned groups, assigning values to centralizers of the generating elements and defining a group operation on corteges of elements of the Galois field with a prime odd characteristic. On the indicated groups we define odules over the Galois field and describe these odules. We prove that the considered groups are those with unique extraction of root. 相似文献