Lösungsdarstellungen einer Klasse spezieller Operatorgleichungen

The gluing construction for graphs, which is used in algebraic theory of graph grammars and applied in several fields of Computer Science, is a pushout construction in the category of graphs. In addition to the well known universal properties of pushouts also several nonuniversal properties are required in algebraic graph theory. A systematic collection of these nonuniversal properties is presented in this paper.     

Recognition in a Distributed System

A general design for a distributed system is presented which characterizes system recognition of external events as a sheaf in a Grothendieck topos on a category of diagrams. The information that the system may derive from this sheaf involves transitions through a state space constructed from a collection of topoi interconnected by geometric morphisms. Similarities of this design with natural neural systems leads to the premise that cognitive processes involve the construction and manipulation of sheaf-like structures.     

Monads on Composition Graphs

Collections of objects and morphisms that fail to form categories, inasmuch as the expected composites of two morphisms need not always be defined, were introduced in [14,15] under the name composition graphs. In [14,16], notions of adjunction and weak adjunction for composition graphs are proposed. Building on these definitions, we now introduce a concept of monads for composition graphs and show that the usual correspondence between adjunctions and monads remains correct, i.e. that (weak) adjunctions give rise to monads and that all monads are induced by adjunctions. Monads are described in terms of natural transforms as well as in terms of Kleisli triples, which seem to be better suited in the absence of associativity. The realization of a monad by an adjunction relies on a generalization of the Kleisli construction to composition graphs; on the other hand, the Eilenberg–Moore construction produces only a weak adjunction and admits comparison functors from weak adjunctions. As a first nontrivial example, we determine the algebras of the word monad on the composition graph of full morphisms between sets with a distinguished subset.     

Toric rings arising from vertex cover ideals

We extend the sortability concept to monomial ideals which are not necessarily generated in one degree and as an application we obtain normal Cohen-Macaulay toric rings attached to vertex cover ideals of graphs. Moreover, we consider a construction on a graph called a clique multi-whiskering which always produces vertex cover ideals with componentwise linear powers.     

Algebraic structures on graphs

In this paper we consider directed graphs with algebraic structures: group-graphs, ringgraphs, involutorial graphs, affine graphs, graphs of morphisms between graphs, graphs of reduced paths of an involutorial graph, etc. We show also how several well-known algebraic constructions can be carried over to graphs. As a typical example we generalize the construction of the group of automorphisms of a set, by constructing a group-graph associated with any given graphΓ. It is the group-graph of reduced paths of the involutorial graph associated to the graph of automorphisms ofΓ.     

A 2-groupoid Characterisation of the Cubical Homotopy Pushout

We give a 2-track-theoretical characterisation of the homotopy pushout of a 3-corner by recognising the mapping 2-simplex as an initial object in a coherent homotopy category of Hausdorff spaces under a 3-corner with morphisms expressed in terms of the 1-morphisms and 2-morphisms of a homotopy 2-groupoid.     

Double-Pullback Transitions and Coalgebraic Loose Semantics for Graph Transformation Systems

The classical algebraic approach to graph transformation is a mathematical theory based on categorical techniques with several interesting applications in computer science. In this paper, a new semantics of graph transformation systems (in the algebraic, double-pushout (DPO) approach) is proposed in order to make them suitable for the specification of concurrent and reactive systems. Classically, a graph transformation system comes with a fixed behavioral interpretation. Firstly, all transformation steps are intended to be completely specified by the rules of the system, that is, there is an implicit frame condition: it is assumed that there is a complete control about the evolution of the system. Hence, the interaction between the system and its (possibly unknown) environment, which is essential in a reactive system, cannot be modeled explicitly. Secondly, each sequence of transformation steps represents a legal computation of the system, and this makes it difficult to model systems with control. The first issue is addressed by providing graph transformation rules with a loose semantics, allowing for unspecified effects which are interpreted as activities of the environment. This is formalized by the notion of double-pullback transitions, which replace (and generalize) the well-known double-pushout diagrams by allowing for spontaneous changes in the context of a rule application. Two characterizations of double-pullback transitions are provided: the first one describes them in terms of extended direct DPO derivations, and the second one as incomplete views of parallel or amalgamated derivations. The issue of constraining the behavior of a system to transformation sequences satisfying certain properties is addressed instead by introducing a general notion of logic of behavioral constraints, which includes instances like start graphs, application and consistency conditions, and temporal logic constraints. The loose semantics of a system with restricted behavior is defined as a category of coalgebras over a suitable functor. Such category has a final object which includes all finite and infinite transition sequences satisfying the constraints.     

Strong homotopy induced by adjacency structure

This paper generalizes the concept of SA-homotopy in finite topological adjacency category, which is introduced in our previous work, to graph category and discusses its properties. We prove that every SA-strong deformation retract of a simple graph G could be obtained by removing trivial vertices one by one, which makes it possible to allow an iterative algorithm of finding all SA-strong deformation retracts of G. We also obtain that two simple graphs are SA-homotopy equivalent if and only if they have graph isomorphic cores. Compared with the graph homotopy transformation defined by S.T. Yau et al. and the s-homotopy transformation defined by R. Boulet et al., the main advantage of SA-homotopy transformation is that it could reflect correspondences between vertices, and hence it more accurately describe the transformation process than the graph homotopy transformation and s-homotopy transformation. As an application of SA-homotopy on graphs, we introduce the mapping class group of a graph, which also shows its advantage over the graph homotopy transformation and the s-homotopy transformation.     

