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 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]

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]

Copyright of Beton- Und Stahlbetonbau is the property of Wiley-Blackwell and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

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]

The use of Complex Event Processing (CEP) and Stream Processing (SP) systems to process high-volume, high-velocity Big Data has renewed interest in procedures for managing these systems. In particular, selfmanagement and adaptation of runtime platforms have been common research themes, as most of these systems run under dynamic conditions. Nevertheless, the research landscape in this area is still young and fragmented. Most research is performed in the context of specific systems, and it is difficult to generalize the results obtained to other contexts. To enable generic and reusable CEP/SP system management procedures and self-management policies, this research introduces the Attributed Graph Rewriting for Complex Event Processing Management (AGeCEP) formalism. AGeCEP represents queries in a language- and technologyagnostic fashion using attributed graphs. Query reconfiguration capabilities are expressed through standardized attributes, which are defined based on a novel classification of CEP query operators. By leveraging this representation, AGeCEP also proposes graph rewriting rules to define consistent reconfigurations of queries. To demonstrate AGeCEP feasibility, this research has used it to design an autonomic manager and to define a selected set of self-management policies. Finally, experiments demonstrate that AGeCEP can indeed be used to develop algorithms that can be integrated into diverse CEP systems. [ABSTRACT FROM AUTHOR]

We consider the proof complexity of the minimal complete fragment, KS, of standard deep inference systems for propositional logic. To examine the size of proofs we employ atomic flows, diagrams that trace structural changes through a proof but ignore logical information. As results we obtain a polynomial simulation of versions of Resolution, along with some extensions. We also show that these systems, as well as bounded-depth Frege systems, cannot polynomially simulate KS, by giving polynomial-size proofs of certain variants of the propositional pigeonhole principle in KS. [ABSTRACT FROM AUTHOR]

Using procedural narrative generation in video games provides a flexible way to extend game play and provide more depth to the game world at low cost to the developers. Current examples of narrative generation in commercial games, however, tend to be simplistic, resulting in repetitive and uninteresting stories. In this paper, we develop a system for narrative generation using a context-aware graph-rewriting framework. We use a graph representation of the game world to create narratives which reflect and modify the current world state. Using a novel set of metrics to evaluate narrative quality, we validate our approach by comparing our generated narratives to other procedurally generated stories, as well as to authored narratives from commercially successful and critically praised games. The results show that our narratives compare favorably to the authored narratives. Our metrics provide a new approach to narrative analysis, and our system provides a unique and practical approach to story generation. [ABSTRACT FROM PUBLISHER]

SUMMARY Model processing programs are regularly used when working with models or synthetizing the code from them; therefore, their verification has become an essential component of constructing reliable software in model-based software engineering. Models are usually formalized and visualized as graphs; therefore, model processing programs based on algebraic graph rewriting systems-such programs are called model transformations-are often applied, and their verification has become an important research area. The goal of our research is to support offline transformation analysis by automated methods, where offline means that only the definition of the program itself, the language definitions of its source and target models are used during the analysis. Therefore, the results are independent from concrete source models, and the analysis needs to be performed only once. Based on previous work, this paper provides the synthesis and of a set of individual components and improves them to provide a complete verification solution: (i) a language is introduced to specify the properties to be verified; (ii) a formalism to describe model transformations in a declarative way; and (iii) automated algorithms that can analyse the declarative transformations as well as the properties expressed by the language. Besides its theoretical basis, the implementation of a verification framework is presented, and its operation is illustrated on a case study. Although the formal verification of model transformation properties is algorithmically undecidable in general, our goal is to provide a practically usable, scoped framework that can largely facilitate the manual verification of model transformations. Copyright © 2013 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Pull-tabbing is an evaluation approach for functional logic computations, based on a graph transformation recently proposed, which avoids making irrevocable nondeterministic choices that would jeopardize the completeness of computations. In contrast to other approaches with this property, it does not require an upfront cloning of a possibly large portion of the choice's context. We formally define the pull-tab transformation, characterize the class of programs for which the transformation is intended, extend the computations in these programs to include the transformation, and prove the correctness of the extended computations. [ABSTRACT FROM AUTHOR]

GrGen.NET is a generative programming system for graph rewriting, transforming intuitive and expressive rewrite rule specifications into highly efficient .NET code. The user is supported by a convenient environment consisting of a graph viewer, an interactive shell with integrated debugging support, and an elegant domain-specific language for the combination of rewrite rules. After rapid prototyping with these tools, the resulting graph transformation programmes can be easily integrated into arbitrary .NET applications to serve as the algorithmic kernel. Expressiveness, convenience, and speed are exemplified by GrGen-solutions to the case studies AntWorld, Refactoring, and Conference Scheduling—besides others. [ABSTRACT FROM AUTHOR]

