Search

Let C be a collection of closed walks of a connected graph Γ . We study coverings and homotopy of Γ under the condition that every member of C can be lifted through covering morphisms, and is contractible. Since they depend on C , we call them C -coverings and C -homotopy. After we review the existence of universal C -covers and their uniqueness modulo isomorphism studied by E. E. Shult and others, we investigate conditions that a finite graph is C -simply connected, i.e., the graph itself is a universal C -cover. As an application, we show that classes of distance-regular graphs and distance-semiregular graphs are C -simply connected when C is the collection of closed paths of minimal length. We also show a finiteness condition of a universal C -cover of a class of connected bipartite graphs when C is the collection of closed paths of minimal length.

In this paper we introduce and study new notions of uniform recurrence in multidimensional words. A d -dimensional word is called uniformly recurrent if for all ( s 1 , … , s d ) ∈ N d there exists n ∈ N such that each block of size ( n , … , n ) contains the prefix of size ( s 1 , … , s d ) . We are interested in a modification of this property. Namely, we ask that for each rational direction ( q 1 , … , q d ) , each rectangular prefix occurs along this direction in positions l ( q 1 , … , q d ) with bounded gaps. Such words are called uniformly recurrent along all directions. We provide several constructions of multidimensional words satisfying this condition, and more generally, a series of four increasingly stronger conditions. In particular, we study the uniform recurrence along directions of multidimensional rotation words and of fixed points of square morphisms.

Given an infinite word x over an alphabet A, a letter b occurring in x, and a total order @s on A, we call the smallest word with respect to @s starting with b in the shift orbit closure of x an extremal word of x. In this paper we consider the extremal words of morphic words. If x=g(f^@w(a)) for some morphisms f and g, we give two simple conditions on f and g that guarantee that all extremal words are morphic. This happens, in particular, when x is a primitive morphic or a binary pure morphic word. Our techniques provide characterizations of the extremal words of the period-doubling word and the Chacon word and a new proof of the form of the lexicographically least word in the shift orbit closure of the Rudin-Shapiro word.

A combinatorial study discloses two surjective morphisms between generalized shuffle algebras and algebras generated by the colored Hurwitz polyzêtas. The combinatorial aspects of the products and co-products involved in these algebras will be examined.

We introduce a framework for the study of formal contexts and their lattices induced by the additional structure of self-relations on top of the traditional incidence relation. The induced contexts use subsets as objects and attributes, hence the name power context and power concept. Six types of new incidence relations are introduced by taking into account all possible combinations of universal and existential quantifiers as well as the order of the quantifications in constructing the lifted power contexts. The structure of the power concept lattice is investigated through projection mappings from the baseline objects and attributes to those of the power context, respectively. We introduce the notions of extensional consistency and intensional consistency, corresponding to the topological notions of continuity in the analogous setting when concepts are viewed as closed sets. We establish Galois connections for these notions of consistency. We further introduce the notion of faithfulness for the first type of lifted incidence relation based on the fact that it can be equivalently characterized by a concept-faithful morphism. We also present conditions under which the power concept lattice serves as a factor lattice of the base concept lattice.

We consider avoiding squares and overlaps over the natural numbers, using a greedy algorithm that chooses the least possible integer at each step; the word generated is lexicographically least among all such infinite words. In the case of avoiding squares, the word is 01020103..., the familiar ruler function, and is generated by iterating a uniform morphism. The case of overlaps is more challenging. We give an explicitly-defined morphism phi : N* -> N* that generates the lexicographically least infinite overlap-free word by iteration. Furthermore, we show that for all h,k in N with h, 16 pages, 2 tables

