Count of primitive words

Abstract. The present paper concerns with the formula of the count of primitive words and ex-changeable primitive words.     

Automata accepting primitive words

LeA be an automaton whose set of inputs equalsX (|X|≧2) and whose cardinality of the set of states equalsn (n≧2), and letQ be the set of all primitive words overX. ByT(A) we denote the language accepted byA. In this paper, we give the following results:

Note on primitive words

This note presents an example that disproves, forn=4, Weinbaum’s conjecture, that ifw is a cyclically reduced primitive word inF _n such that all the generatorsx∈X appear inw then some cyclic permutation ofw can be partitioned inton words generatingF _n :w≡uv,vu≡s ₁ s ₂…s _n , <s ₁,s ₂,…s _n >=F _n .     

Marcus contextual languages consisting of primitive words

In this paper we prove that the language of all primitive (strongly primitive) words over a nontrivial alphabet can be generated by certain types of Marcus contextual grammars.     

On some properties of the decoding of admissible words for primitive substitutions

A number of properties of decoding for admissible sequences are studied, some of which were studied earlier, and some are new. Several conditions under which a substitution possesses these properties are obtained. Bibliography: 10 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 223, 1995, pp. 127–136. Supported by Russian Foundation for Basic Research, grant 94-01-00921. Translated by A. N. Livshits.     

Simulated factorizations II

Summary A factorization of a finite abelian group is said to be simulated if it is obtained from a factorization into a direct product of subgroups by changing at mostk elements in each subgroup. The question has been asked as to which values ofk imply that in fact at least one subgroup must be left unaltered. This has been shown to be true fork = 1 but to be false, in general, fork = p – 1, wherep is the least prime dividing the order ofG. In this paper it is shown to be true fork = p – 2.     

Orthogonal factorizations of graphs

Let G be a graph with vertex set V(G) and edge set E(G). Let k₁, k₂,…,k_m be positive integers. It is proved in this study that every [0,k₁+…+k_m?m+1]‐graph G has a [0, k_i]₁^m‐factorization orthogonal to any given subgraph H with m edges. © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 267–276, 2002     

Isomorphic factorizations of trees

A tree is even if its edges can be colored in two colors so that the monochromatic subgraphs are isomorphic. All even trees of maximum degree 3 in which no two vertices of degrees 1 or 3 are adjacent are determined. It is also shown that, for every n, there are only finitely many trees of maximum degree 3 and with n vertices of degree 3 that are not even. © 1995 John Wiley & Sons, Inc.     

Orthogonal factorizations of digraphs

Let G be a digraph with vertex set V(G) and arc set E(G) and let g = (g ⁻, g ⁺) and ƒ = (ƒ ⁻, ƒ ⁺) be pairs of positive integer-valued functions defined on V(G) such that g ⁻(x) ⩽ ƒ ⁻(x) and g ⁺(x) ⩽ ƒ ⁺(x) for each x ∈ V(G). A (g, ƒ)-factor of G is a spanning subdigraph H of G such that g ⁻(x) ⩽ id _H (x) ⩽ ƒ ⁻(x) and g ⁺(x) ⩽ od _H (x) ⩽ ƒ ⁺(x) for each x ∈ V(H); a (g, ƒ)-factorization of G is a partition of E(G) into arc-disjoint (g, ƒ)-factors. Let = {F ₁, F ₂,…, F _m} and H be a factorization and a subdigraph of G, respectively. is called k-orthogonal to H if each F _i , 1 ⩽ i ⩽ m, has exactly k arcs in common with H. In this paper it is proved that every (mg+m−1,mƒ−m+1)-digraph has a (g, f)-factorization k-orthogonal to any given subdigraph with km arcs if k ⩽ min{g ⁻(x), g ⁺(x)} for any x ∈ V(G) and that every (mg, mf)-digraph has a (g, f)-factorization orthogonal to any given directed m-star if 0 ⩽ g(x) ⩽ f(x) for any x ∈ V(G). The results in this paper are in some sense best possible.      

Postnikov factorizations at infinity

We have developed Postnikov sections for Brown–Grossman homotopy groups and for Steenrod homotopy groups in the category of exterior spaces, which is an extension of the proper category. The homotopy fibre of a fibration in the factorization associated with Brown–Grossman groups is an Eilenberg–Mac Lane exterior space for this type of groups and it has two non-trivial consecutive Steenrod homotopy groups. For a space which is first countable at infinity, one of these groups is given by the inverse limit of the homotopy groups of the neighbourhoods at infinity, the other group is isomorphic to the first derived of the inverse limit of this system of groups. In the factorization associated with Steenrod groups the homotopy fibre is an Eilenberg–Mac Lane exterior space for this type of groups and it has two non-trivial consecutive Brown–Grossman homotopy groups. We also obtain a mix factorization containing both kinds of previous factorizations and having homotopy fibres which are Eilenberg–Mac Lane exterior spaces for both kinds of groups.Given a compact metric space embedded in the Hilbert cube, its open neighbourhoods provide the Hilbert cube the structure of an exterior space and the homotopy fibres of the factorizations above are Eilenberg–Mac Lane exterior spaces with respect to inward (or approaching) Quigley groups.     

On tree factorizations of Kn

In this paper we exhibit a class of trees with the property that if T_k is a tree on k vertices that belongs to this class, then necessary and sufficient conditions for K_n to have a T_k-factorization are simply n = 0 (mod k) and n = 1 (mod 2(k - 1)). (This class is large and in particular contains all caterpillars with an odd number of vertices.) As a corollary we obtain necessary and sufficient conditions for the existence of a K_1,k-1-factorization of K_n, which previously had only been known to be asymptotically sufficient. © 1993 John Wiley & Sons, Inc.     

Rank factorizations of positive operators

The notion of a rank factorization of a positive operator through a cone is introduced and related to the nonnegative rank factorization of a nonnegative matrix. The concept is applied to the study of group inverses of certain positive operators.     

Irreducible factorizations of rationalq-parameter matrices

This paper considers rational q-parameter matrices (i.e., matrices the entries of which are ratios of scalar polynomials in q variables) and extends the previous results of the authors. Bibliography: 8 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 248, 1998, pp. 147–164. Translated by V. N. Kublanovskaya.     

Pseudoprime factorizations of integer matrices

We give a method of factoring integer matrices in into components such that the factorization is not unique unless certain information is known. In Section 2, we introduce this method of factorization and provide theorems which establish its well-definedness. In Section 3, we construct a matrix in as a product of specific types of matrices and establish an algorithm for factoring the result uniquely given an amount of information.     

Star factorizations of graph products

A k‐star is the graph K_1,k. We prove a general theorem about k‐star factorizations of Cayley graphs. This is used to give necessary and sufficient conditions for the existence of k‐star factorizations of any power (K_q)^s of a complete graph with prime power order q, products C × C ×··· × C of k cycles of arbitrary lengths, and any power (C_r)^s of a cycle of arbitrary length. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 59–66, 2001     

Cube factorizations of complete graphs

A cube factorization of the complete graph on n vertices, K_n, is a 3‐factorization of K_n in which the components of each factor are cubes. We show that there exists a cube factorization of K_n if and only if n ≡ 16 (mod 24), thus providing a new family of uniform 3‐factorizations as well as a partial solution to an open problem posed by Kotzig in 1979. © 2004 Wiley Periodicals, Inc.