Model-based development is one of the most promising solutions for several problems of industrial software engineering. Graph transformation is a proven method for processing domain-specific models. However, in order to be used by domain experts without graph transformation experts, it must be fast even if not tweaked for speed manually based on knowledge available only to the implementers of the transformation system. In this paper, we compare the performance of such manual optimizations with a solution using automated optimization based on sharing of matches between overlapping left-hand-sides of sequentially independent rules. This yields a 11% improvement in our scenario, although our prototypical implementation only exploits overlapping between, at most, two rules, and the analyzed benchmark does not contain many cases where the optimization is applicable. [ABSTRACT FROM AUTHOR]

The existing extensions of Petri nets supporting dynamic changes cannot ensure preservation of desired properties of the modeled systems. This paper tries to address this problem. By extending the structure of the net rewriting system (NRS) and modifying the specification of its rewriting rule, we present improved net rewriting system (INRS). INRS enjoys four important properties, i.e., locality, transitivity, reflexivity, and reversibility. A practical system subject to dynamic changes can be modeled by an INRS, and its desired properties can be preserved with the state evolvement of the INRS. The property-preserving principles of INRS and their strict proofs are provided as well. Finally, a case study is provided to demonstrate the modeling of an automated manufacturing cell with changeable structure using an INRS. The result shows that the desired properties of the cell are still preserved despite its model evolvement. [ABSTRACT FROM AUTHOR]

Model-driven development of software systems envisions transformations applied in various stages of the development process. Similarly, the use of domain-specific languages also necessitates transformations that map domain-specific constructs into the constructs of an underlying programming language. Thus, in these cases, the writing of transformation tools becomes a first-class activity of the software engineer. This paper introduces a language that was designed to support implementing highly efficient transformation programs that perform model-to-model or model-to-code translations. The language uses the concepts of graph transformations and metamodeling, and is supported by a suite of tools that allow the rapid prototyping and realization of transformation tools. [ABSTRACT FROM AUTHOR]

Economic globalization leads to complex decentralized company structures calling for the extensive use of distributed IT-systems. The business processes of a company have to reflect these changes of infrastructure. In particular, due to new electronic applications and the inclusion of a higher number of—potentially unknown—persons, the business processes are more vulnerable against malicious attacks than traditional processes. Thus, a business should undergo a security analysis. Here, the vulnerabilities of the business process are recognized, the risks resulting from the vulnerabilities are calculated, and suitable safeguards reducing the vulnerabilities are selected. Unfortunately, a security analysis tends to be complex and affords expensive security expert support. In order to reduce the expense and to enable domain experts with in-depth insight in business processes but with limited knowledge about security to develop secure business processes, we developed the framework MoSSBP facilitating the handling of business process security requirements from their specification to their realization. In particular, MoSS BP provides graphical concepts to specify security requirements, repositories of various mechanisms enforcing the security requirements, and a collection of reference models and case studies enabling the modification of the business processes. In this paper, the MoSS BP -framework is presented. Additionally, we introduce a tool supporting the MoSSBP-related security analysis of business processes and the incorporation of safeguards. This tool is based on object-oriented process models and acts with graph rewrite systems. Finally, we clarify the application of the MoSSBP-framework by means of a business process for tender-handling which is provided by anonymity-preserving safeguards. [ABSTRACT FROM AUTHOR]

Architecture transformations are frequently performed during software design and maintenance. However this activity is not well supported at a sufficiently abstract level. In this paper, the authors characterize architecture transformations using graph rewriting rules, where architectures are represented in graph notations. Architectures are usually required to satisfy certain constraints during evolution. Therefore a way is presented to construct the sufficient and necessary condition for a transformation to preserve a constraint. The condition can be verified before the application of the transformation. Validated transformations are guaranteed not to violate corresponding constraints whenever applied. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

Rewriting usually relies on a notion of substitution which can be understood as the succession of three basic operations: deletion of the part to be rewritten to provide a context, union of this context with the right-hand side of a rule, liaison of those two parts, most often by identification of some corresponding items. In the field of graph rewriting, this has led to the elegant, productive and therefore popular method known as the double push-out approach to graph rewriting. Yet this method has met its descriptive limits when trying to deal with the various notions of node replacement. In this paper we show how – when set in a proper framework – products (or pullbacks) can provide a very generic and uniform rewriting mechanism which extends uniformly to arbitrary complicated graph-like structures. [ABSTRACT FROM AUTHOR]

We describe an approach to modeling the dynamics of distributed systems. By distributed systems we mean systems consisting of concurrent processes communicating via shared ports and posing certain synchronization requirements, via the ports, to the adjacent processes. The basic idea is to use graphs to represent states of such systems, and graph rewriting to represent their evolution. The kind of graph rewriting we use is based on simple context-free productions which are, however, combined by means of a synchronization mechanism. This allows for a good level of expressivity in the system without sacrifying full distribution. To formally model this kind of graph rewriting, however, we do not adopt the classical graph rewriting style but a more general framework, called the tile model, which allows for a clear separation between sequential rewriting and synchronization. Then, since the problem of satisfying the synchronization requirements may be a complex combinatorial problem, we suggest exploiting existing techniques for constraint solving. This is based on the observation that the synchronization problem can be modeled as a (finite domain) constraint problem. In this respect, we propose to use both local consistency techniques, to remove the possible redundancies in a system state, and a distributed backtracking search algorithm, as used in distributed constraint solving. Our method has the following advantages: first, it provides a formal description of the way a distributed system evolves; second, it seems promising from the performance point of view, since the techniques we propose for combining productions have been proved to be very convenient in several cases; finally, the kind of system evolution we describe here is just a particular instance of what can be described by using the tile model in its most general form, thus suggesting the possibility of extending our approach to modeling more complex distributed systems. [ABSTRACT FROM AUTHOR]