代数的局部完备集范畴和FS-局部dcpo范畴的笛卡儿闭性

本文引入了代数的局部完备集,FS-局部dcpo,局部稳定映射等概念．主要结果是：以局部Scott连续映射为态射的代数的局部完备集范畴,以局部稳定映射为态射的代数的局部完备集范畴以及以局部Scott连续映射为态射的FS-局部dcpo范畴都是笛卡儿闭范畴．     

Every finite graph is a full subgraph of a rigid graph

We prove that every finite undirected graph is a full subgraph of a rigid graph. Our construction proceeds on taking a family of “mutually rigid” graphs and attaching them to the vertices of a given graph in a one-to-one manner; then the vertices are fixed on their place. Actually, the new graph is “strongly rigid”, which enables us to show that the category of all graphs containing a given finite graph as a full subgraph is binding.     

The Krull-Schmidt Theorem in the Case Two

We study what happens if, in the Krull-Schmidt Theorem, instead of considering modules whose endomorphism rings have one maximal ideal, we consider modules whose endomorphism rings have two maximal ideals. If a ring has exactly two maximal right ideals, then the two maximal right ideals are necessarily two-sided. We call such a ring of type 2. The behavior of direct sums of finitely many modules whose endomorphism rings have type 2 is completely described by a graph whose connected components are either complete graphs or complete bipartite graphs. The vertices of the graphs are ideals in a suitable full subcategory of Mod-R. The edges are isomorphism classes of modules. The complete bipartite graphs give rise to a behavior described by a Weak Krull-Schmidt Theorem. Such a behavior had been previously studied for the classes of uniserial modules, biuniform modules, cyclically presented modules over a local ring, kernels of morphisms between indecomposable injective modules, and couniformly presented modules. All these modules have endomorphism rings that are either local or of type 2. Here we present a general theory that includes all these cases.     

Categorical principles,techniques and results for high-level-replacement systems in computer science

The aim of this paper is to give an introduction how to use categorical methods in a specific field of computer science: The field of high-level-replacement systems has its roots in the well-established theories of formal languages, term rewriting, Petri nets, and graph grammars playing a fundamental role in computer science. More precisely, it is a generalization of the algebraic approach to graph grammars which is based on gluing constructions for graphs defined as pushouts in the category of graphs. The categorical theory of high-level-replacement systems is suitable for the dynamic handling of a large variety of high-level structures in computer science including different kinds of graphs and algebraic specifications. In this paper we discuss the basic principles and techniques from category theory applied in the field of high-level-replacement systems and present some basic results together with the corresponding categorical proof techniques.     

DIGRAPH CATEGORIES AND LINE DIGRAPH FUNCTORS

The authors define line digraph functors on digraph category which are full and faith-ful and,as a consequence of the result,determine all homomorphisms in De Bruijn-Goodgraph category and automorphisms of Kautz digraph category.Moreover the authorsconsider a type of arc-full morphisms of digraph category such that F~n(f) is arc-full foreach functor F~n,and succeeding paper [9] study the strong homomorphisms of de Bruijn-Good digraph.     

The path relation for directed planar graphs in rectangles, and its relation to the free diad

In this paper, we define the path relation of a directed graph to be the relation which relates two vertices if there is a path from the first to the second. We study the restriction of this relation to paths from sources to sinks, and consider the question of when two finite graphs embedded in a rectangle give the same relation. We find a set of local changes to these graphs which can be used to get between any two graphs for which this relation is the same. Furthermore, we classify the relations which can arise as this relation for a finite directed graph embedded in a rectangle as the triconvex relations between finite ordinals (defined in this paper).This work originated from some of the author’s work on category theory. It turns out that the category of finite ordinals and relations that can be the path relation of a directed graph embedded in a rectangle, is relevant to the study of diads—introduced by the author as a common generalisation of monads and comonads (note that the terms diad and dyad have been used to mean different things by other authors). More specifically, the referee of one of the author’s papers suggested that it would be useful to identify the category which plays the role for diads that the category of finite ordinals and order-preserving functions plays for monads. It turns out that the category of finite ordinals and relations that can be path relations of graphs embedded in a rectangle, is exactly the category that plays this role.     

Hom complexes and homotopy in the category of graphs

In this extended abstract we develop a notion of ×-homotopy of graph maps that is based on the internal hom associated to the categorical product. We show that graph ×-homotopy is characterized by the topological properties of the so-called Hom complex, a functorial way to assign a poset to a pair of graphs. Along the way we establish some structural properties of Hom complexes involving products and exponentials of graphs, as well as a symmetry result which can be used to reprove a theorem of Kozlov involving foldings of graphs. We end with a discussion of graph homotopies arising from other internal homs, including the construction of ‘A-theory’ associated to the cartesian product in the category of reflexive graphs. For proofs and further discussions we refer the reader to the full paper [Anton Dochtermann. Hom complexes and homotopy theory in the category of graphs. arXiv:math.CO/0605275].