Graph rewriting (original) (raw)
Una transformació de grafs, o reescriptura de grafs, és una tècnica per crear algorístmicament un nou graf a partir d'un altre graf donat. Té nombroses aplicacions, des de l'enginyeria de programari fins a algorismes i generació d'imatges.
| Property | Value |
|---|---|
| dbo:abstract | Una transformació de grafs, o reescriptura de grafs, és una tècnica per crear algorístmicament un nou graf a partir d'un altre graf donat. Té nombroses aplicacions, des de l'enginyeria de programari fins a algorismes i generació d'imatges. La reescriptura de grafs es pot utilitzar com a abstracció de computacions. La idea bàsica és que l'estat d'una computació es pot representar en forma de graf, i els passos següents en aquesta computació es poden representar mitjançant regles de transformació sobre el graf. Aquestes regles consisteixen d'un graf de partida, que s'encaixa amb un subgraf per a l'edtat complet, i un graf de substitució, que reemplaçarà el subgraf encaixat. (ca) Graphersetzungssysteme dienen der formalen Beschreibung der Veränderung von Graphen. Sie werden häufig mit Computerprogrammen implementiert und damit ausführ- und anwendbar gemacht. Ein Graphersetzungssystem ist eine Menge von Graphersetzungsregeln . Eine Graphersetzungsregel besteht aus dem Mustergraphen der linken Seite sowie dem Ersetzungsgraphen der rechten Seite. Eine Regel wird in einer direkten Ableitung angewandt, ist der Arbeitsgraph vor der Regelanwendung, der modifizierte Arbeitsgraph danach.Eine Regelanwendung besteht aus dem Finden einer Instanz von in (Pattern Matching, hier: Teilgraphen-Isomorphie) und dem Ersetzen der gefundenen Instanz durch eine Instanz der rechten Seite .Eine Ableitung ist eine Folge von Regelanwendungen, die einen Ausgangsgraph in einen resultierenden Graphen überführt. Verschiebt sich der Fokus vom Verändern eines gegebenen Graphen hin zum Erzeugen aller, aus einem Startgraphen ableitbarer Graphen, wird von einer Graphgrammatik anstelle eines Graphersetzungssystems und von Produktionen anstelle von Regeln gesprochen. Die Vereinigung der beim systematischen Aufzählen entstehenden Graphen ist die Sprache der Graphgrammatik. Meist werden zudem die Graphelemente in Nichtterminale und Terminale unterschieden, und nur die Nichtterminale ersetzt; unter der Sprache werden dann nur die ableitbaren terminalen Graphen verstanden. Wohlgeformtheit von Graphen wird häufig über das Enthaltensein in der Sprache einer kontextfreien Graphgrammatik definiert. Ein gegebener Graph kann dann mit einem Graphparser, der berechnet, ob er in der Sprache der Graphgrammatik enthalten ist, auf Wohlgeformtheit geprüft werden, im Erfolgsfall erhält man zudem seine Ableitung(en). Graphersetzungssysteme können (auch) als eine Verallgemeinerung der Termersetzungssysteme von (Grund-)Termen / deren Bäumen auf Graphen angesehen werden. (de) En ciencias de la computación, transformación de grafos, o reescritura de grafos, Se refiere a la técnica de crear nuevos grafos a partir de un grafo origina de forma algorítmica. Tiene numerosas aplicaciones, desde ingeniería de software, ( y también Verificación de software) hasta diseño de algoritmos y generación de imágenes. Las transformaciones de grafos pueden ser usadas como abstracción computacional. la idea básica es que el estado de un cálculo puede ser representado como un grafo, los siguientes pasos de ese cálculo pueden ser entonces representados como reglas de transformación en ese grafo. Dichas reglas consisten en un grafo original, que debe coincidir con un subgrafo en su estado completo, y un grafo de reemplazo que sustituirá a dicho grafo coincidente. Formalmente, un sistema de reescritura de grafos suele consistir de un conjunto de reglas de reescritura de la forma , con siendo "grafos de patrón" (o lado izquierdo) y siendo "grafo de reemplazo" (o lado derecho de la regla). Una regla de reescritura se aplica al grafo anfitrión buscando una ocurrencia en el grafo de patrón (Búsqueda de patrones, así resolviendo el Problema de isomorfismo de subgrafos) y reemplazando la ocurrencia encontrada por una instancia del grafo de reemplazo. Reglas de reescritura pueden ser más reguladas en el caso de grafo etiquetados, como en una gramática de grafos regulada por cadenas. A veces gramática de grafos se usa como sinónimo de sistema de reescritura de grafos, especialmente en el contexto de ; diferentes estilos de escritura se utilizan para enfatizar el objetivo buscado, como la enumeracion de todos los grafos desde un grafo inicial, es decir, la generación de un idioma de grafos, en lugar de simplemente transformar un estado dado (grafo anfitrión) a un nuevo estado. (es) In computer science, graph transformation, or graph rewriting, concerns the technique of creating a new graph out of an original graph algorithmically. It has numerous applications, ranging from software engineering (software construction and also software verification) to layout algorithms and picture generation. Graph transformations can be used as a computation abstraction. The basic idea is that if the state of a computation can be represented as a graph, further steps in that computation can then be represented as transformation rules on that graph. Such rules consist of an original graph, which is to be matched to a subgraph in the complete state, and a replacing graph, which will replace the matched subgraph. Formally, a graph rewriting system usually consists of a set of graph rewrite rules of the form , with being called pattern graph (or left-hand side) and being called replacement graph (or right-hand side of the rule). A graph rewrite rule is applied to the host graph by searching for an occurrence of the pattern graph (pattern matching, thus solving the subgraph isomorphism problem) and by replacing the found occurrence by an instance of the replacement graph. Rewrite rules can be further regulated in the case of labeled graphs, such as in string-regulated graph grammars. Sometimes graph grammar is used as a synonym for graph rewriting system, especially in the context of formal languages; the different wording is used to emphasize the goal of constructions, like the enumeration of all graphs from some starting graph, i.e. the generation of a graph language – instead of simply transforming a given state (host graph) into a new state. (en) Na Teoria dos Grafos, reescrita de grafos denota um sistema de reescrita para grafos, isto é, um conjunto de regras de reescrita de grafos da forma , sendo o grafo usado como padrão (no lado esquerdo) e o grafo de substituição (no lado direito da regra). Uma regra de reescrita de grafos é aplicada ao grafo hospedeiro procurando por uma ocorrência do grafo padrão (resolvendo assim o problema do isomorfismo de subgrafos) e substituindo a ocorrência encontrada por uma instância do grafo de substituição. Algumas vez gramática de grafos é usado como um sinônimo para sistema de reescrita de grafos, especialmente no contexto de linguagens formais; a expressão distinta é usada para enfatizar o objetivo de enumerar todos os grafos a partir de um grafo inicial, isto é, descrevendo uma linguagem de grafos (como em uma gramática de atributos), em vez de transformar um estado dado (um grafo hospedeiro) em um novo estado. (pt) В информатике переписывание графов (также перезапись графов, преобразование графов, трансформация графов) — техника по созданию нового графа изисходного графа алгоритмическим образом.Переписывание графов находит широкое применение в компьютерных науках, например, в конструировании программного обеспечения, в , в генерировании изображений, в компиляторах, в графовых базах данных. Преобразования графов можно использовать в качестве абстракции вычислений.Основная идея заключается в том, что состояние вычисления может быть представлено в виде графа, дальнейшие шаги этого вычисления могут быть представлены как правила преобразования на этом графе.Такие правила состоят из исходного графа, который должен быть сопоставлен с подграфом полного состояния, и заменяющего графа, который заменит сопоставленный подграф. Формально система переписывания графа обычно состоит из множества правил переписывания графа в форме , где называется графом-образцом (или левой стороной), а называется заменяющим графом (или правой частью правила). Правило переписыванияграфа применяется к исходному графу путем поиска вхождения шаблонного графа (сопоставление с образцом, тем самым решая проблему изоморфизма подграфа) изамены найденного вхождения экземпляром заменяющего графа. Правила переписываниямогут быть дополнительно упорядочены в случае помеченных графов, например, вграфовых грамматиках, регулируемых строками. Иногда понятие графовой грамматики используется в качестве синонима для системыпереписывания графа, особенно в контексте формальных языков; различные формулировкииспользуются, чтобы подчеркнуть цель конструкций, таких как перечисление всехграфов из некоторого начального графа, то есть генерация графового языка –вместо простого преобразования исходного состояния (хостового графа) в новоесостояние. (ru) |
| dbo:thumbnail | wiki-commons:Special:FilePath/GraphRewriteExample_color.png?width=300 |
| dbo:wikiPageExternalLink | http://www.elsevier.com/locate/entcs http://www.informatik.uni-trier.de/~ley/db/conf/gg/handbook1997.html http://emoflon.org/ http://groove.cs.utwente.nl/ http://tinkerpop.apache.org/gremlin.html http://wiki.opencog.org/w/RelEx http://www.fmi.uni-stuttgart.de/szs/publications/koenigba/habilschrift.pdf http://www.fujaba.de/ http://www.se.rwth-aachen.de/tikiwiki/tiki-index.php%3Fpage=Research%3A+Progres.html https://uoycs-plasma.github.io/GP2/ https://archive.today/20150317152250/https:/www.soley-technology.com/en/pr-soley-studio https://web.archive.org/web/20110217171142/http:/user.cs.tu-berlin.de/~gragra/agg/ https://www.worldscientific.com/worldscibooks/10.1142/3303 https://www.worldscientific.com/worldscibooks/10.1142/4180 https://www.worldscientific.com/worldscibooks/10.1142/4181 http://opus.kobv.de/btu/volltexte/2009/593/pdf/thesis.pdf https://www.eclipse.org/henshin/ http://homepages.laas.fr/khalil/GMTE/ http://www.emorf.org http://www.graphsynth.com https://dx.doi.org/10.1016/j.tcs.2011.07.004 https://github.com/Verites/verigraph/ https://github.com/tinkerpop/gremlin/wiki/Graph-Rewriting |
| dbo:wikiPageID | 1252846 (xsd:integer) |
| dbo:wikiPageLength | 14965 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1077289437 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Up_to_isomorphism dbr:Dependency_grammar dbr:Double_pushout_graph_rewriting dbr:Critical_pair_(logic) dbr:Rewriting dbr:GrGen dbr:Graph_(discrete_mathematics) dbr:Graph_homomorphism dbr:Model_checking dbr:Morphism dbr:Operational_semantics dbr:Link_grammar dbr:Logic dbr:Story-driven_modeling dbr:Computer_science dbr:Clean_programming_language dbr:Software_engineering dbr:C++ dbr:C_Sharp_(programming_language) dbr:Database_theory dbr:GReAT dbr:Linear_graph_grammar dbr:Graph_Database dbr:Eclipse_Modeling_Framework dbr:Formal_verification dbr:Formal_grammar dbr:Formal_language dbr:Graph_matching dbr:Graph_theory dbr:Haskell_(programming_language) dbr:Attributed_graph_grammar dbc:Graph_rewriting dbr:Java_(programming_language) dbr:Hypergraph dbr:Model_transformation dbr:VIATRA dbr:Software_construction dbr:Integrated_development_environment dbr:OpenCog dbr:Automated_verification dbr:Category_theory dbr:XML dbr:Model-driven_architecture dbr:Pattern_matching dbr:Shape_grammar dbr:Subgraph_isomorphism_problem dbr:Pushout_(category_theory) dbr:Single_pushout_graph_rewriting dbr:Injective dbr:Term_graph dbr:Double-pushout_approach dbr:Abstract_rewriting dbr:Labeled_graph dbr:Labeled_multigraph dbr:Single-pushout_approach dbr:VDM_Verlag dbr:Interaction_net dbr:Layout_algorithm dbr:File:GraphRewriteExample_color.png dbr:Port_graph_grammar |
| dbp:wikiPageUsesTemplate | dbt:Citation dbt:Cite_book dbt:Cite_journal dbt:Refbegin dbt:Refend dbt:Reflist dbt:Short_description |
| dct:subject | dbc:Graph_rewriting |
| rdf:type | yago:Abstraction100002137 yago:Communication100033020 yago:Language106282651 yago:WikicatFormalLanguages |
| rdfs:comment | Una transformació de grafs, o reescriptura de grafs, és una tècnica per crear algorístmicament un nou graf a partir d'un altre graf donat. Té nombroses aplicacions, des de l'enginyeria de programari fins a algorismes i generació d'imatges. (ca) Graphersetzungssysteme dienen der formalen Beschreibung der Veränderung von Graphen. Sie werden häufig mit Computerprogrammen implementiert und damit ausführ- und anwendbar gemacht. Ein Graphersetzungssystem ist eine Menge von Graphersetzungsregeln . Eine Graphersetzungsregel besteht aus dem Mustergraphen der linken Seite sowie dem Ersetzungsgraphen der rechten Seite. Graphersetzungssysteme können (auch) als eine Verallgemeinerung der Termersetzungssysteme von (Grund-)Termen / deren Bäumen auf Graphen angesehen werden. (de) In computer science, graph transformation, or graph rewriting, concerns the technique of creating a new graph out of an original graph algorithmically. It has numerous applications, ranging from software engineering (software construction and also software verification) to layout algorithms and picture generation. (en) En ciencias de la computación, transformación de grafos, o reescritura de grafos, Se refiere a la técnica de crear nuevos grafos a partir de un grafo origina de forma algorítmica. Tiene numerosas aplicaciones, desde ingeniería de software, ( y también Verificación de software) hasta diseño de algoritmos y generación de imágenes. (es) В информатике переписывание графов (также перезапись графов, преобразование графов, трансформация графов) — техника по созданию нового графа изисходного графа алгоритмическим образом.Переписывание графов находит широкое применение в компьютерных науках, например, в конструировании программного обеспечения, в , в генерировании изображений, в компиляторах, в графовых базах данных. (ru) Na Teoria dos Grafos, reescrita de grafos denota um sistema de reescrita para grafos, isto é, um conjunto de regras de reescrita de grafos da forma , sendo o grafo usado como padrão (no lado esquerdo) e o grafo de substituição (no lado direito da regra). Uma regra de reescrita de grafos é aplicada ao grafo hospedeiro procurando por uma ocorrência do grafo padrão (resolvendo assim o problema do isomorfismo de subgrafos) e substituindo a ocorrência encontrada por uma instância do grafo de substituição. (pt) |
| rdfs:label | Graph rewriting (en) Reescriptura de grafs (ca) Graphersetzungssystem (de) Reescritura de grafos (es) Reescrita de grafos (pt) Переписывание графов (ru) |
| owl:sameAs | freebase:Graph rewriting yago-res:Graph rewriting wikidata:Graph rewriting dbpedia-ca:Graph rewriting dbpedia-de:Graph rewriting dbpedia-es:Graph rewriting dbpedia-pt:Graph rewriting dbpedia-ru:Graph rewriting https://global.dbpedia.org/id/Wb78 |
| prov:wasDerivedFrom | wikipedia-en:Graph_rewriting?oldid=1077289437&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/GraphRewriteExample_color.png |
| foaf:isPrimaryTopicOf | wikipedia-en:Graph_rewriting |
| is dbo:wikiPageRedirects of | dbr:Determinate_graph_rewriting dbr:Graph_grammar dbr:Graph_rewriting_system dbr:Graph_transformation dbr:Term_graph_rewriting dbr:Hypergraph_grammar |
| is dbo:wikiPageWikiLink of | dbr:Entry_point dbr:List_of_computer_scientists dbr:Double_pushout_graph_rewriting dbr:Interaction_nets dbr:Intermediate_representation dbr:Rewriting dbr:ZX-calculus dbr:Clean_(programming_language) dbr:GrGen dbr:Graph_(discrete_mathematics) dbr:Graph_homomorphism dbr:Halin_graph dbr:Determinate_graph_rewriting dbr:Domain-specific_language dbr:GXL dbr:List_of_CLI_languages dbr:Adhesive_category dbr:Graph_(abstract_data_type) dbr:Graph_operations dbr:Graph_theory dbr:Rewrite dbr:Grzegorz_Rozenberg dbr:Abstract_semantic_graph dbr:Dorothea_Blostein dbr:Graph_grammar dbr:Graph_rewriting_system dbr:Graph_transformation dbr:Henshin_(disambiguation) dbr:Model_transformation_language dbr:Shape_grammar dbr:Term_graph_rewriting dbr:Subgraph_isomorphism_problem dbr:Single_pushout_graph_rewriting dbr:Shared_Risk_Resource_Group dbr:Term_graph dbr:Hypergraph_grammar |
| is foaf:primaryTopic of | wikipedia-en:Graph_rewriting |