The high-level Compiler Intermediate Language CIL is a general-purpose description language of parallel graph rewriting computational model intended for parallel implementation of declarative languages on multiprocessor systems. In this paper, we first outline a new Hybrid Execution Model(HEM) and corresponding parallel abstract machine PAM/TGR based on Extended parallel Graph Rewriting Computational Model EGRCM for implementing CIL language on distributed memory multiprocessor systems. Then we focus on the compiling CIL language with various optimizing techniques such as pattern matching, rule indexing, node ordering and compile-time partial scheduling. The experimental results on a 16-node Transputer Array demonstrates the effectiveness of our model and strategies. [ABSTRACT FROM AUTHOR]

In image analysis, recognition of the primitives plays an important role. Subsequent analysis is used to interpret the arrangement of primitives. This subsequent analysis must make allowance for errors or ambiguities in the recognition of primitives. In this paper, we assume that the primitive recognizer produces a set of possible interpretations for each primitive. To reduce this primitive-recognition ambiguity, we use contextual information in the image, and apply constraints from the image domain. This process is variously termed constraint satisfaction, labeling or discrete relaxation. Existing methods for discrete relaxation are limited in that they assume a priori knowledge of the neighborhood model: before relaxation begins, the system is told (or can determine) which sets of primitives are related by constraints. These methods do not apply to image domains in which complex analysis is necessary to determine which primitives are related by constraints. For example, in music notation, we must recognize which notes belong to one measure, before it is possible to apply the constraint that the number of beats in the measure should match the time signature. Such constraints can be handled by our graph-rewriting paradigm for discrete relaxation: here neighborhood-construction is interleaved with constraint-application. In applying this approach to the recognition of simple music notation, we use approximately 180 graph-rewriting rules to express notational constraints and semantic-interpretation rules for music notation. The graph rewriting rules express both binary and higher-order notational constraints. As image-interpretation proceeds, increasingly abstract levels of interpretation are assigned to (groups of) primitives. This allows application of higher-level constraints, which can be formulated only after partial interpretation of the image. [ABSTRACT FROM AUTHOR]

Dealing properly with sharing is important for expressing some of the common compiler optimizations as source-to-source transformations, such as common subexpressions elimination, lifting of free expressions and removal of invariants from a loop. Term graph rewriting is a computational model to accommodate these concerns. In this paper we are interested in defining a term model for term graph rewriting systems, which allows us to prove total correctness of those optimizations. We introduce the notion of Böhm tree, and show that for orthogonal term graph rewriting systems, Böhm tree equivalence defines a congruence. Total correctness then follows in a straightforward way from showing that if a program M contains less sharing than a program N, then both M and N have the same Böhm tree. Using Böhm trees we also show that orthogonal term graph rewriting systems are a correct implementation of orthogonal term rewriting systems. This boils down to showing that the behavior of a term graph can be deduced from its finite approximations, that is, graph rewriting is a continuous operation. Our approach differs from that of other researchers which is based on infinite rewriting. [ABSTRACT FROM AUTHOR]

We believe that software architectures should provide an appropriate basis for the proof of properties of large software. This goal can be achieved through a clearcut separation between computation and communication and a formal definition of the interactions between individual components. We present formalism for the definition of software architectures in terms of graphs. Nodes represent the individual agents and edges define their interconnection. Individual agents can communicate only along the links specified by the architecture. The dynamic evolution of an architecture is defined independently by a "coordinator." An architecture style is a class of architectures specified by a graph grammar. The class characterizes a set of architectures sharing a common communication pattern. The rules of the coordinator are statically checked to ensure that they preserve the constraints imposed by the architecture style. [ABSTRACT FROM AUTHOR]

Planning is investigated in an area where classical STRIPS-like approaches usually fail. The application domain is therapy (i.e. repair) for complex dynamic processes. The peculiarities of this domain are discussed in some detail for convincingly developing the characteristics of the inductive planning approach presented. Plans are intended to be run for process therapy. Thus, plans are programs. Because of the unavoidable vagueness and uncertainty of information about complex dynamic processes in the case of disturbance, therapy plan generation turns out to be inductive program synthesis. There is developed a graph-theoretically based approach to inductive therapy plan generation. This approach is investigated from the inductive inference perspective. Particular emphasis is put on consistent and incremental learning of therapy plans. Basic application scenarios are developed and compared to each other. The inductive inference approach is invoked to develop and investigate a couple of planning algorithms. The core versions of these algorithms are successfully implemented in Lisp and Prolog. [ABSTRACT FROM AUTHOR]