Search

The goal of this article is to characterize the lax pullback complement of a given partial morphism along a total morphism, in an -partial morphism category, where is an exponentiable stable system. To achieve this, we first show that if a lax pullback complement of a partial morphism exists in the partial morphism category, then a lax pullback complement of its total part exists in the base category. For the converse, we consider two cases. In the first case the base category is assumed to be adhesive and the morphism along which we take the lax pullback complement is admissible (i.e., its pushout along a monomorphism forms a pullback complement square), while in the second case the base category is -cohesive, however the morphism along which we take the lax pullback complement is an arbitrary total morphism. Finally as a byproduct we provide the connection between exponentials in the partial morphism category and its base category. [ABSTRACT FROM AUTHOR]

In engineering and architecture, different approaches have been developed that share the use of graph transformation to automate design processes or to search for design solutions by means of computational design synthesis. In order to give an overview of these approaches, we provide a review of articles published in the last decade. Forty-eight articles were reviewed to determine similarities and differences of these approaches. Research fields in method development for the representation of design problems and the processing of graph transformations, as well as the application of graph transformations in engineering, architecture, and shape grammars were identified. Different approaches for the documentation of the vocabulary and the rules were examined. Finally, different approaches for rule applications were analyzed. Based on found limitations, future research directions are suggested. [ABSTRACT FROM AUTHOR]

Dataflow Models of Computation (MoCs) are widely used in embedded systems, including multimedia processing, digital signal processing, telecommunications, and automatic control. In a dataflow MoC, an application is specified as a graph of actors connected by FIFO channels. One of the first and most popular dataflow MoCs, Synchronous Dataflow (SDF), provides static analyses to guarantee boundedness and liveness, which are key properties for embedded systems. However, SDF and most of its variants lack the capability to express the dynamism needed by modern streaming applications. In particular, the applications mentioned above have a strong need for reconfigurability to accommodate changes in the input data, the control objectives, or the environment. We address this need by proposing a new MoC called Reconfigurable Dataflow (RDF). RDF extends SDF with transformation rules that specify how and when the topology and actors of the graph may be reconfigured. Starting from an initial RDF graph and a set of transformation rules, an arbitrary number of new RDF graphs can be generated at runtime. A key feature of RDF is that it can be statically analyzed to guarantee that all possible graphs generated at runtime will be consistent and live. We introduce the RDF MoC, describe its associated static analyses, and present its implementation and some experimental results. [ABSTRACT FROM AUTHOR]

The ability to handle evolving graph structures is important both for programming languages and modeling languages. Of various languages that adopt graphs as primary data structures, a graph rewriting language LMNtal provides features of both (concurrent) programming languages and modeling languages, and its implementation unifies ordinary program execution and model checking functionalities. Unlike pointer manipulation in imperative languages, LMNtal allows us to manipulate graph structures in such a way that the well-formedness of graphs is guaranteed by the language itself. However, since the shapes of graphs can be complex and diverse compared to algebraic data structures such as lists and trees, it is a non-obvious important task to formulate types of graphs to verify individual programs. With this motivation, this paper discusses LMNtal ShapeType, a type checking framework that applies the basic idea of Structured Gamma to a concrete graph rewriting language. Types are defined by generative grammars written as LMNtal rules, and type checking of LMNtal programs can accordingly be done by exploiting the model checking features of LMNtal itself. We gave a full implementation of type checking exploiting the features of the LMNtal meta-interpreter and confirmed that it works for practical operations on various graph structures, including single-step and multi-step operations on non-algebraic data structures and data structures with numerical shape constraints.

The causal set program and the Wolfram physics project leave open the problem of how a graph that is a (3+1)-dimensional Minkowski spacetime according to its simple geodesic distances could be generated solely from simple deterministic rules. This paper provides a solution by describing simple rules that characterize discrete Lorentz boosts between 4D lattice graphs, which combine further to form Wigner rotations that produce isotropy and lead to the emergence of the continuous Lorentz group and the (3+1)-dimensional Minkowski spacetime. On such graphs, the speed of light, the proper time interval, as well as the proper length are all shown to be highly accurate. [ABSTRACT FROM AUTHOR]

In this article, we first give two equivalent criteria for the existence of pullback complements along a universal morphism in a category in terms of the existence of pullbacks and co-universality of certain morphisms. Then we introduce the notion of admissible morphism and we characterize the existence of pullback complements in a partial morphism category along an admissible morphism in terms of the existence of pullback complements in its base category; when the base category is a certain admissible category. At the end we make a comparison between partial pullback complement rewriting and sesqui-pushout, double-pushout and single pushout rewritings, for an admissible match. [ABSTRACT FROM AUTHOR]

