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