About: A graph grammar with parallel replacement of subgraphs, based on the single-pushout approach in graph rewriting, was designed which constructs Cayley graphs of monoids of transformations of a finite set, with permutation groups as a special case. As input, graph-based representations of a finite number of generating transformations have to be specified; they will then correspond to the edge types of the Cayley graph which is the final result of the rewriting process. The grammar has [Formula: see text] rules, where d is the number of generators, and operates at two scale levels. The fine-scale level is the level of elements on which the transformations act and where their composition is calculated by parallel subgraph replacement. The coarse-scale level corresponds to the transformations themselves which are organized in the Cayley graph in a sequential rule application process. Both scale levels are represented in a single graph. The graph grammar was implemented in the programming language XL on the software platform GroIMP, a graph rewriting tool which was originally designed for simulating the growth of plants.   Goto Sponge  NotDistinct  Permalink

An Entity of Type : fabio:Abstract, within Data Space : covidontheweb.inria.fr associated with source document(s)

AttributesValues
type
value
  • A graph grammar with parallel replacement of subgraphs, based on the single-pushout approach in graph rewriting, was designed which constructs Cayley graphs of monoids of transformations of a finite set, with permutation groups as a special case. As input, graph-based representations of a finite number of generating transformations have to be specified; they will then correspond to the edge types of the Cayley graph which is the final result of the rewriting process. The grammar has [Formula: see text] rules, where d is the number of generators, and operates at two scale levels. The fine-scale level is the level of elements on which the transformations act and where their composition is calculated by parallel subgraph replacement. The coarse-scale level corresponds to the transformations themselves which are organized in the Cayley graph in a sequential rule application process. Both scale levels are represented in a single graph. The graph grammar was implemented in the programming language XL on the software platform GroIMP, a graph rewriting tool which was originally designed for simulating the growth of plants.
Subject
  • Graph theory
  • Geometric group theory
  • Graph families
  • Group theory
  • Programming languages
  • Programming language classification
  • Application-specific graphs
  • Permutation groups
  • Graph rewriting
  • Cayley graphs
part of
is abstract of
is hasSource of
Faceted Search & Find service v1.13.91 as of Mar 24 2020


Alternative Linked Data Documents: Sponger | ODE     Content Formats:       RDF       ODATA       Microdata      About   
This material is Open Knowledge   W3C Semantic Web Technology [RDF Data]
OpenLink Virtuoso version 07.20.3229 as of Jul 10 2020, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (94 GB total memory)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software