Capturing human knowledge underlying the design and engineering of products has been among the main goals of computational engineering since its very beginning. Over the last decades, various approaches have been proposed to tackle this objective. Among the most promising approaches is the application of graph theory for representing product structures by defining nodes representing entities and edges representing relations among them. The concrete meaning of these structures ranges from geometry representations over hierarchical product breakdowns to functional descriptions and flows of information or resources. On top of these graph structures, graph rewriting techniques provide another powerful layer of technology. By enabling the formal definition of rules for transforming graph structures, they allow on the one hand side to formally capture the engineering development process. On the other hand, the assembly of rewriting rules into graph grammars allows for an exhaustive search of the solution space of the engineering problem at hand. In combination with search strategies, an automated optimization of the design under given constraints and objectives can be realized. The paper provides an overview of the current state-of-the-art in graph rewriting and its applications in engineering design, with a focus on the built environment. It concludes with a discussion of the progress achieved and the missing research gaps.

This paper proposes a simplicity-oriented approach and framework for language-to-language transformation of, in particular, graphical languages. Key to simplicity is the decomposition of the transformation specification into sub-rule systems that separately specify purpose-specific aspects. We illustrate this approach by employing a variation of Plotkin's Structural Operational Semantics (SOS) for pattern-based transformations of typed graphs in order to address the aspect 'computation' in a graph rewriting fashion. Key to our approach are two generalizations of Plotkin's structural rules: the use of graph patterns as the matching concept in the rules, and the introduction of node and edge types. Types do not only allow one to easily distinguish between different kinds of dependencies, like control, data, and priority, but may also be used to define a hierarchical layering structure. The resulting Type-based Structural Operational Semantics (TSOS) supports a well-structured and intuitive specification and realization of semantically involved language-to-language transformations adequate for the generation of purpose-specific views or input formats for certain tools, like, e.g., model checkers. A comparison with the general-purpose transformation frameworks ATL and Groove, illustrates along the educational setting of our graphical WebStory language that TSOS provides quite a flexible format for the definition of a family of purpose-specific transformation languages that are easy to use and come with clear guarantees. [ABSTRACT FROM AUTHOR]

Modular bridge structures made of carbon fibre reinforced ultra‐high performance concrete Graph‐based design and trajectory‐sensitive manufacturing In order to enable the prefabrication of bridge structures in a continuous production line, extensive changes in design and execution are necessary. Therefore, this paper explains a holistic and end‐to‐end digital design process for a modular construction system that composes planar, additively manufactured modules. The system is computationally represented with a graph‐based data model, laying the foundation for design automation employing graph rewriting rules. Sets of rules are employed to generate modular structures according to two approaches: Either existing component geometries are segmented, or rules formalize the aggregation of structures. At this process state, predominantly geometric information is available. This information is developed into a semantically rich representation of the decomposition until a highly detailed production model for each module can be instantiated parametrically. Because of the flexible definition based on NURBS, the production model can depict a variety of possible joining situations and connections. Beyond this, the model is the basis of the printing path generation for the additive manufacturing process. The path is determined according to the principal stress directions, numerically interpolating the results of a non‐linear FE analysis. Along this printing path, the alignment of carbon fibre reinforcement is steered by custom nozzle technology, enabling outstanding material properties of the manufactured components. [ABSTRACT FROM AUTHOR]

Adhesive categories , and variants such as M , N -adhesive ones, marked a watershed moment for the algebraic approaches to the rewriting of graph-like structures, since they provide an abstract framework where many general results (on e.g. parallelism) could be recast and uniformly proved. However, often checking that a model satisfies the adhesivity properties is far from immediate. In this paper we present a new criterion giving a sufficient condition for M , N -adhesivity , a generalisation of the original notion of adhesivity. To show the effectiveness of this criterion, we apply it to several existing categories of graph-like structures, including hypergraphs, various kinds of hierarchical graphs (a formalism that is notoriously difficult to fit in the mould of algebraic approaches to rewriting), and combinations of them. [ABSTRACT FROM AUTHOR]

The general question of what constitutes bio-curation for rule-based modelling of cellular signalling is posed. A general approach to the problem is presented, based on rewriting in hierarchies of graphs, together with a specific instantiation of the methodology that addresses our particular bio-curation problem. The current state of the ongoing development of the KAMI bio-curation tool, based on this approach, is outlined along with our plans for future development. [ABSTRACT FROM AUTHOR]

We study spans of cospans in a category C and explain how to horizontally and vertically compose these. When C is a topos and the legs of the spans are monic, these two forms of composition satisfy the interchange law. In this case there is a bicategory of objects, cospans, and 'monic-legged' spans of cospans in C. One motivation for this construction is an application to graph rewriting. [ABSTRACT FROM AUTHOR]