In this paper, we study the binary relations R on a nonempty N^*-set A which are h-independent and h-positive (cf. the introduction below). They are called homothetic positive orders. Denote by B the set of intervals of R having the form [r,+~[ with 0="0. It is a Q">"0-set endowed with a binary relation > extending the usual one on R">"0 (identified with a subset of B via the map r@?[r,+~[). We first prove that there exists a unique map @F"R:AxA->B such that (for all x,y@?A and all m,n@?N^*) we have @F(mx,ny)=mn^-^1@?@F(x,y) and xRy@?@F"R(x,y)>1. Then we give a characterization of the homothetic positive orders R on A such that there exist two morphisms of N^*-sets u"1,u"2:A->B satisfying xRy@?u"1(x)>u"2(y). They are called generalized homothetic biorders. Moreover, if we impose some natural conditions on the sets u"1(A) and u"2(A), the representation (u"1,u"2) is ''uniquely'' determined by R. For a generalized homothetic biorder R on A, the binary relation R"1 on A defined by xR"1y@?@F"R(x,y)>@F"R(y,x) is a generalized homothetic weak order; i.e. there exists a morphism of N^*-sets u:A->B such that (for all x,y@?A) we have xR"1y@?u(x)>u(y). As we did in [B. Lemaire, M. Le Menestrel, Homothetic interval orders, Discrete Math. 306 (2006) 1669-1683] for homothetic interval orders, we also write ''the'' representation (u"1,u"2) of R in terms of u and a twisting factor.

We show that no Arshon sequence of odd order can be generated by an iterated morphism. This solves a problem of Kitaev and generalizes results of Berstel and of Kitaev.

The algebra of polylogarithms (iterated integrals over two differential forms ω 0 = d z/z and ω 1 = d z/(1−z) ) is isomorphic to the shuffle algebra of polynomials on non-commutative variables x 0 and x 1 . The multiple zeta values (MZVs) are obtained by evaluating the polylogarithms at z=1 . From a second shuffle product, we compute a Grobner basis of the kernel of this evaluation morphism. The completeness of this Grobner basis up to order 12 is equivalent to the classical conjecture about MZVs. We also show that certain known relations on MZVs hold for polylogarithms.

An object X of a category is said to have the projection property if the only idempotent morphisms f : X x X --> X are the projections. Here a morphism f : X x X --> X is called idempotent if f circle Delta = id for the diagonal map Delta : X --> X x X. There are two motivations for studying the question whether X has the projection property. Firstly, Arrow's 'dictator theorem' states that the only maps of a product XA to X with certain properties are the projections (see Arrow, 1963; Pouzet et al. 1996). Secondly, the projection property is closely related to the fixed point property (see Corominas, 1990). In that paper the projection property has been introduced for posets. It has been studied in a more general setting by Davey et al. (1994) and Pouzet et al. (1996). For a detailed discussion of the projection property, its background and connections with other properties see also the paper by Pouzet (this volume). In this paper we prove that an irreducible building of spherical type and of rank at least 2 has the projection property. Actually, the theorem is more general. It holds not only for the case of a product of two copies of X but for any finite number of copies of X and is thus similar to Arrow's theorem. For a precise statement of the hypotheses see below. By contrast, every reducible building and every building of rank one does not have the projection property. We also give a counterexample concerning the finiteness assumption of the theorem. (C) 1998 Published by Elsevier Science B.V. All rights reserved.

The aim of this paper is to give axiomatizations for sixteen types of finite relations. These classes of relations are obtained as intersections of the following basic classes of relations: total relations, surjective relations, partial functions, and injective relations.A normal form for all relations is given and each of the sixteen types of relations is (syntactically) characterized by certain additional conditions on this normal form.For each of the sixteen types T, a set of identities ET is singled out. The class of relations of type T forms an initial algebra in the category of all algebras which satisfy ET. In the first part of this paper, for each type T the involved algebras are symmetric strict monoidal categories (in the sense of MacLane), enriched with certain specific constants.

Ehrenfeucht's conjecture states that every language L has a finite subset F such that, for any pair (g, h) of morphisms, g and h agree on every word of L if and only if they agree on every word of F. We show that it holds if and only if every infinite system of equations (with a finite number of unknowns) over a free monoid has an equivalent finite subsystem. It is shown that this holds true for rational (regular) systems of equations.The equivalence and inclusion problems for finite and rational systems of equations are shown to be decidable and, consequently, the validity of Ehrenfeucht's conjecture implies the decidability of the HDOL and DTOL sequence equivalence problems. The simplicity degree of a language is introduced and used to argue in support of Ehrenfeucht's conjecture.

We study a class of discrete dynamical systems that consist of the following data: (a) a finite (labeled) graph Y with vertex set {1,...,n}, where each vertex has a binary state, (b) a vertex labeled multi-set of functions (F"i","Y:F"2^n->F"2^n)"i and (c) a permutation @p@?S"n. The function F"i","Y updates the binary state of vertex i as a function of the states of vertex i and its Y-neighbors and leaves the states of all other vertices fixed. The permutation @p represents a Y-vertex ordering according to which the functions F"i","Y are applied. By composing the functions F"i","Y in the order given by @p we obtain the sequential dynamical system (SDS)[F"Y,@p]=@?i=1nF"@p"("i")","Y:F"2^n@?F"2^n.Let G[F"Y,@p] be the graph with vertex set F"2^n and edge set {(x,[F"Y,@p](x))|x@?F"2^n}. An SDS-morphism between [F"Y,@p] and [F"Z,@s] is a triple (@f,@h,@F), where @f:Y@?Z is a graph-morphism, @h:S"|"Z"|@?S"|"Y"| is a map such that @h(@s)=@p and @F is a digraph-morphism @F:G[F"Z,@s]@?G[F"Y,@p]. Our main result is that locally bijective graph-morphisms (coverings) between dependency graphs of SDS naturally induce SDS-morphisms. We show how these SDS-morphisms allow for a new proof for the upper bound on the number of inequivalent SDS obtained by only varying their underlying permutations. Here, two SDS are called inequivalent if they are inequivalent as dynamical systems. Furthermore, we apply our result in order to obtain phase space properties of SDS.

The work in this paper divides naturally into five sections. After an introductory section, Section 2 treats the basic concepts of finite linear function spaces. In section 3 morphisms on such spaces are considered. The results of Sections 2 and 3 are applied to the study of measures on hypergraphs in Section 4. In particular, various measure morphisms are characterized. Section 5 treats the dimension of the space of measures on a hypergraph.

We prove that for every finite homogeneous effect algebra E there exists a finite orthoalgebra O(E) and a surjective full morphism φE:O(E)→E. If E is lattice ordered, then O(E) is an orthomodular lattice. Moreover, φE preserves blocks in both directions: the (pre)image of a block is always a block.

The problems to decide whether H ⩽ G for input graphs H , G where ⩽ is ‘isomorphic to a subgraph’, ‘isomorphic to an induced subgraphs’, ‘isomorphic to a subdivision’, ‘isomorphic to a contraction’ or their combination, are NP-complete. We discuss the complexity of these problems when G is restricted to be a partial k -tree (in other terminology: to have tree-width ⩽ k , to be k -decomposable, to have dimension ⩽ k ). Under this restriction the problems are still NP-complete in general, but there are polynomial algorithms under some natural restrictions imposed on H , for example when H has bounded degrees. We also give a polynomial time algorithm for the n disjoint connecting paths problem restricted to partial k -trees (with n part of input).

A word w is a fixed point of a nontrivial morphism h if w=h(w) and h is not the identity on the alphabet of w. The paper presents the first polynomial algorithm deciding whether a given finite word is such a fixed point. The algorithm also constructs the corresponding morphism, which has the smallest possible number of non-erased letters.

Dual maps have been introduced as a generalization to higher dimensions of word substitutions and free group morphisms. In this paper, we study the action of these dual maps on particular discrete planes and surfaces -- namely stepped planes and stepped surfaces. We show that dual maps can be seen as discretizations of toral automorphisms. We then provide a connection between stepped planes and the Brun multi-dimensional continued fraction algorithm, based on a desubstitution process defined on local geometric configurations of stepped planes. By extending this connection to stepped surfaces, we obtain an effective characterization of stepped planes (more exactly, stepped quasi-planes) among stepped surfaces., Comment: 37 pages, 15 figures

A fibration of graphs is a morphism that is a local isomorphism of in-neighbourhoods, much in the same way a covering projection is a local isomorphism of neighbourhoods. This paper develops systematically the theory of graph fibrations, emphasizing in particular those results that recently found application in the theory of distributed systems.

This paper is mainly concerned with positive sets and positive functions ina finite linear function space. Our two main results characterize positive functions and minimal positive sets. We then show that certain morphisms preserve both the cone of positive functions and minimal positive sets. Finally we specialize these results to the case of measures on a hypergraph.

We present three themes of interest for future research that require the cooperation of fairly large teams: 1. linear spaces as building blocks; 2. data for an Atlas of linear spaces; 3. morphisms of linear spaces.

Infinite permutations (in our sense) were introduced in 2005 by Fon-Der-Flaass and Frid. We introduce an infinite permutation @t in some sense similar to the Thue-Morse word w (where w is the fixed point of the morphism @f"w:[email protected]?01,[email protected]?10). We suggest two essentially different definitions of @t and show their equivalence.