1,721,005 research outputs found
A note on the multiplicative group of a division ring
No full textFor any group G its FC-centre may be defined as the subset of all elements having only finitely many conjugates. This is a subgroup and it allows one to define the upper central FC-series {Fn} by F0=1, F1=FC(G) and Fn+1/Fn=FC(G/Fn). If Fn=G for some n, then G is said to be FC-nilpotent. The author shows that if D is a division ring with centre Z and x∈D has infinitely many conjugates, then so does its image xZ× in D×/Z×, where D× is the multiplicative group of D. He deduces that any division ring D whose group D× is FC-nilpotent is commutative, thus generalizing a theorem which asserts commutativity when D× is nilpotent [L.-K. Hua, Acad. Sinica Science Record 3 (1950), 1--6; MR0039707 (12,584e)]. It follows that D is commutative whenever D× has the permutation property Pn defined by A. Restivo and C. Reutenauer [J. Algebra 89 (1984), no. 1, 102--104; MR0748230 (85k:20188)]
Free groups of quaternions
No full textThis paper deals with the study of the free noncommutative group in the multiplicative group of the skewfield of the real Hamilton quaternions. The main results proved in this paper allows us to obtain the following interesting corollary: let G be a subgroup of rational quaternions. Then G is either solvable or contains the free noncommutative group
Automates, groupes libres et commutations
No full textThese de doctorat 3eme cycle, Universite' de Paris 7, Paris (France
A combinatorial problem on Trapezoidal words
No full textIn this paper, we investigate some combinatorial properties concerning the family of the so-called Trapezoidal words. Trapezoidal words, considered in de Luca (Theoret. Comput. Sci. 218 (1999) 13-39) are finite words over the two-letter alphabet A = {a, b} whose subword complexity has the same behaviour as that of finite Sturmian words. In de Luca (Theoret. Comput. Sci. 218 (1999) 13-39) it has been proved that the family of Finite Sturmian words is properly contained in that one of Trapezoidal words. We carry on with the studying of the family of Trapezoidal words and, in particular, of its relation with that one of finite Sturmian words. (C) 2002 Published by Elsevier Science B.V
On the complexity of Simon automata over the Dyck language
No full textIn this paper the following problem is studied. Let be a finite alphabet where and are disjoint and equipotent sets. Let be a rational language over and let be the Simon distance automaton on L. Let be the square matrix with entries in the extended set of natural numbers given by the formula: for every pair of states of , is the minimum weight of a computation in from to labelled by a Dyck word if such a computation exists, otherwise it is . We exhibit a polynomial time algorithm which allows us to compute the matrix in the case in which is the unary alphabet. This result partially solves an open question raised in [F. d'Alessandro and J. Sakarovitch, Theoret. Comput. Sci. 293 (2003), no. 1, 55--82; MR1957613 (2003m:20025)]
Well quasi-orders and formal languages
No full textThe concept of well quasi-order is a generalization of the classical notion of well order and plays a role in the studying of several problems of Mathematics and Theoretical Computer Science. This paper concerns some applications of well quasi-orders to Formal Language Theory. In particular, we present a survey of classical and recent results, based upon such structures, concerning context-free and regular languages. We also focus our attention to some application of well quasi-orders in the studying of languages obtained by using the operators of shuffle and iterated shuffle of finite languages. © 2008 Springer-Verlag Berlin Heidelberg
The commutative equivalence of bounded context-free and regular languages
No full textIt is proved that every bounded context-free language L is commutatively equivalent to a regular language L', that is, there exists a bijection from L onto L' preserving the Parikh vectors of words
On incomplete and synchronizing finite sets
Full text linkThis paper situates itself in the theory of variable length codes and of finite automata where the concepts of completeness and synchronization play a central role. In this theoretical setting, we investigate the problem of finding upper bounds to the minimal length of synchronizing words and incompletable words of a finite language X in terms of the length of the words of X. This problem is related to two well-known conjectures formulated by Černý and Restivo, respectively. In particular, if Restivo's conjecture is true, our main result provides a quadratic bound for the minimal length of a synchronizing pair of any finite synchronizing complete code with respect to the maximal length of its words
- …
