Back to Search
Start Over
Drags: A compositional algebraic framework for graph rewriting
- Source :
- Theoretical Computer Science, Theoretical Computer Science, 2019, 777, pp.204-231. ⟨10.1016/j.tcs.2019.01.029⟩, Theoretical Computer Science, Elsevier, 2019, 777, pp.204-231. ⟨10.1016/j.tcs.2019.01.029⟩
- Publication Year :
- 2019
- Publisher :
- Elsevier BV, 2019.
-
Abstract
- International audience; We are interested in a natural generalization of term-rewriting techniques to what we call drags, viz. finite, directed, ordered, rooted multigraphs, each vertex of which is labeled by a function symbol. To this end, we develop a rich algebra of drags that generalizes the familiar term algebra and its associated rewriting capabilities. Viewing graphs as terms provides an initial building block for rewriting with such graphs, one that should impact the many areas where computations take place on graphs.
- Subjects :
- Vertex (graph theory)
General Computer Science
Computer science
Generalization
0102 computer and information sciences
02 engineering and technology
01 natural sciences
Term algebra
ACM: G.: Mathematics of Computing
Theoretical Computer Science
ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION
Drags
0202 electrical engineering, electronic engineering, information engineering
[INFO]Computer Science [cs]
Algebraic number
Graph rewriting
symmetric monoidal category
Symmetric monoidal category
Function (mathematics)
Graph
rewriting
Vertex (geometry)
Algebra
010201 computation theory & mathematics
Computer Science::Programming Languages
020201 artificial intelligence & image processing
Rewriting
[INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]
Graphs
MathematicsofComputing_DISCRETEMATHEMATICS
Subjects
Details
- ISSN :
- 03043975 and 18792294
- Volume :
- 777
- Database :
- OpenAIRE
- Journal :
- Theoretical Computer Science
- Accession number :
- edsair.doi.dedup.....3a4e9dd0a91bb146b94a90e2e6d7c140